Integral trees of arbitrarily large diameters. (English) Zbl 1221.05045
Summary: In this paper, we construct trees having only integer eigenvalues with arbitrarily large diameters. In fact, we prove that for every finite set \(S\) of positive integers there exists a tree whose positive eigenvalues are exactly the elements of \(S\). If the set \(S\) is different from the set {1} then the constructed tree will have diameter \(2|S|\).
MSC:
| 05C05 | Trees |
| 05C12 | Distance in graphs |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
References:
| [1] | Brouwer, A.E.: http://www.win.tue.nl/ aeb/graphs/integraltrees.html |
| [2] | Brouwer, A.E.: Small integral trees. Electron. J. Comb. 15 (2008) · Zbl 1158.05314 |
| [3] | Brouwer, A.E., Haemers, W.H.: The integral trees with spectral radius 3. Linear Algebra Appl. 429, 2710-2718 (2008) · Zbl 1152.05042 · doi:10.1016/j.laa.2008.02.009 |
| [4] | Cao, Z.F.: Integral trees of diameter R (3≤R≤6). Heilongjiang Daxue Ziran Kexue Xuebao 95(2), 1-3 (1988) · Zbl 0979.11502 |
| [5] | Cao, Z.F.: Some new classes of integral trees with diameter 5 or 6. J. Syst. Sci. Math. Sci. 11, 20-26 (1991) · Zbl 0731.05012 |
| [6] | Csikvári, P.: Short note on the integrality of some trees. http://www.cs.elte.hu/ csiki · Zbl 1224.05093 |
| [7] | Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics. Springer, Berlin (2001), pp. 186 · Zbl 0968.05002 |
| [8] | Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. A Foundation for Computer Science, 2nd edn. Addison-Wesley, Reading (1994) · Zbl 0836.00001 |
| [9] | Harary, F.; Schwenk, A. J., Which graphs have integral spectra?, No. 406, 45-51 (1974), Berlin · Zbl 0305.05125 · doi:10.1007/BFb0066434 |
| [10] | Wang, L.G., Li, X.L.: Some new classes of integral trees with diameters 4 and 6. Australas. J. Comb. 21, 237-243 (2000) · Zbl 0958.05023 |
| [11] | Wang, L.G., Li, X.L.: Integral trees with diameters 4, 6 and 8. Australas. J. Comb. 25, 29-44 (2002) · Zbl 0997.05027 |
| [12] | Yuan, P.Z.: Integral trees of diameter 4. J. Syst. Sci. Math. Sci. 18(2), 177-181 (1998) · Zbl 0904.05024 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
