湯自凱, 侯耀平

?

譜半徑為4的整樹

湯自凱, 侯耀平

(湖南師范大學數(shù)學與計算機科學學院, 湖南長沙, 410081)

整圖刻畫的問題是學術(shù)屆公認的十分難的問題, 本文利用圖的特征多項式、譜與圖的直徑的關(guān)系等, 刻畫了譜半徑為4, 譜的所有整樹, 這樣的樹有且僅有18種。

樹; 整圖; 譜半徑

表1 譜半徑為4, 譜的所有整樹

表1 譜半徑為4, 譜的所有整樹

序號階D樹譜 1172(01)16±4, 015 23140(12)15±4, (±1)14, 00 35040(12222)814±4, (±2)8, ±1, 030 45660111(12222)8(12333)1(1232323)5±4, (±2)9, (±1)3, 030 56140(12222)12±4, (±2)11, 037 66260111(12222)6(1232323)4±4, (±2)9, (±1)9, 024 7626011(12222)7(12333)2 (1232323)2±4, (±2)10, (±1)5, 030 862601(12222)8(12333)4±4, (±2)11, ±1, 036 96860(12222)5(12333)(1232323)5±4, (±2)10, (±1)11, 024 1068601(12333)6(12333)3(1232323)3±4, (±2)11, (±1)7, 030 116860(12222)7(12333)5(1232323)±4, (±2)12, (±1)3, 036 1274601(2343434)3(1232323)8±4, (±2)10, (±1)17, 018 1374601(12222)4(12333)2(1232323)6±4, (±2)11, (±1)13, 024 147460(12222)5(12333)4(1232323)6±4, (±2)11, (±1)13, 024 1580601(12222)2(12333)(1232323)9±4, (±2)11, (±1)19, 018 168060(12222)3(12333)3(1232323)7±4, (±2)12, (±1)15, 024 1786601(2343434)12±4, (±2)11, (±1)25, 012 18866012222(12333)2(1232323)10±4, (±2)12, (±1)21, 018

1 引理

先給出所有譜半徑小于等2的整樹(表2)及圖譜的一些基本結(jié)論。

引理1[1]設(shè)是圖的特征值,是圖子圖的特征值。則。

引理2[1]設(shè)圖的不同特征值的個數(shù)為, 圖的直徑為, 則。

引理3[1]設(shè)是圖的譜半徑, 則: (1) 圖是連通圖當且僅當?shù)闹財?shù)為1; (2) 圖是二部圖當且僅當也是圖的特征值; (3)中的等號成立, 當且僅當圖是正則圖。

引理4[8]設(shè)為圖的譜半徑值, 則(), 當且僅當?shù)娜我环种荢mith圖或Smith圖的子圖。

引理5[9]設(shè)是連通圖的某割點, 若分支中至少有2個分支的譜半徑大于2或1個分支的譜半徑大于2, 其余分支的譜半徑等于2, 則。

引理6(Godsil引理)[8]設(shè)是樹,是重數(shù)為(> 1)的樹的譜,是樹中的一條路, 則是圖的譜, 且重數(shù)不小于。

表2 譜半徑小于等于2的整樹

2 譜半徑為4, 譜l1±3的整樹

通過計算機搜索滿足條件1,2,3,4,5的整數(shù)解只有3組, 即1= 0,2= 15,3= 0,4= 0,5= 0或1= 4,2= 0,3= 0,4= 0,5= 9或1= 0,2= 0,3= 0,4= 0,5= 12。當1= 0,2= 15,3= 0,4= 0,5= 0時,(表1中序號2); 當1= 4,2= 0,3= 0,4= 0,5= 9時,同構(gòu)于表1中序號3; 當1= 0,2= 0,3= 0,4= 0,5= 12時,同構(gòu)于表1中序號5。

表3 直徑為6, 譜半徑為4, 譜的部分整圖

表3 直徑為6, 譜半徑為4, 譜的部分整圖

