Vol. 5, No. 4, 2012

Download this article
Download this article For screen
For printing
Recent Issues

Volume 10
Issue 3, 361–539
Issue 2, 181–360
Issue 1, 1–180

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
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