Interlacing - extremal graphs

Abstract

A graph G is singular if the zero-one adjacency matrix has the eigenvalue zero. The multiplicity of the eigenvalue zero is called the nullity of G. For two vertices y and z of G, we call (G, y, z) a device with respect to y and z. The nullities of G, G − y, G − z and G − y − z classify devices into different kinds. We identify two particular classes of graphs that correspond to distinct kinds. In the first, the devices have the minimum allowed value for the nullity of G − y − z relative to that of G for all pairs of distinct vertices y and z of G. In the second, the nullity of G − y reaches the maximum possible for all vertices y in a graph G. We focus on the non–singular devices of the second kind.