兩類聯圖的PI不變邊

熊金,李怡博

(湖北大學數學與統計學學院, 湖北 武漢 430062)

0 引言

設G=(V(G),E(G))和H=(V(H),E(H))是兩個圖。G和H的聯圖,記為G∨H,定義為:

V(G∨H):=V(G)∪V(H),

E(G∨H):=E(G)∪E(H)∪{uv|u∈V(G),v∈V(H)}.

設G1,G2,…,Gr是r個點不交的連通圖,我們用G1+G2+…+Gr表示G1,G2,…,Gr的不交并圖。若G1=G2=…=Gr,則記G1+G2+…+Gr=rG。

令Sk,r=Kk∨rK1,Wn=Cn∨K1,其中Kk為k階完全圖,Cn為n階圈。Sk,r和Wn分別稱為門檻圖[1]和輪圖。

設G=(V(G),E(G))是一個簡單連通圖。令x,y∈V(G),e=uv∈E(G)。圖G中x和y的距離,記為dG(x,y),定義為x與y的最短路的長。令

N1(e|G)={x∈V(G)|dG(x,u)

N2(e|G)={y∈V(G)|dG(y,u)>dG(y,v)}.

圖G的Padmakar-Ivan指標,簡記為PI指標,定義為:

PI(G)=∑e=uv∈E(G)[n1(e|G)+n2(e|G)],

其中ni(e|G)=|Ni(e|G)|,i=1,2。

如果PI(G-e)=PI(G),那么邊e稱為圖G的PI不變邊。

圖的PI指標是Khadikar[4]在2000年提出的一個基于距離的拓撲指標。PI指標被提出以來,受到了廣大學者的關注,廣泛應用于QSAR和QSPR領域,得到了一些研究成果[2-4]。Khalifeh等[5]給出了笛卡爾乘積圖的PI指標的精確表達式。最近, Indulal等[6]證明了含有奇圈的圖G存在PI不變邊,其中奇圈的每條邊都是圖G的PI不變邊,并且證明了當n≥4時,完全圖Kn沒有PI不變邊。本文中,我們分別研究門檻圖和輪圖存在PI不變邊的條件。

1 門檻圖的PI指標及不變邊

本節中,我們主要研究門檻圖Sk,r的PI指標和Sk,r存在PI不變邊的條件。

首先給出n階完全圖Kn的PI指標。

定理1.1當n≥2時,PI(Kn)=n2-n。

定理1.1的證明當n=2時,設e=uv∈E(K2),顯然N1(e|K2)={u},N2(e|K2)={v}。于是n1(e|K2)+n2(e|K2)=2。

當n≥3時,對任意的邊e=uv∈E(Kn)及任意的點w∈V(Kn){u,v},均有dKn(w,u)=dKn(w,v)。因此N1(e|Kn)={u},N2(e|Kn)={v}。

于是n1(e|Kn)+n2(e|Kn)=2。

接下來,我們計算PI(Sk,r)的值。

定理1.2設k,r是正整數,則PI(Sk,r)=kr2+kr+k2-k。

定理1.2的證明設e=vivj∈E(Sk,r),vl∈V(Sk,r){vi,vj}。

首先證明下面的論斷。

論斷11)如果e∈E1,那么n1(e|Sk,r)+n2(e|Sk,r)=2;

2)如果e∈E2,那么n1(e|Sk,r)+n2(e|Sk,r)=r+1。

論斷1的證明1)注意到dSk,r(vl,vi)=dSk,r(vl,vj)=1。

于是N1(e|Sk,r)={vi},N2(e|Sk,r)={vj}。因此n1(e|Sk,r)+n2(e|Sk,r)=2。

2)若vl∈V1,則dSk,r(vl,vi)=dSk,r(vl,vj)=1;若vl∈V2,則dSk,r(vl,vi)=1<2=dSk,r(vl,vj)。因此N1(e|Sk,r)={vi}∪(V2{vj}),N2(e|Sk,r)={vj}。于是n1(e|Sk,r)+n2(e|Sk,r)=r+1。

由論斷1可知,

=2|E1|+(r+1)|E2|

=kr2+kr+k2-k.

定理1.3如果r=k-1,那么E2的每一條邊都是Sk,r的PI不變邊。

