Nullspace vertex partition in graphs

DOI10.1007/S10878-020-00624-XMaRDI QIDQ2230734zbMATH OpenOpenAlexFDO

Authors Irene Sciriha, Xandru Mifsud, James L. Borg

Publication date 28 September 2021

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3783047 (Why is no real title available?)
• scientific article; zbMATH DE number 1123800 (Why is no real title available?)
• scientific article; zbMATH DE number 798644 (Why is no real title available?)
• scientific article; zbMATH DE number 3414355 (Why is no real title available?)
• A characterization of singular graphs
• Coalesced and embedded nut graphs in singular graphs
• Combinatorial properties of the family of maximum stable sets of a graph
• Minimal configuration trees
• More on Graph Perturbations
• Null decomposition of trees
• On the construction of graphs of nullity one
• On the displacement of eigenvalues when removing a twin vertex
• On the nullity of a graph with cut-points
• The least eigenvalue of signless Laplacian of graphs under perturbation
• The second largest eigenvalue of a tree
• Tree decomposition by eigenvectors
• Trees with maximum nullity

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)