Induced Trees, Minimum Semidefinite Rank, and Zero Forcing
1944-4184 (online-only) 1944-4176 (print)
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.
Mathematical Sciences Publishers
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.