极大基尔霍夫指数的块图

高珊，钟秀雨，韩硕

(1.湖北大学计算机与信息工程学院， 湖北 武汉 430062；2.应用数学湖北省重点实验室(湖北大学)， 湖北 武汉 430062； 3.湖北大学数学与统计学学院， 湖北 武汉 430062；4.武汉大学数学与统计学院，湖北 武汉 430072)

0 引言

1993年, Klein和Randic在研究电网络时定义了电网距离和基尔霍夫指数.设G是一个连通图，顶点集为V={u1,u2,…,un}.图G中两点ui与uj的有效电阻称为ui与uj的电阻距离，记为rG(ui,uj).图G的基尔霍夫指数，记为Kf(G)，定义为Kf(G)=∑i

本研究首先给出一些基本概念和记号以及图的基尔霍夫指数的相关运算，接着利用移接变形对图的基尔霍夫指数进行了研究，给出了块数小于4的块图的基尔霍夫指数的上界，并刻画了对应的极图.

1 图的基尔霍夫指数的运算

本节中给出图的基尔霍夫指标的基本概念和性质以及相关运算.这些性质和运算在本文中的主要结论的证明中经常用到.

定义1.1设G是一个连通图，G1，G2是G的两个非连通子图.如果E(G)=E(G1)∪E(G2)，V(G)=V(G1)∪V(G2)，且V(G1)∩V(G2)=x，则记G:=G1xG2，并称x为图G的割点(cut vertex或seperating vertex).

定义1.2设G是一个连通图，如果图G不含分离点，则称G是不可分的(nonseperable)，否则是可分的(seperable).

定义1.3设G是一个图，图G的极大不可分离子图称为G的块(block).

注记如果图G是一个不可分离图，则G本身就是一个块.

定义1.4设G是一个连通图，如果G的每个块都是完全图，则称G是块图.

定义1.5给定一个图G，令B={B:B是G的块}，S={v∈V(G):v是G的割点}，定义一个二部图B(G)，B和S分别是B(G)的二部划分，且对任意的B∈B，v∈S.B与v在B(G)中有边相连当且仅当v∈V(B).

定义1.6设G是一个图，若G的块路图B(G)是一条路，则称G为块路图.特别地，若G为块图，则记G=K[n1,n2,…,ni]是由i个块Kni构成的块路图，其中V(Kna)∩V(Kna+1)≠φ，1≤a≤i-1.当i=2时，G=K[n1,n2](如图1)；当i=3时，G=K[n1,n2,n3](如图2).

引理1.7[8]设图G1,G2是两个连通图，令G=G1xG2，其中V(G1)∩V(G2)={x}，则有

Kf(G)=Kf(G1)+Kf(G2)+(|V(G1)|-1)Kfx(G2)+(|V(G2)|-1)Kfx(G1).

引理1.8[9]设图G是一个连通图，x是图G的割点，令G1和G2分别是G-x两个的连通分支，则对于任意的a∈V(G1)，b∈V(G2)，均有rG(a;b)=rG1(a;x)+rG2(x;b).

引理1.9[2]n阶完全图记为Kn，则有如下的结论：

1)Kf(Kn)=n-1；

引理1.10的证明1)令V(Kn1)∩V(Kn2)={x}(如图1)，则由引理1.7和引理1.9可知

图1 K[n1,n2]

Kf(K[n1,n2])=Kf(Kn1)+Kf(Kn2)+(n1-1)Kfx(Kn2)+(n2-1)Kfx(Kn1)

2)令V(Kn1)∩V(Kn2)={x1}，V(Kn2)∩V(Kn3)={x2}(如图2)，则由引理1.7至引理1.9以及(1)可知

图2 K[n1,n2,n3]

=Kfx2(Kn2)+∑z∈V(Kn1){x1}(rKn2(x2,x1)+rKn1(x1,z))

Kf(K[n1,n2,n3])=Kf(K[n1,n2])+Kf(Kn3)+(n3-1)Kfx2(K[n1,n2])+(n1+n2-2)Kfx2(Kn3)

证毕.

2 块图的基尔霍夫指数的上界

本节主要研究块图的基尔霍夫指数的上界.首先我们给出两个块图的移接变形，通过这些运算，给出某些块图的基尔霍夫指数的单调增性质.

引理2.1令H0是一个非平凡块图，H∶=H0xKn1，其中V(H0)∩V(Kn1)={x}，y∈V(Kn1){x}.如果记G=HxKn2(如图3)，G′=HyKn2(如图4)，则Kf(G)

图3 K[nH0,n1,n2]

图4 K[nH0,n1,n2]

引理2.1的证明由引理1.7可知

Kf(G)=Kf(H)+Kf(Kn1)+(|V(H)|-1)Kfx(Kn2)+(n2-1)Kfx(H)；

Kf(G′)=Kf(H)+Kf(Kn1)+(|V(H)|-1)Kfy(Kn2)+(n2-1)Kfy(H).

那么，

Kf(G)-Kf(G′)=(n2-1)(Kfx(H)-Kfy(H)).

由引理1.7～1.9可知

=Kfy(Kn1)+∑z∈V(H0){x}(rKn1(y,x)+rH0(x,z))

引理2.2令G0是一个非平凡块图，H0∶=Kn1vKn2，其中x1∈V(Kn1){v}，x2∈V(Kn2){v}.设G=H0x2G0(如图5),G′=G0x1H0(如图6).则当n2≤n1时，Kf(G)≥Kf(G′)且等号成立当且仅当n1=n2.引理2.2的证明令a=|V(G0)|，b=|V(H0)|，则由引理1.7可知

图5 K[n1,n2,nG0]

图6 K[nG0,n1,n2]

Kf(G)=Kf(G0)+Kf(H0)+(a-1)Kfx2(H0)+(b-1)Kfx2(G0)，

Kf(G′)=Kf(G0)+Kf(H0)+(a-1)Kfx1(H0)+(b-1)Kfx1(G0)，

因此

Kf(G)-Kf(G′)=(a-1)(Kfx2(H0)-Kfx1(H0))

即Kf(G)≥Kf(G′)且等式成立当且仅当n1=n2.证毕.

注记令a1∈V(H0)且a1∈V(Kn2)，b1∈V(G0)，则通过点a1与点b1粘成点x2，把块H0与块G0连接起来得到图5；令a2∈V(H0)且a2∈V(Kn1)，b2∈V(G0)，则通过点b2与点a2粘成点x1，把块G0与块H0连接起来得到图6；那么当第二个块的点数增大时(图6→图5)，块图的基尔霍夫指数也随着增大.

下面我们研究具有小于4个块的n阶连通块图的基尔霍夫指数的上界.

令Bn,k={G:G是一个有k个块的n阶连通块图}.注意到Bn,1={Kn}.因此下面可以假设k≥2.定理2.3令G∈Bn,2，则

定理2.4令G∈Bn,3，则

证毕.