Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Small integral trees. | Small integral trees A. E. Brouwer Dept. of Math. Techn. Univ. Eindhoven . Box 513 5600MB Eindhoven Netherlands aeb@ Submitted Dec 31 2007 Accepted Jan 18 2008 Published Jan 28 2008 Mathematics Subject Classification 05C05 05C30 05E99 Abstract We give a table with all integral trees on at most 50 vertices and characterize integral trees with a single eigenvalue 0. 1 Integral trees A finite graph is called integral if the spectrum of its adjacency matrix has only integral eigenvalues. A tree is a connected undirected graph without cycles. In this note we give a table with all integral trees on at most 50 vertices and a further table with all known integral trees on at most 100 vertices. For an on-line version possibly with updates see 1 . In particular we find the smallest integral trees of diameter 6 and the smallest known integral tree of diameter 8. The nicest result about integral trees is that by Watanabe 12 that says that an integral tree different from K2 does not have a complete matching. Here we give a generalization. All starlike integral trees that is all integral trees with at most one vertex of degree larger than 2 were given by Watanabe and Schwenk 13 . All integral trees of diameter at most 3 were given in 13 4 . See also 10 3 . Several people have worked on constructing integral trees with large diameter and examples with diameters 0-8 and 10 are known see 13 9 3 8 6 7 . It is unknown whether integral trees can have arbitrarily large diameter. The spectral radius of a nonempty graph is the maximum absolute value of an eigenvalue. In 2 all integral trees with spectral radius at most 3 are determined. Names of general trees In the tables below we need a notation to name trees. Given a tree pick some vertex and call it the root. Now walk along the tree depth-first starting at the root and when a THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 N1 1 Figure 1 17 01233 1 23 3 2 124 21. vertex is encountered for the first time write down its .
