Nullspace vertex partition in graphs

DOI10.1007/S10878-020-00624-XzbMATH Open1473.05187arXiv2001.04710OpenAlexW3044242934MaRDI QIDQ2230734FDOQ2230734

Authors: Irene Sciriha, Xandru Mifsud, James L. Borg 

Publication date: 28 September 2021

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: The core vertex set of a graph is an invariant of the graph. It consists of those vertices associated with the non-zero entries of the nullspace vectors of a $0,1$-adjacency matrix. The remaining vertices of the graph form the core--forbidden vertex set. For graphs with independent core vertices, such as bipartite minimal configurations and trees, the nullspace induces a well defined three part vertex partition. The parts of this partition are the core vertex set, their neighbours and the remote core--forbidden vertices. The set of the remote core--forbidden vertices are those not adjacent to any core vertex. We show that this set can be removed, leaving the nullity unchanged. We show that for graphs with independent core vertices, the submatrix of the adjacency matrix defining the edges incident to the core vertices determines the nullity of adjacency matrix. To maximize the number of edges for optimal network graphs with a specified nullity, we determine which perturbations make up sufficient conditions for the core vertex set of the adjacency matrix of a graph to be preserved on adding edges.

Full work available at URL: https://arxiv.org/abs/2001.04710

Recommendations

• scientific article; zbMATH DE number 1866895
• scientific article; zbMATH DE number 2058456
• On the nullity of bipartite graphs
• On the nullity of bipartite graphs
• scientific article; zbMATH DE number 637295
• scientific article; zbMATH DE number 966836
• Publication:3469129
• Partitioning graphs into complete and empty graphs
• Partitions of Graphs
• scientific article; zbMATH DE number 524137

zbMATH Keywords

nullspacecore verticescore-labellinggraph perturbations

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• The second largest eigenvalue of a tree
• Trees with maximum nullity
• The least eigenvalue of signless Laplacian of graphs under perturbation
• Title not available (Why is that?)
• On the nullity of a graph with cut-points
• More on Graph Perturbations
• Combinatorial properties of the family of maximum stable sets of a graph
• A characterization of singular graphs
• On the construction of graphs of nullity one
• Title not available (Why is that?)
• Minimal configuration trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tree decomposition by eigenvectors
• Null decomposition of trees
• Coalesced and embedded nut graphs in singular graphs
• On the displacement of eigenvalues when removing a twin vertex

Cited In (2)

• Coalescing Fiedler and core vertices.
• \(\lambda\)-core distance partitions

This page was built for publication: Nullspace vertex partition in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2230734)