Induced trees, minimum semidefinite rank, and zero forcing

Rachel Cranfill, Lon H. Mitchell, Sivaram K. Narayan, Taiji Tsutsui

Research output: Contribution to journalArticlepeer-review

Abstract

We prove that the ordered subgraph number of a connected graph that has no duplicate vertices is at most three if and only if the complement does not contain a cycle on four vertices. The duality between zero forcing and ordered subgraphs then provides a complementary characterization for positive semidefinite zero forcing. We also provide some necessary conditions for when the minimum semidefinite rank can be computed using tree size.

Original languageEnglish
Pages (from-to)411-420
Number of pages10
JournalInvolve
Volume5
Issue number4
DOIs
StatePublished - 2012

Keywords

  • minimum semidefinite rank

Fingerprint

Dive into the research topics of 'Induced trees, minimum semidefinite rank, and zero forcing'. Together they form a unique fingerprint.

Cite this