P. Botti and R. Merris, Almost all trees share a complete set of immanantal polynomials, J. Graph Theory 17 (1993), 467-476. Research supported by the National Security Agency under grant no. MDA904-90-H-4024. Math Reviews 95d:05085. Math Reviews 94g:05053.

Suppose G is a graph on n vertices. Let D(G) = diag(d1,d2, ... ,dn) be the diagonal matrix of its vertex degrees and A(G) be its adjacency matrix. Let y and z be independent indeterminants and define L(G) = yD(G) + zA(G). (Setting y = 1 and z = -1 produces the Laplacian matrix.)

If c is an irreducible character of the symmetric group of degree n, denote the corresponding immanant by d_c. (When c = 1, the identically 1 character, d_c = permanent. When c = epsilon, the alternating character, d_c = determinant.)

The main result of the article is that for "almost all" trees T, there is a nonisomorphic tree T' such that T and T' are coimmanantal, meaning that the polynomial identities

d_c(xI-L(T)) = d_c(xI-L(T')),

in the three variables x, y, and z hold, simultaneously, for every irreducible character c of the symmetric group of degree n.

The authors are unaware of a single example of a 2-connected graph G for which there is a nonisomorphic graph G' such that per(xI-L(G)) = per(xI-L(G')) even for the specialization y = 1 & z = -1.

Among the publications citing this article are:

  • L. Halbeisen and N. Hungerbuhler, J. Graph Theory 31 (1999), 255-265.
  • O. Chan and T. K. Lam, SIAM J. Matrix Anal. Appl. 21 (1999), 129-144.
  • L. Halbeisen and N. Hungerbuhler, European J. Combinatorics 21 (2000), 641-650.
  • M. Diudea, I. Gutman, and J. Lorentz, Molecular Topology, Nova Science Publishers, 2001 [p. 82].
  • I. Gutman and G. G. Cash, MATCH-Comm. Math. & Comput. Chem. 45 (2002), 55-70.
  • E. R. van Dam and W. H. Haemers, Linear Algebra Appl. 373 (2003), 241-272.
  • G. G. Cash, J. Chem. Inf. & Comp. Sci. 43 (2003), 1942-1946.