zbMATH — the first resource for mathematics

Maximal core size in singular graphs. (English) Zbl 1190.05084
Summary: A graph \(G\) is singular of nullity \(\eta \) if the nullspace of its adjacency matrix \(G\) has dimension \(\eta \). Such a graph contains \(\eta \) 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 \(\eta \) 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.

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
Full Text: DOI