zbMATH — the first resource for mathematics

Balanced integral trees. (English) Zbl 0958.05025
A graph \(G\) is called integral if all the zeros of its characteristic polynomial \(P(G,\lambda)\) are integers. A tree \(T\) is said to be balanced if all vertices of the same distance from the centre \(Z(T)\) of \(T\) are of the same degree. The authors give a survey of known results and present some new results on balanced integral trees. They prove that there are infinitely many balanced integral trees of diameter \(8\), however there is no balanced integral tree of diameter \(7\) and \(4k+1\) for \(k\geq 1\).

05C05 Trees
Full Text: EuDML
[1] BUSSEMAKER F. C.-CVETKOVIC D.: There are exactly 13 connected cubic integral graphs. Publ. Elektrotech. Fak. Ser. Mat. Fiz. 544 (1976), 43-48. · Zbl 0357.05064
[2] CVETKOVIC D.-DOOB M.-SACHS H.: Spectra of Graphs. VEB Deutscher Verlag d. Wiss, Berlin, 1980. · Zbl 0458.05042
[3] HARARY F.: Graph Theory. Addison-Wesley, Reading Mass., 1969. · Zbl 0196.27202
[4] HARARY F.-SCHWENK A. J.: Which graphs have integral spectra?. Graphs and Combinatorics. Lecture Notes in Math. 406, Springer-Verlag, Berlin, 1974, pp. 45-51.
[5] HARARY F.: Four difficult unsolved problems in graph theory. Recent Advances in Graph Theory, Academia, Praha, 1975, pp. 253-255. · Zbl 0329.05125
[6] HIC P.-NEDELA R.-PAVLIKOVA S.: Front divisor of trees. Acta Math. Univ. Comenian. LXI (1992), 69-84.
[7] HIC P.-NEDELA R.: Note on zeros of the characteristic polynomial of balanced integral trees. Acta Univ. Mathaei Belii Ser. Math. 3 (1995), 31-35. · Zbl 0861.05044
[8] LI X. L.-LIN G. N.: On integral trees problems. Kexue Tongbao (Chinese) 33 (1988), 802-806. · Zbl 0677.05057
[9] LIU R. Y.: Integral trees of diameter 5. J. Systems Sci. Math. Sci. 8 (1988), 357-360. · Zbl 0695.05016
[10] SCHWENK J. A.: Computing the characteristic polynomial of a graphs. Graphs and Combinatorics. Lecture notes in Math. 406, Springer-Verlag, Berlin, 1974, pp. 247-251.
[11] SCHWENK A. J.: Exactly thirteen connected cubic graphs have integral spectra. Notes in Math. Ser. A 642, Springer-Verlag, Berlin, 1978, pp. 516-533. · Zbl 0376.05050
[12] SCHWENK A. J.-WATANABE M.: Integral starlike trees. J. Austral. Math. Soc. Ser. A 28 (1979), 120-128. · Zbl 0428.05021
[13] WATANABE M.: Note on integral trees. Math. Rep. Toyama Univ. 2 (1979), 95-100. · Zbl 0432.05019
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.