定理1.3的證明設G=Sk,r-v1vk+1, 則dG(v1,vk+1)=2。令E11={v1vj|2≤j≤k},E21={v1vj|k+2≤j≤k+r},E22={vivk+1|2≤i≤k}。顯然E11?E1,E21?E2,E22?E2,且|E11|=k-1,|E21|=r-1,|E22|=k-1。

我們首先證明下面的論斷。

論斷21)如果e∈E11,那么n1(e|G)+n2(e|G)=3;

2)如果e∈E1E11,那么n1(e|G)+n2(e|G)=2;

3)如果e∈E21,那么n1(e|G)+n2(e|G)=r;

4)如果e∈E22,那么n1(e|G)+n2(e|G)=r+2;

5)如果e∈E2(E21∪E22),那么n1(e|G)+n2(e|G)=r+1。

論斷2的證明1)令e=v1vj,其中2≤j≤k。易知dG(vk+1,v1)=2>1=dG(vk+1,vj),且對任意vs∈V(G){v1,vj,vk+1},均有dG(vs,v1)=dG(vs,vj)=1。因此N1(e|G)={v1},N2(e|G)={vj,vk+1}。于是n1(e|G)+n2(e|G)=3。

2)令e=vivj,其中2≤i

3)令e=v1vj,其中k+2≤j≤k+r。當vs∈{vk+1}∪V1{v1}時,dG(vs,v1)=dG(vs,vj);當vs∈V2{vk+1,vj}時,有dG(vs,v1)=1<2=dG(vs,vj)。于是N1(e|G)={v1}∪(V2{vk+1,vj}),N2(e|G)={vj}。因而n1(e|G)+n2(e|G)=r。

4)令e=vivk+1,其中2≤i≤k。若vs∈V1{v1,vi},則dG(vs,vi)=dG(vs,vk+1)=1;若vs∈{v1}∪(V2{vk+1}),有dG(vs,vi)=1<2=dG(vs,vk+1)。因此N1(e|G)={v1,vi}∪(V2{vk+1}),N2(e|G)={vk+1}。

于是n1(e|G)+n2(e|G)=r+2。

5)令e=vivj,其中2≤i≤k,k+2≤j≤k+r。如果vs∈V1{vi},那么dG(vs,vi)=dG(vs,vj)=1;如果vs∈V2{vj},那么dG(vs,vi)=1<2=dG(vs,vj)。于是N1(e|G)={vi}∪(V2{vj}),N2(e|G)={vj}。

因此n1(e|G)+n2(e|G)=r+1。

由論斷2可知,

=3|E11|+2(|E1|-|E11|)+r|E21|+(r+2)|E22|

+(r+1)(|E2|-|E21|-|E22|-1)

=kr2+(k-2)r+k2+k-2,

進而,根據定理1.2可得,PI(Sk,r)-PI(G)=2r-2k+2。因此,當r=k-1時,PI(Sk,r)-PI(G)=0,即v1vk+1是Sk,r的PI不變邊。

由對稱性,可知E2的每一條邊都是Sk,r的PI不變邊。

2 輪圖的PI指標及不變邊

本節中,我們主要研究輪圖Wn的PI指標和Wn存在PI不變邊的條件。

引理2.1[5]當n≥4時,Kn沒有PI不變邊。

我們先計算PI(Wn)的值。

定理2.2當n≥4時,PI(Wn)=n2+3n。

定理2.2的證明我們首先證明下面的論斷。

論斷3的證明1)注意到

dWn(ui-1,ui)=1<2=dWn(ui-1,ui+1);

dWn(ui+2,ui)=2>1=dWn(ui+2,ui+1)。

若us∈V(Wn){ui-1,ui,ui+1,ui+2},則dWn(us,ui)=dWn(us,ui+1)。于是N1(e|Wn)={ui-1,ui},N2(e|Wn)={ui+1,ui+2}。因此n1(e|Wn)+n2(e|Wn)=4。

2)若us∈{ui-1,ui+1},則dWn(us,ui)=dWn(us,u0);當us∈V(Wn){ui-1,ui,ui+1,u0}時,均有dWn(us,ui)=2>1=dWn(us,u0)。因此N1(e|Wn)={ui},N2(e|Wn)=V(Wn){ui-1,ui,ui+1}。從而n1(e|Wn)+n2(e|Wn)=n-1。

