|
|||||
 |
|
|
|
|
|
Induced trees,
minimum semidefinite rank, and zero forcing
Rachel Cranfill, Lon H. Mitchell, Sivaram K. Narayan and Taiji Tsutsui
Vol. 5 (2012), No. 4, 411–420
|
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. |
Keywords
minimum semidefinite rank
|
Mathematical Subject Classification 2010
Primary: 05C50, 15A18, 15B48
|
Milestones
Received: 20 May 2011
Revised: 12 June 2012
Accepted: 13 June 2012
Published: 14 June 2013
Communicated by Chi-Kwong Li
|
Authors |
| Rachel Cranfill | |
| Department of Mathematics Harvey Mudd College Claremont, CA 91771 United States |
|
| Lon H. Mitchell | |
| Department of Mathematics Virginia Commonwealth University Richmond, VA 23284-2014 United States |
|
| Sivaram K. Narayan | |
| Department of Mathematics Central Michigan University Mount Pleasant, MI 48859 United States |
|
| Taiji Tsutsui | |
| Department of Mathematics Hiram College Hiram, OH 44234 United States |
|
|
