景 芬，邵燕靈

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

本文研究的特殊三圈圖是指具有k個(gè)懸掛點(diǎn)且三圈只有1個(gè)公共頂點(diǎn)的圖。同時(shí)給出此類圖中有極大Harary指數(shù)的極圖的圖類。

1 引理

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

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

2 主要結(jié)論

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

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

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

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

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

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

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

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

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

不妨設(shè)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指數(shù)極大圖

情形1g1與g3均為偶數(shù)，則

① 當(dāng)g1-g3=2時(shí)，

② 當(dāng)g1-g3>2時(shí)，

情形2g1為偶數(shù)，而g3為奇數(shù)，則

情形3g1為奇數(shù)，而g3為偶數(shù)，則

情形4g1與g3均為奇數(shù)，則

① 當(dāng)g1-g3=2時(shí)，

② 當(dāng)g1-g3>2時(shí)，

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

引理8 設(shè)G∈Un,k(g1,g2,g3)是Un,k中Harary指數(shù)極大的圖，則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)，對(duì)任意1≤i,j≤k有|ni-nj|≤1，且對(duì)任意1≤i,j≤3有|gi-gj|≤1。不妨設(shè)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指數(shù)極大圖

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

情形1g1=g2=g3。

① 若g1=g2=g3為偶數(shù)，則

② 若g1=g2=g3為奇數(shù)，此時(shí)g3≤2n1-1，從而

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

① 若g3為偶數(shù)，而g2為奇數(shù)，則

② 若g3為奇數(shù)，而g2為偶數(shù)，則

情形3g2=g3=g1-1。

① 若g1為奇數(shù)，而g3為偶數(shù)，則

② 若g1為偶數(shù)，g3為奇數(shù)，則

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

綜合引理4～8，得到關(guān)于Un,k中具有極大Harary指數(shù)的圖的特征刻畫(huà)如下：

定理9 設(shè)G∈Un,k(g1,g2,g3)是Un,k中Harary指數(shù)極大的圖，則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}。