Complementarity eigenvalue analysis of connected graphs

This work concerns the spectral analysis of connected graphs from a non-traditional point of view. Instead of the usual eigenvalues of the adjacency matrix AG of a graph G under consideration, we compute and analyze the complementarity eigenvalues of AG. The complementarity eigenvalues of a general square matrix are defined in terms of a certain complementarity system relative to the componentwise ordering. The complementarity eigenvalues of AG form the so-called complementarity spectrum of G. In general, the structure of a connected graph is better discriminated in terms of its complementarity spectrum than in terms of its usual spectrum. This observation is one of the leading motivation behind our work.