谱半径为4的整树

汤自凯, 侯耀平



谱半径为4的整树

汤自凯, 侯耀平

(湖南师范大学数学与计算机科学学院, 湖南长沙, 410081)

整图刻画的问题是学术届公认的十分难的问题, 本文利用图的特征多项式、谱与图的直径的关系等, 刻画了谱半径为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)及图谱的一些基本结论。

引理1[1]设是图的特征值,是图子图的特征值。则。

引理2[1]设图的不同特征值的个数为, 图的直径为, 则。

引理3[1]设是图的谱半径, 则: (1) 图是连通图当且仅当的重数为1; (2) 图是二部图当且仅当也是图的特征值; (3)中的等号成立, 当且仅当图是正则图。

引理4[8]设为图的谱半径值, 则(), 当且仅当的任一分支是Smith图或Smith图的子图。

引理5[9]设是连通图的某割点, 若分支中至少有2个分支的谱半径大于2或1个分支的谱半径大于2, 其余分支的谱半径等于2, 则。

引理6(Godsil引理)[8]设是树,是重数为(> 1)的树的谱,是树中的一条路, 则是图的谱, 且重数不小于。

表2 谱半径小于等于2的整树

2 谱半径为4, 谱l¹±3的整树

通过计算机搜索满足条件1,2,3,4,5的整数解只有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时,同构于表1中序号3; 当1= 0,2= 0,3= 0,4= 0,5= 12时,同构于表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 续表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

湖南师范大学优秀青年项目(ET13101); 湖南省自然科学基金(12JJ6005)。