Nullspace vertex partition in graphs

Irene Sciriha (), Xandru Mifsud () and James L. Borg ()
Additional contact information
Irene Sciriha: University of Malta
Xandru Mifsud: University of Malta
James L. Borg: University of Malta

Journal of Combinatorial Optimization, 2021, vol. 42, issue 2, No 6, 310-326

Abstract: 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\}$$ { 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. For graphs with independent core vertices, we show that the submatrix of the adjacency matrix defining the edges incident to the core vertices determines the nullity of the adjacency matrix. For the efficient allocation of edges in a network graph without altering the nullity of its adjacency matrix, we determine which perturbations make up sufficient conditions for the core vertex set of the adjacency matrix of a graph to be preserved in the process.

Keywords: Nullspace; Core vertices; Core-labelling; Graph perturbations; 05C50; 15A18 (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00624-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:42:y:2021:i:2:d:10.1007_s10878-020-00624-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00624-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().