(n1, n3, n4, n5)序號階D樹譜 (3, 6, 0, 4)66260111(12222)6(1232323)4±4, (±2)9, (±1)9, 024 (2, 7, 2, 2)7626011(12222)7(12333)2(1232323)2±4, (±2)10, (±1)5, 030 (1, 8, 4, 0)862601((12222)8(1232323)4±4, (±2)11, 1, 036 (2, 5, 1, 5)9686011(12222)5(12333)1(1232323)5±4, (±2)10, (±1)11, 024 (1, 6, 3, 3)1068601((12222)6(12333)3(1232323)3±4, (±2)11, (±1)7, 030 (0, 7, 5, 1)116860(12222)7(12333)5(1232323)±4, (±2)12, 13, 036 續(xù)表3 (2, 3, 0, 8)12746011(12222)3(1232323)8±4, (±2)10, (±1)17, 018 (1, 4, 2, 6)1374601(12222)4(12333)2(1232323)6±4, (±2)11, (±1)13, 024 (0, 5, 4, 4)147460(12222)5(12333)4(1232323)4±4, (±2)12, (±1)9, 030 (1, 2, 1, 9)1580601(12333)2(12333)(1232323)9±4, (±2)11, (±1)19, 018 (0, 3, 3, 7)168060(12222)3(12333)3(1232323)7±4, (±2)12, (±1)15, 024 (1, 0, 0, 12)1786601(2343434)12±4, (±2)11, (±1)25, 012 (0, 1, 2, 10)18866012222(12333)2(1232323)10±4, (±2)12, (±1)21, 018

表4 T - p的譜

參考文獻：

[1] Cvetkovic D, Doob M, Sachs H. Spectra of graphs: Theory and Application [M]. New York: Academic Press, 1995.

[2] Harary F, Schwenk A. Which graphs have integral spectra? [C]// Bari R, Harary F. Graphs and Combinatorics. Berlin: Springer-Verlag, 1974: 45–51.

[3] Bussemaker F, Cvetkovic D. There are exactly 13 connected cubic, integral graphs [J]. Univ Beograd Publ Elektrotehn Fak Ser Mat, 1976, 552: 43–48.

[4] Hagos E M. Some results on graph spectra [J]. Lin Alg Appl, 2002, 356: 103–111.

[5] Brouwer A E, Haemers W H. The integral trees with spectral radius 3 [J]. Lin Alg Appl, 2008, 429: 2 710–2 718.

[6] Tang Z K, Hou Y P. The integral graphs with index 3 and exactly two main eigenvalues [J]. Lin Alg Appl, 2010, 433: 984–993.

[7] Wang L G, Liu X D. Integral complete multipartite graphs [J]. Discrete Mathematics, 2008, 308: 3 860–3 870.

[8] Godsil C D. Spectra of trees [J]. Annals of Discrete Mathematics, 1984, 20: 151–159.

[9] Smith J H. Some properties of the spectrum of a graph [C]// Guy R, Hanani H, Sauer N, et al. Combinatorial Structures and Their Applications. New York: Gordon and Breach Science Publ, 1970: 403–406.

[10] Radosavljevic Z, Simic S. Which bicyclic graphs are reflexive? [J]. Univ Beograd Publ Elektrotehn Fak Ser Mat,1996, 7: 90–104.

(責任編校:劉曉霞)

The integral trees with index 4

Tang Zikai, Hou Yaoping

(College of Mathematics and Computer Science, Hunan Normal University, Changsha 410081, China)

Integral graphs are very difficult to be found. In this paper, bythe characteristic polynomials and the relations of spectrum and diameter of graph, all integral trees with index 4 and avoiding 3 in the spectral are determined, such trees have only 18 species.

trees; integral graph; spectral radius

10.3969/j.issn.1672–6146.2015.04.003

O 157

1672–6146(2015)04–0008–06

湯自凱, zikaitang@163.com。

2015–09–06

湖南師范大學優(yōu)秀青年項目(ET13101); 湖南省自然科學基金(12JJ6005)。