Interlacing–extremal graphs

Irene Sciriha, Mark Debono, Martha Borg, Patrick W. Fowler, Barry T. Pickup


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.


adjacency matrix, singular graphs, nut graphs, uniform core graphs, interlacing.

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications