On the minimum semidefinite rank of signed graphs

Nancy Matar, Lon H. Mitchell, Sivaram K. Narayan

Research output: Contribution to journalArticlepeer-review

Abstract

The (real) minimum semidefinite rank of a signed graph is the minimum rank among all real symmetric positive semidefinite matrices associated to the graph and having the given sign pattern. We give a new lower bound for the minimum semidefinite rank of a signed multigraph and show it equals a new upper bound for signed complete multigraphs. This allows a complete characterization of signed multigraphs with minimum semidefinite rank two. We also determine the minimum semidefinite rank of all signed wheel graphs.

Original languageEnglish
Pages (from-to)73-85
Number of pages13
JournalLinear Algebra and Its Applications
Volume642
DOIs
StatePublished - Jun 1 2022

Keywords

  • Complete signed multigraphs
  • Minimum semidefinite rank
  • Signed graphs

Fingerprint

Dive into the research topics of 'On the minimum semidefinite rank of signed graphs'. Together they form a unique fingerprint.

Cite this