由論斷3可知,

=n2+3n。

注意到W3?K4,由引理2.1可知,W3沒有PI不變邊。

定理2.3對任意的1≤i≤4,uiu0均是W4的PI不變邊。

定理2.3的證明令F=W4-u1u0。我們首先證明下面的論斷。

論斷41)如果e∈{u1u2,u1u4},那么n1(e|F)+n2(e|F)=5;

2)如果e∈{u2u3,u3u4,u2u0,u4u0},那么n1(e|F)+n2(e|F)=4;

3)如果e=u3u0,那么n1(e|F)+n2(e|F)=2。

論斷4的證明1)令e=u1uj,其中j=2,4。易知dF(u1,uj)=1,dF(u2,u4)=2,且當ut∈{u3,u0}時,有dF(ut,u1)=2>1=dF(ut,uj)。于是N1(e|F)={u1,u6-j},N2(e|F)={u0,u3,uj}。因此n1(e|F)+n2(e|F)=5。

2)令e=uiuj,其中i=0,3,j=2,4。注意到dF(ui,uj)=dF(u0,u3)=1;dF(u2,u4)=2;dF(u1,ui)=2>1=dF(u1,uj)。于是N1(e|F)={ui,u6-j},N2(e|F)={u1,uj}。因而n1(e|F)+n2(e|F)=4。

3)對任意的ut∈{u1,u2,u4},有dF(ut,u3)=dF(ut,u0)。因此N1(e|F)={u3},N2(e|F)={u0}。于是n1(e|F)+n2(e|F)=2。

由論斷4可知,

=5×2+4×4+2

=28,

從而,根據定理2.2可得,PI(W4)=42+3×4=28=PI(F), 故u1u0是W4的PI不變邊。

由對稱性可知,對任意的1≤i≤4,uiu0都是W4的PI不變邊。

引理2.4對任意的1≤i≤5,uiu0均不是W5的PI不變邊。

引理2.4的證明令H=W5-u1u0。我們先證明下面的論斷。

論斷51)如果e∈{u1u2,u1u5,u2u0,u5u0},那么n1(e|H)+n2(e|H)=5;

3)如果e∈{u3u0,u4u0},那么n1(e|H)+n2(e|H)=3。

論斷5的證明1)令e=u1uj,其中j=2,5。易知dH(uj,u1)=1,dH(u2,u5)=2及dH(u7-k,u1)=dH(u7-k,uj)=2,其中|k-j|=1且k≠1;當up∈{uk,u0}時,有dH(up,u1)=2>1=dH(up,uj)。因此N1(e|H)={u1,u7-j},N2(e|H)={u0,uj,uk}。

于是n1(e|H)+n2(e|H)=5。

令e=u0uj,其中j=2,5。注意到dH(u1,u0)=2>1=dH(u1,uj)及dH(uk,u0)=dH(uk,uj)=1,其中|k-j|=1且k≠1;對任意的up∈{u7-j,u7-k},均有dH(up,u0)=1<2=dH(up,uj)。因此N1(e|H)={u0,u7-j,u7-k},N2(e|H)={u1,uj}。從而n1(e|H)+n2(e|H)=5。

2)令e=uiui+1,其中2≤i≤4。注意到dH(ui-1,ui)=1<2=dH(ui-1,ui+1);dH(ui+2,ui)=2>1=dH(ui+2,ui+1); 若up∈{ui+3,u0},則dH(up,ui)=dH(up,ui+1)。于是N1(e|H)={ui-1,ui},N2(e|H)={ui+1,ui+2}。

因此n1(e|H)+n2(e|H)=4。

3)令e=u0uj,其中j=3,4。易知dH(u0,uj)=dH(u3,u4)=1及dH(uk,u0)=1<2=dH(uk,uj),其中|k-j|=2且k≠1; 對任意的up∈{u1,u7-k,u7-j},有dH(up,u0)=dH(up,uj)。于是N1(e|H)={u0,uk},N2(e|H)={uj}。

