Three-connected graphs whose maximum nullity is at most three

H. Holst, van der

Research output: Contribution to journalArticleAcademicpeer-review

14 Citations (Scopus)

Abstract

For a graph G=(V,E) with vertex-set V={1,2,…,n}, let be the set of all n×n real-valued symmetric matrices A which represent G. The maximum nullity of a graph G, denoted by M(G), is the largest possible nullity of any matrix . Fiedler showed that a graph G has M(G)1 if and only if G is a path. Johnson et al. gave a characterization of all graphs G with M(G)2. Independently, Hogben and van der Holst gave a characterization of all 2-connected graphs with M(G)2. In this paper, we show that k-connected graphs G have M(G)k, that k-connected partial k-graphs G have M(G)=k, and that for 3-connected graphs G, M(G)3 if and only if G is a partial 3-path.
Original languageEnglish
Pages (from-to)625-632
JournalLinear Algebra and Its Applications
Volume429
Issue number2-3
DOIs
Publication statusPublished - 2008

Fingerprint

Dive into the research topics of 'Three-connected graphs whose maximum nullity is at most three'. Together they form a unique fingerprint.

Cite this