湯自凱, 侯耀平

?

譜半徑為4的整樹

湯自凱, 侯耀平

(湖南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 湖南長(zhǎng)沙, 410081)

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

樹; 整圖; 譜半徑

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

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

序號(hào)階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è)圖的不同特征值的個(gè)數(shù)為, 圖的直徑為, 則。

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

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

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

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

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

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

通過(guò)計(jì)算機(jī)搜索滿足條件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。當(dāng)1= 0,2= 15,3= 0,4= 0,5= 0時(shí),(表1中序號(hào)2); 當(dāng)1= 4,2= 0,3= 0,4= 0,5= 9時(shí),同構(gòu)于表1中序號(hào)3; 當(dāng)1= 0,2= 0,3= 0,4= 0,5= 12時(shí),同構(gòu)于表1中序號(hào)5。

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

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

(n1, n3, n4, n5)序號(hào)階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的譜

參考文獻(xiàn)：

[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.

(責(zé)任編校:劉曉霞)

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

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