因而n1(e|H)+n2(e|H)=3。

由論斷5可知,

=5×4+4×3+3×2

=38,

進而,根據定理2.2可得,PI(W5)-PI(H)=52+3×5-38=2。因此,u1u0不是W5的PI不變邊。

由對稱性可知,對任意的1≤i≤5,uiu0均不是W5的PI不變邊。

定理2.5當n≥5時,Wn沒有PI不變邊。

定理2.5的證明令Q=Wn-e0,e0∈E(Wn)。考慮如下的兩種情形:

由對稱性,不妨假設e0=u1u2。我們先證明下面的論斷。

論斷61)如果e∈{u2u3,u1un},那么n1(e|Q)+n2(e|Q)=3;

3)如果e∈{u1u0,u2u0},那么n1(e|Q)+n2(e|Q)=n;

論斷6的證明1)令e=u2u3。注意到dQ(u4,u2)=2>1=dQ(u4,u3),且當ul∈V(Q){u2,u3,u4}時,有dQ(ul,u2)=dQ(ul,u3)。因此N1(e|Q)={u2},N2(e|Q)={u3,u4}。于是n1(e|Q)+n2(e|Q)=3。

令e=u1un。易知dQ(un-1,u1)=2>1=dQ(un-1,un),且若ul∈V(Q){u1,un,un-1},則dQ(ul,u1)=dQ(ul,un)。于是N1(e|Q)={u1},N2(e|Q)={un-1,un}。從而n1(e|Q)+n2(e|Q)=3。 2)令e=uiui+1,其中3≤i≤n-1。易見dQ(ui-1,ui)dQ(ui+2,ui+1);如果ul∈V(Q){ui-1,ui,ui+1,ui+2},那么dQ(ul,ui)=dQ(ul,ui+1)。因此N1(e|Q)={ui-1,ui},N2(e|Q)={ui+1,ui+2}。于是n1(e|Q)+n2(e|Q)=4。

3)令e=u1u0。注意到dQ(un,u1)=dQ(un,u0)=1; 如果ul∈V(Q){u1,un},那么dQ(ul,u1)>dQ(ul,u0)。因此N1(e|Q)={u1},N2(e|Q)=V(Q){u1,un}。從而n1(e|Q)+n2(e|Q)=n。

令e=u2u0。易知dQ(u3,u2)=dQ(u3,u0)=1;對任意的ul∈V(Q){u2,u3},均有dQ(ul,u2)>dQ(ul,u0)。于是N1(e|Q)={u2},N2(e|Q)=V(Q){u2,u3}。因而n1(e|Q)+n2(e|Q)=n。

4)令e=uiu0,其中3≤i≤n。當ul∈{ui-1,ui+1}時,有dQ(ul,ui)=dQ(ul,u0);當ul∈V(Q){ui-1,ui,ui+1}時,有dQ(ul,ui)>dQ(ul,u0)。于是N1(e|Q)={ui},N2(e|Q)=V(Q){ui-1,ui,ui+1}。因此n1(e|Q)+n2(e|Q)=n-1。

由論斷6可知,

=3×2+4×(n-3)+n×2+(n-1)×(n-2)

=n2+3n-4,

從而,根據定理2.2可得,PI(Wn)-PI(Q)=n2+3n-(n2+3n-4)=4。

因此,u1u2不是Wn的PI不變邊。

根據對稱性,不妨假設e0=u1u0。由引理2.4,我們有n≥6。我們先證明下面的論斷。

論斷71)如果e∈{u1u2,u1un,u2u0,unu0},那么n1(e|Q)+n2(e|Q)=n;

2)如果e∈{u3u4,un-2un-1},那么n1(e|Q)+n2(e|Q)=5;

4)如果e∈{u3u0,un-1u0},那么n1(e|Q)+n2(e|Q)=n-2;

論斷7的證明1)令e=u1u2。注意到dQ(un-1,u1)=dQ(un-1,u2)=2;dQ(un,u1)=1<2=dQ(un,u2);若uq∈V(Q){u1,un-1,un},則dQ(uq,u1)>dQ(uq,u2)。因此N1(e|Q)={u1,un},N2(e|Q)=V(Q){u1,un-1,un}。

