Halin圖譜半徑的進一步論述

張超權(quán)， 劉曉輝

(桂林航天工業(yè)學(xué)院 理學(xué)部 廣西 桂林 541004)

?

Halin圖譜半徑的進一步論述

張超權(quán)， 劉曉輝

(桂林航天工業(yè)學(xué)院 理學(xué)部 廣西 桂林 541004)

Halin圖； 譜半徑； 正則圖； 行和； 內(nèi)點； 外點

0 引言

矩陣譜半徑的計算和估計，不僅在理論數(shù)學(xué)方面相當(dāng)重要，而且在需要用到譜半徑的一個初始估計值的迭代過程方面也體現(xiàn)出了相當(dāng)重要的作用，該問題引起了大量學(xué)者的興趣，也得到了很多重要的結(jié)果[1-4].

1969年，Halin[4]在討論最小3-連通平面圖時引入了Halin圖，隨后，研究者對Halin圖的點、邊著色、全色數(shù)、譜半徑的上界和極圖等展開了研究[4-8]，并得到了比較好的結(jié)果.

本文研究了上面不等式取得等號的極圖，并且對含有2個內(nèi)點的Halin圖的譜半徑進行了討論，得到了該類Halin圖的譜半徑呈遞增的趨勢.

1 主要結(jié)論

設(shè)G是n階簡單連通圖，A(G)是圖G的鄰接矩陣，A(G)的最大特征值ρ稱為圖G的譜半徑，記為ρ(G).ρ(G)所對應(yīng)的的單位特征向量X稱為圖G的Perron向量.G中與頂點v相關(guān)聯(lián)的邊的數(shù)目稱為頂點v的度，如果G的所有頂點都有相同的頂點度k，則稱G是k-正則圖，簡稱為正則的.

設(shè)T是一個除1度點外，其余點的度至少是3的樹，將樹T的1度點順次連接成一個圈所得到的圖稱為Halin圖.我們稱圈上的點為Halin圖的外點，其余的點為Halin圖的內(nèi)點.

定理1 設(shè)Gn為n階Halin圖，a表示Halin圖的內(nèi)點個數(shù)(a≥2)，則

當(dāng)a=2時，見圖1，有

sv1(A2-2A)=sv1(A2)-2sv1(A)=3n1+n2+1-2(n1+1)=n1+n2-1=n-3,

sv2(A2-2A)=sv2(A2)-2sv2(A)=3n2+n1+1-2(n2+1)=n2+n1-1=n-3,

在與v1相鄰的左邊的n1個點中任取一個點，記為v，則

sv(A2-2A)=sv(A2)-2sv(A)=2×3+n1+1-2×3=n1+1，

在與v2相鄰的右邊的n2個點中任取一個點，我們不妨也記為v，則

sv(A2-2A)=sv(A2)-2sv(A)=2×3+n2+1-2×3=n2+1，

當(dāng)a=3時，見圖2(注：與頂點v2相鄰的頂點也可能會位于下面的邊上，但這并不會影響到下面行和的計算，所以我們可以假設(shè)它們?nèi)慷嘉挥谀骋粭l邊上，下面當(dāng)a取別的數(shù)值時也做同樣的處理)，有

圖1 內(nèi)點為2的n階Halin圖Fig.1 n-order Halin graphs with interior points for 2

圖2 內(nèi)點為3的n階Halin圖Fig.2 n-order Halin graphs with interior points for 3sv1(A2-2A)=sv1(A2)-2sv1(A)=3n1+n2+2-2(n1+1)=n1+n2,sv2(A2-2A)=sv2(A2)-2sv2(A)=3n2+n1+1+n3+1-2(n2+2)=n1+n2+n3-2,

sv=(A2-2A)=sv(A2)-2sv(A)=2×3+n3+1-2×3=n3+1=3，

當(dāng)a=4時，見圖3，有

sv1(A2-2A)=sv1(A2)-2sv1(A)=3n1+n2+2-2(n1+1)=n1+n2，

sv2(A2-2A)=sv2(A2)-2sv2(A)=3n2+n1+1+n3+2-2(n2+2)=n1+n2+n3-1，

sv3(A2-2A)=sv3(A2)-2sv3(A)=3n3+n2+2+n4+1-2(n3+2)=n2+n3+n4-1，

sv4(A2-2A)=sv4(A2)-2sv4(A)=3n4+n3+2-2(n4+1)=n3+n4，

sv(A2-2A)=sv(A2)-2sv(A)=2×3+n3+2-2×3=n3+2=3，

圖3 內(nèi)點為4的n階Halin圖Fig.3 n-order Halin graphs with interior points for 4

圖4 內(nèi)點數(shù)≥5的n階Halin圖Fig.4 n-order Halin graphs with interior points ≥5

