一類單圈圖的最小能量

王智玉, 高玉斌

(中北大學(xué) 數(shù)學(xué)學(xué)院, 太原 030051)

1 引言與主要結(jié)果

設(shè)G是一個n階簡單連通圖, 其頂點集為V(G)={v1,v2,…,vn}, 邊集為E(G),dG(vi)表示圖G中頂點vi的度,NG(vi)表示頂點vi的鄰集, 其中i=1,2,…,n.若dG(vi)=1, 則vi稱為G的懸掛點.邊數(shù)等于頂點數(shù)的連通圖稱為單圈圖.用G(n,l)表示圍長是l且頂點數(shù)是n的連通單圈圖.Cg∪St是通過連接圈Cg上的一頂點與星圖St的某一懸掛點或中心點組成的一類單圈圖.

(1)

(2)

2 預(yù)備知識

引理1[14]設(shè)G∈G(n,l), 則對所有的k≥0均有(-1)ka2k≥0.若l=2r+1且r是奇數(shù)(或偶數(shù)), 則對所有的k≥0均有(-1)ka2k+1≥0(或≤0).

由式(2)可得

(3)

為方便, 本文設(shè)bi(G)=|ai(G)|, 則εR(G)是一個關(guān)于參數(shù)bi(G)的單調(diào)遞增函數(shù), 其中i=1,2,…,n, 即以下結(jié)論成立.

引理2[14]設(shè)G1和G2是兩個單圈圖, 如果對所有的i≥0均有bi(G1)≥bi(G2), 則εR(G1)≥εR(G2).

3 給定單圈圖的圖變換

3.1 變換Ⅰ

圖1 變換ⅠFig.1 Operation Ⅰ

1) 0

當(dāng)i=2k≥4時, 有

即

2)g≤i≤g+1.

① 圍長g為偶數(shù).當(dāng)i=g=2k時, 有

即

若g≡2(mod 4), 則式(4)中的符號“±”為正; 若g≡0(mod 4), 則式(4)中的符號“±”為負(fù).

② 圍長g為奇數(shù).當(dāng)i=g時, 有

即

3.2 變換Ⅱ

圖2 變換ⅡFig.2 Operation Ⅱ

即

即

若g-1≡2(mod 4), 則式(5)中符號“±”為正; 若g-1≡0(mod 4), 則式(5)中符號“±”為負(fù).

3.3 變換Ⅲ

設(shè)圖G3∈Cg∪St是通過連接圈Cg上的一頂點與星圖St的中心點而生成的單圈圖Cg∪St, 其中Cg=u1u2…ugu1, 圈長g≥6且g為偶數(shù).設(shè)

圖3 變換ⅢFig.3 Operation Ⅲ

當(dāng)i=2k=2時, 有

當(dāng)i=2k=4時, 有

即

3.4 變換Ⅳ

圖4 變換ⅣFig.4 Operation Ⅳ

證明: 易得

其中n≥4.因此

由式(2)知,

故

4 定理1的證明