刘二强,李银奎

(青海民族大学数学与统计学院,青海 西宁 810007)

网络结构的边毁裂度

刘二强,李银奎

(青海民族大学数学与统计学院,青海 西宁 810007)

在毁裂度的基础上,研究图的边的毁裂度.通过优化组合、归纳假设的方法界定了图的边毁裂度的值,如笛卡尔积图:Pm×Pn,Pm×Cn,Cm×Cn,Km×Kn,并界定了G=G1×G2的边毁裂度的界.最后给出了一些基本图,如路、圈、星图、完全二部图Km,n的线图边毁裂度.

边毁裂度;笛卡尔积图;线图

1 引言

特高压交流电网不但要求稳定可靠、不容易被破坏,而且要求特高压交流网络一旦被毁后能够容易确定位置,且极易修复.借助图的连通参数讨论图网络的稳定性,对于在复杂电网中的应用有特殊意义.文献[1-8]引入了如边连通度、边坚韧度、边完整度、离散度、边粘连度等一些不错的刻画参数,只是每个参数都有各自的局限性.图的边毁裂度是一个新的度量参数(文献[8]),对于图网络的刻画也有一定的影响.本文进一步的探讨了路、圈、完全图在笛卡尔积下的图的边毁裂度以及路、圈、星图、完全二部图Km,n在线图下的边毁裂度.

设图G=(V,E),S⊆E(G),用w(G−S)表示G−S的连通分支数,τ(G−S)表示图G−S的最大连通分支的阶数.图的边毁裂度定义为:

对于一个边集S⊆E(G),如果w(G−S)−|S|−τ(G−S)=Er(G),称S为G的一个Er−集.文中讨论的图均为简单、无向图,未提及的术语及定义见文献[7].

2 一些笛卡尔积图的边毁裂度结果

定义 2.1[8]连通图G1与G2的笛卡尔积G1×G2是连通图且对 u1,v1∈V(G1),u2,v2∈V(G2),((u1,u2),(v1,v2))∈E(G1×G2)⇔ 或者 u1=v1,且(u2,v2)∈E(G2),或者u2=v2,且(u1,v1)∈E(G1).

Pm×Pn构造的网络图可以看作是一顶点数为m×n的平面网格.

定理2.1连通图G是……