Complementarity eigenvalues and graph determination

Abstract

Determination of connected graphs is a fundamental theme of spectral graph theory. In this work, the task of separating a pair of connected graphs is done with the help of the spectral code function. The verb ''o separate is used here as a synonym of the verb to discriminate or to distinguish. By definition, the spectral code of a connected graph G is an eventually zero sequence Gamma(G) := (rho(1) (G); rho(2)(G); rho(3) (G). . .) whose kth term is the k-largest complementarity eigenvalue of the graph. The spectral code of a graph is a convenient vector representation of the so-called complementarity spectrum of the graph. The spectral code separation technique runs as follows: while comparing two connected graphs, say G and H, we start by considering rho(1), which is nothing but the spectral radius function; in case of equality rho(1) (G) = rho(1) (H), the second largest complementarity eigenvalue function rho(2) enters into action; in case of a new equality, we pass to rho(3), and so on. Complementarity eigenvalues perform more efficiently the separation role usually played by classical eigenvalues.