## A Generalization of the Characteristic Polynomial of a Graph

##### View/Open

##### Date

2003##### Author

Lipton, Richard J.

Vishnoi, Nisheeth Kumar

Zalcstein, Yechezkel (Zeke)

##### Metadata

Show full item record##### Abstract

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).)