Idiosyncratic Polynomial

The idiosyncratic polynomial is the bivariate graph polynomial defined as the characteristic polynomial in  of , where  is the adjacency matrix,  is the unit matrix, and  is the identity matrix.

Nonisomorphic graphs do not necessarily have distinct idiosyncratic polynomials. For example, the Harries graph and Harries-Wong graph share the same polynomial. The smallest nonisomorphic graphs sharing an idiosyncratic polynomial occur for graphs on seven vertices.

The idiosyncratic polynomial is not multiplicative with respect to graph disjoint unions.

REFERENCES

Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications II: Interrelations and Interpretations." 28 Jun 2008.

 http://arxiv.org/abs/0806.4699.Tutte, W. T. "All the King's Horses." In Graph Theory and Related Topics (Ed. J. A. Bondy and U. R. S. Murty). New York: Academic Press, pp. 15-33, 1979.

van Dam, E. R. "Cospectral Graphs and the Generalized Adjacency Matrix." Linear Alg. Appl. 423, 33-41, 2007.