Faculty Publications

Title

Induced Trees, Minimum Semidefinite Rank, and Zero Forcing

SelectedWorks Author Profiles:

Lon Mitchell

Document Type

Article

Publication Date

2012

ISSN

1944-4184 (online-only) 1944-4176 (print)

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.

Publisher

Mathematical Sciences Publishers

Share

COinS