Isospectral Multigraphs

FIGURE 3.4 The smallest isospectral multigraphs having from six to eight vertices. 

The answer to this question is hitherto unknown although it will not be surprising that there are isospectral multi-trees that for A = 1 do not reduce to the same graph. 

In Table 3.2, we show the coefficients of the 15 characteristic polynomials of all mnltigraphs for n = 6, expressed in terms of the path polynomial L Lg + C4L4 + C2L2 + CoLq. As one can see from Table 3.2, the coefficient C4 for all mnlti-trees having n = 6 vertices is equal (1 - k). This means that all isospectral multi-trees must have the same k, the same multiplicity of the edge. The path polynomials L appear very suitable for computations of the characteristic polynomials of graphs, and it is useful to have coefficients of x powers expanded in L . In Table 3.3 at left, we show the coefficients of polynomials when the x powers are expanded in L . 

The Coefficients of Characteristic Polynomials in Chebyshev Expansion for Isomers of Hexene 

Truncated Pascal Triangle Giving the Coefficients in Expansion of x in Terms of L  

---