熊金,李怡博
(湖北大學數學與統計學學院, 湖北 武漢 430062)
設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不變邊的條件。 本節中,我們主要研究門檻圖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不變邊。 本節中,我們主要研究輪圖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) 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不變邊。1 門檻圖的PI指標及不變邊
2 輪圖的PI指標及不變邊