于是n1(e|Q)+n2(e|Q)=n。

令e=u1un。易見dQ(u3,u1)=dQ(u3,un)=2;dQ(u2,u1)=1<2=dQ(u2,un);如果uq∈V(Q){u1,u2,u3},則dQ(uq,u1)>dQ(uq,un)。因此N1(e|Q)={u1,u2},N2(e|Q)=V(Q){u1,u2,u3}。從而n1(e|Q)+n2(e|Q)=n。

令e=u2u0。注意到dQ(u3,u2)=dQ(u3,u0)=1;dQ(u1,u2)=1<2=dQ(u1,u0);當uq∈V(Q){u1,u2,u3}時,有dQ(uq,u2)>dQ(uq,u0)。于是N1(e|Q)={u1,u2},N2(e|Q)=V(Q){u1,u2,u3}。

因此n1(e|Q)+n2(e|Q)=n。

令e=unu0。易知dQ(un-1,un)=dQ(un-1,u0)=1;dQ(u1,un)=1<2=dQ(u1,u0);對任意的uq∈V(Q){u1,un-1,un},均有dQ(uq,un)>dQ(uq,u0)。于是N1(e|Q)={u1,un},N2(e|Q)=V(Q){u1,un-1,un}。

因而n1(e|Q)+n2(e|Q)=n。

2)令e=u3u4。易知dQ(u5,u3)=2>1=dQ(u5,u4);若uq∈{u1,u2},則dQ(uq,u3)

于是n1(e|Q)+n2(e|Q)=5。

令e=un-2un-1。注意到dQ(un-3,un-2)=1<2=dQ(un-3,un-1);當uq∈{u1,un}時,有dQ(uq,un-2)>dQ(uq,un-1);對任意的uq∈V(Q){u1,un-3,un-2,un-1,un},有dQ(uq,un-2)=dQ(uq,un-1)。于是N1(e|Q)={un-2,un-3},N2(e|Q)={u1,un-1,un}。

因此n1(e|Q)+n2(e|Q)=5。

3)令e=uiui+1,其中2≤i≤n-1且i≠3,n-2。

易見dQ(ui-1,ui)=1<2=dQ(ui-1,ui+1);dQ(ui+2,ui)=2>1=dQ(ui+2,ui+1);當uq∈V(Q){ui-1,ui,ui+1,ui+2}時,均有dQ(uq,ui)=dQ(uq,ui+1)。因此N1(e|Q)={ui-1,ui},N2(e|Q)={ui+1,ui+2}。

從而n1(e|Q)+n2(e|Q)=4。

4)令e=u3u0。如果uq∈{u1,u2,u4},那么dQ(uq,u3)=dQ(uq,u0);當uq∈V(Q){u1,u2,u3,u4}時,均有dQ(uq,u3)>dQ(uq,u0)。因此N1(e|Q)={u3},N2(e|Q)=V(Q){u1,u2,u3,u4}。

于是n1(e|Q)+n2(e|Q)=n-2。

令e=un-1u0。若uq∈{u1,un-2,un},則dQ(uq,un-1)=dQ(uq,u0);對任意的uq∈V(Q){u1,un-2,un-1,un},有dQ(uq,un-1)>dQ(uq,u0)。于是N1(e|Q)={un-1},N2(e|Q)=V(Q){u1,un-2,un-1,un}。

因而n1(e|Q)+n2(e|Q)=n-2。

5)令e=uiu0,其中4≤i≤n-2。當uq∈{ui-1,ui+1}時,有dQ(uq,ui)=dQ(uq,u0);對任意uq∈V(Q){ui-1,ui,ui+1},均有dQ(uq,ui)>dQ(uq,u0)。于是N1(e|Q)={ui},N2(e|Q)=V(Q){ui-1,ui,ui+1}。

因此n1(e|Q)+n2(e|Q)=n-1。

由論斷7可知,

=n×4+5×2+4×(n-4)+(n-2)×2+(n-1)×(n-5)

=n2+4n-5,

進而,根據定理2.2可得,PI(Wn)-PI(Q)=n2+3n-(n2+4n-5)=5-n。故當n≥6時,PI(Wn)-PI(Q)<0,即u1u0不是Wn的PI不變邊。