Signed graphs with maximum nullity two

Marina Arav, F. Scott Dahlgren, Hein van der Holst

Research output: Contribution to journalArticleScientificpeer-review

9 Downloads (Pure)

Abstract

A signed graph is a pair (G,Σ), where G=(V,E) is a graph (in which parallel edges are permitted, but loops are not) with V={1,…,n} and Σ⊆E. The edges in Σ are called odd and the other edges of E even. If there are parallel edges, then only two edges in each parallel class are permitted, one of which is even and one of which is odd. By S(G,Σ) we denote the set of all symmetric n×n matrices A=[ai,j] with ai,j<0 if i and j are connected by an even edge, ai,j>0 if i and j are connected by an odd edge, ai,j∈R if i and j are connected by both an even and an odd edge, ai,j=0 if i≠j and i and j are non-adjacent, and ai,i∈R for all vertices i. The maximum nullity M(G,Σ) of a signed graph (G,Σ) is the maximum nullity attained by any A∈S(G,Σ). Arav et al. gave a combinatorial characterization of 2-connected signed graphs (G,Σ) with M(G,Σ)=2. In this paper, we give a complete combinatorial characterization of the signed graphs (G,Σ) with M(G,Σ)=2.

Original languageEnglish
Pages (from-to)29-47
Number of pages19
JournalLinear Algebra and Its Applications
Volume675
DOIs
Publication statusPublished - 2023

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

  • Nullity
  • Signed graph
  • Symmetric

Fingerprint

Dive into the research topics of 'Signed graphs with maximum nullity two'. Together they form a unique fingerprint.

Cite this