當(dāng)a≥5時，見圖4，有

sv1(A2-2A)=sv1(A2)-2sv1(A)=3n1+n2+2-2(n1+1)=n1+n2,

sv2(A2-2A)=sv2(A2)-2sv2(A)=3n2+n1+1+n3+2-2(n2+2)=n1+n2+n3-1,

sv3(A2-2A)=sv3(A2)-2sv3(A)=3n3+n2+2+n4+2-2(n3+2)=n2+n3+n4,

sv4(A2-2A)=sv4(A2)-2sv4(A)=3n4+n3+2+n5+2-2(n4+2)=n3+n4+n5,

… … …

sva-2(A2-2A)=sva-2(A2)-2sva-2(A)==na-3+na-2+na-1,

sva-1(A2-2A)=sva-1(A2)-2sva-1(A)==na-2+na-1+na-1,

sva(A2-2A)=sva(A2)-2sva(A)==na-1+na,

圖5 內(nèi)點數(shù)為2且n1=2的n階 Halin圖(n≥7)Fig.5 n-order Halin graphs with interior points for 2 and n1=2(n≥7)

定理2 設(shè)Gn為內(nèi)點數(shù)為2且n1=2的n階Halin圖(n≥7)，見圖5，則

ρ(Gn-1)<ρ(Gn)<ρ(Gn+1).

證明 含有2個內(nèi)點的Halin圖階數(shù)至少必須是6，所以在這里我們假設(shè)n≥7.下面證明ρ(Gn-1)嚴(yán)格單調(diào)遞增.

即A′(Gn-1)表示在矩陣A(Gn-1)的基礎(chǔ)上加一行和一列0所得到的n階矩陣.則

XTA(Gn)X-XTA′(Gn)X=XT(A(Gn)-A′(Gn))X=2(x2xn+x4xn+xn-1xn-x4xn-1)=

2[(x2+x4+xn-1)xn-x4xn-1],

2 數(shù)值實例

我們通過Mathematics演算得到了內(nèi)點數(shù)為2且n1=2的部分n階Halin圖Gn的譜半徑，見表1.

表1 內(nèi)點數(shù)為2且n1=2的n階Halin圖的譜半徑Tab.1 The spectral radius of n-order Halin graphs with interior points for 2 and n1=2

上面表格中的結(jié)果顯示隨著n取值的增大ρ(Gn)呈遞增的趨勢.

3 結(jié)束語

[1] Liu Jianzhou，Zhang Chaoquan．Some criteria for nonsingular H-matrices[J]． Natural Science Journal of Xiangtan University，2008，30(3)：21-29．

[2] 張超權(quán)，劉曉輝．矩陣譜半徑的一類迭代算法[J]．梧州學(xué)院學(xué)報，2009，19(6)：16-18．

[3] 徐允慶．關(guān)于圖譜半徑的一個不等式[J]．信陽師范學(xué)院學(xué)報:自然科學(xué)版，1992，5(3)：263-268．

[4] Halin R. Studies on minimallyn-connected graph[C]∥Proceedings of Combi Math and its Applications. Oxford，1969．

[5] 李鴻祥，張忠輔，張建勛．Halin圖的色性[J]．上海鐵道學(xué)院學(xué)報，1994,15(1):19-24．

[6] Zhang Zhongfu，Wang Jiangfang， Li Hongxiang．A note on the total chromatic number of 3-regular Halin graph[J]．Mathematics in Economics，1997,14(2):9-12．

[7] 束金龍，洪淵．外平面圖和Halin圖譜半徑的上界[J]．?dāng)?shù)學(xué)年刊，2000,21A(6)：677-682．

[8] 袁勁松，束金龍．Halin圖譜半徑的新上界及極圖[J]．高校應(yīng)用數(shù)學(xué)學(xué)報，2008,23(3):335-342．

(責(zé)任編輯：王浩毅)

A Further Discussion of the Spectral Radius of Halin Graphs

ZHANG Chao-quan， LIU Xiao-hui

(FacultyofScience,GuilinUniversityofAerospaceTechnology,Guilin541004，China)

Halingraph;spectralradius;rowssum;interiorpoint;exteriorpoint

2015-01-10

廣西壯族自治區(qū)教育廳科研項目，編號201106LX709;桂林航天工業(yè)學(xué)院2012年科研項目，編號X12Z022.

張超權(quán)(1979-)，女，湖南桃江人，講師，碩士，主要從事應(yīng)用數(shù)學(xué)研究，E-mail：zhang_chao3201@163.com.

張超權(quán)，劉曉輝.Halin圖譜半徑的進一步論述[J].鄭州大學(xué)學(xué)報：理學(xué)版，2015，47(3)：30-33.

O

A

10.3969/j.issn.1671-6841.2015.03.005