具有k個懸掛點的一類特殊三圈圖的Harary指數

景 芬，邵燕靈

(中北大學 理學院， 太原 030051)

本文研究的特殊三圈圖是指具有k個懸掛點且三圈只有1個公共頂點的圖。同時給出此類圖中有極大Harary指數的極圖的圖類。

1 引理

以下先給出幾條證明定理所需要的引理。

引理1[7]設G是階數n≥2的連通圖，u是G的頂點。設Gk,l是G在u處添加兩條長為k和l的路P和Q后得到的圖，其中P：uv1v2…vk，Q：uu1u2…ul，v1,v2,…,vk和u1,u2,…,ul是不同的點，若k≥l≥1，則H(Gk,l)>H(Gk+1,l-1)。

2 主要結論

設Un,k是所有恰含k個懸掛點且3個圈有且僅有1個公共頂點的n階三圈圖的集合。設Un,k(g1,g2,g3)?Un,k是3個圈(記為Cg1,Cg2,Cg3)的長度分別為g1、g2、g3的Un,k中圖的集合。

引理4 設G∈Un,k(g1,g2,g3)是Un,k(g1,g2,g3)中Harary指數極大圖，點v是G中3個圈的公共頂點，則G中所有圈上頂點(除點v外)的度至多為2。

引理5 設G∈Un,k(g1,g2,g3)是Un,k(g1,g2,g3)中Harary指數極大的圖，點v是G中3個圈的公共頂點，則點v是G中唯一的度大于2的點。

證明由引理4，G中所有圈上頂點(除點v外)的度至多為2。下面僅需證明G中所有不在圈上的點的度至多為2。

圖1 Un,k(g1,g2,g3)中的圖

引理6 設G∈Un,k(g1,g2,g3)是Un,k(g1,g2,g3)中Harary指數極大的圖，則G?Un,k(g1,g2,g3,n1,n2,…,nk)，且|ni-nj|≤1，1≤i,j≤k。

證明設G∈Un,k(g1,g2,g3)是Un,k中Harary指數極大的圖，由引理4與引理5可知，G?Un,k(g1,g2,g3,n1,n2,…,nk)。此時，由引理4不難看出，對任意1≤i,j≤k，有|ni-nj|≤1。證明完畢。

引理7 設G∈Un,k(g1,g2,g3)是Un,k(g1,g2,g3)中Harary指數極大的圖，則G?Un,k(g1,g2,g3,n1,n2,…,nk)，其中|gi-gj|≤1，1≤i,j≤3。

證明設G∈Un,k(g1,g2,g3)是Un,k中Harary指數極大的圖，由引理6知，G?Un,k(g1,g2,g3,n1,n2,…,nk)，且|ni-nj|≤1，1≤i,j≤k。下面用反證法證明對任意1≤i,j≤3，|gi-gj|≤1。

不妨設g1≥g2≥g3，且g1-g3≥2。令Cg1=vv1v2…vg1v，Cg3=vu1u2…ug3v，G′=G-{v1v2,vu1}+{vv2,v1u1}，如圖3、4所示。下面將分4種情形證明H(G)

圖3 Un,k(g1,g2,g3)中Harary指數極大圖

情形1g1與g3均為偶數，則

① 當g1-g3=2時，

② 當g1-g3>2時，

情形2g1為偶數，而g3為奇數，則

情形3g1為奇數，而g3為偶數，則

情形4g1與g3均為奇數，則

① 當g1-g3=2時，

② 當g1-g3>2時，

綜合上述4種情形知H(G)

引理8 設G∈Un,k(g1,g2,g3)是Un,k中Harary指數極大的圖，則G?Un,k(g1,g2,g3,n1,n2,…,nk)，且min{g1,g2,g3}>2max{n1,n2,…,nk}。

證明首先由引理6與引理7知，G?Un,k(g1,g2,g3,n1,n2,…,nk)，對任意1≤i,j≤k有|ni-nj|≤1，且對任意1≤i,j≤3有|gi-gj|≤1。不妨設g1≥g2≥g3，n1≥n2≥…≥nk。

若g1≤2n1，考慮圖G′=G-{wn1wn1-1,vtvt+1}+{vtwn1,wn1vt+1}，如圖5、6所示，下面將證明H(G)≤H(G′)。

圖5 Un,k(g1,g2,g3)中Harary指數極大圖

圖6 G′=G-{wn1wn1-1,vtvt+1}+{vtwn1,wn1vt+1}

情形1g1=g2=g3。

① 若g1=g2=g3為偶數，則

② 若g1=g2=g3為奇數，此時g3≤2n1-1，從而

情形2g1=g2，g3=g2-1。

① 若g3為偶數，而g2為奇數，則

② 若g3為奇數，而g2為偶數，則

情形3g2=g3=g1-1。

① 若g1為奇數，而g3為偶數，則

② 若g1為偶數，g3為奇數，則

從上述3種情形的討論知，若g1≤2n1，則H(G)≤H(G′)，這與H(G)的極大性矛盾。證明完畢。

綜合引理4～8，得到關于Un,k中具有極大Harary指數的圖的特征刻畫如下：

定理9 設G∈Un,k(g1,g2,g3)是Un,k中Harary指數極大的圖，則G∈Un,k(g1,g2,g3,n1,n2,…,nk)，且滿足

② |ni-nj|≤1，1≤i,j≤k；

③ |gi-gj|≤1，1≤i,j≤k；

④ min{g1,g2,g3}>2max{n1,n2,…,nk}。