zbMATH — the first resource for mathematics

Almost all trees share a complete set of immanantal polynomials. (English) Zbl 0782.05038
If \(\chi\) is an irreducible character of the symmetric group \(S_ n\) and \(A=(a_{ij})\) is an \((n,n)\)-matrix, then \(d_ \chi=\sum_{p\in S_ n}\chi(p) \prod^ n_{i=1} a_{ip(i)}\). If \(G_ 1\) and \(G_ 2\) are isomorphic graphs they share a complete set of immanantal polynomials, i.e., \(d_ \chi(xI-A(G_ 1))= d_ \chi(xI-A(G_ 2))\) for all \(\chi\). Let \(y\) and \(z\) be independent indeterminants over the complex numbers. Define \(L(G)= yD(G)+ zA(G)\), where \(D(G)\) is the diagonal matrix of the vertex degrees and \(A(G)\) is the adjacency matrix of a graph \(G\). The main result is the following theorem:
Let \(t_ n\) be the number of nonisomorphic trees on \(n\) vertices and \(s_ n\) the number of such trees \(T\) for which there exists a nonisomorphic tree \(\widetilde T\) such that the polynomial identities \(d_ \chi(xI- L(T))= d_ \chi(xI- L(\widetilde T))\), in the three variables \(x\), \(y\), and \(z\), hold, simultaneously, for every irreducible character \(\chi\) of \(s_ n\). Then \(\lim_{n\to\infty} {s_ n\over t_ n}= 1\).

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C05 Trees
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI
[1] , and , Spectra of Graphs. Academic Press, New York (1979).
[2] McKay, Ars Combinat. 3 pp 219– (1977)
[3] Almost all trees are cospectral. New Directions in the Theory of Graphs. Academic Press, New York (1973) 275–307.
[4] Turner, SIAM J. Appl. Math. 16 pp 520– (1968)
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.