Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Are trees (connected acyclic graphs) determinable up to isomorphism by their spectra or characteristic polynomials? If not, what other pieces of information may help determine the tree?

share|improve this question
3  
Wikipedia asserts that almost all trees are isospectral (en.wikipedia.org/wiki/Spectral_graph_theory#Isospectral_graphs). –  Qiaochu Yuan Aug 23 '13 at 5:47
add comment

2 Answers 2

Any tree is uniquely defined by the distances (the length of the shortest chain) between its leaves (vertices of degree 1); see:

Smolenskii Ye. A. A method for the linear recording of graphs Zh. Vychisl. Mat. Mat. Fiz., 2:2 (1962), pp.371–372.

http://www.mathnet.ru/php/person.phtml?&personid=26482&option_lang=eng

http://www.zentralblatt-math.org/zmath/en/advanced/?q=an:03207296&type=pdf&format=complete

K. A. Zaretskii, Constructing a tree on the basis of a set of distances between the hanging vertices”. Uspekhi Mat. Nauk, 20:6(126) (1965), pp. 90–92 (Russian).

http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=6134&option_lang=eng http://www.zentralblatt-math.org/zmath/search/?an=Zbl%200151.33302

share|improve this answer
add comment

Brendan McKay showed that there are many pairs of non-isomorphic trees with identical characteristic polynomials, as well as several other algebraic invariants. See Thm 4.2 in the linked paper.

share|improve this answer
1  
Schenk showed in 1973 that there were infinitely many pairs of non-isomorphic trees (reference in McKay's paper). He showed that the probability that a tree on $n$ vertices is determined by its spectrum goes to zero as $n$ goes to infinity. –  Chris Godsil Aug 23 '13 at 11:50
    
Err, Schwenk showed... –  Chris Godsil Aug 23 '13 at 14:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.