A Generalization of the Characteristic Polynomial of a Graph
Lipton, Richard J.
Vishnoi, Nisheeth Kumar
Zalcstein, Yechezkel (Zeke)
MetadataShow full item record
Given a graph G with its adjacency matrix A, consider the matrix A(x, y) in which the 1s are replaced by the indeter0minate x and 0s (other than the diagonals) are replaced by y. The ℒ-polynomial of G is defined as: ℒ[subscriptG](x, y, λ) := det(A(x, y) λI). This polynomial is a natural generalization of the standard characteristic polynomial of a graph. In this note we characterize graphs which have the same ℒ-polynomial. The answer is rather simple: Two graphs G and H have the same ℒ-polynomial if and only if - G and H are co-spectral and G[subscript c] and H[subscript c] are co-spectral. (Here G[subscript c] (resp. H[subscript c]) is the complement of G (resp. H).)