Induced Trees, Minimum Semidefinite Rank, and Zero Forcing

Authors

Rachel Cranfill
Lon Mitchell, University of South Florida St. PetersburgFollow
Sivaram Narayan
Taiji Tsutsui

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

Recommended Citation

Cranfill, R., Mitchell, L., Narayan, S. & Tsutsui, T. (2012) Induced trees, minimum semidefinite rank, and zero forcing. Involve, 5(4), 411-420. http://dx.doi.org/10.2140/involve.2012.5.411.