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?
1
-
3$\begingroup$ Wikipedia asserts that almost all trees are isospectral (en.wikipedia.org/wiki/Spectral_graph_theory#Isospectral_graphs). $\endgroup$– Qiaochu YuanCommented Aug 23, 2013 at 5:47
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
-
1$\begingroup$ 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. $\endgroup$ Commented Aug 23, 2013 at 11:50
-
$\begingroup$
$\endgroup$
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
answered Aug 23, 2013 at 7:10