Maximal core size in singular graphs
Abstract
A graph G is singular of nullity η if the nullspace of its adjacency matrix G has dimension η. Such a graph contains η cores determined by a basis for the nullspace of G. These are induced subgraphs of singular configurations, the latter occurring as induced subgraphs of G. We show that there exists a set of η distinct vertices representing the singular configurations. We also explore how the nullity controls the size of the singular substructures and characterize those graphs of maximal nullity containing a substructure reaching maximal size.
Keywords
adjacency matrix, singular graphs, nullity, extremal singular graphs, singular congurations, core width
DOI: https://doi.org/10.26493/1855-3974.115.891
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