Vol. 8, No. 1, 2015

 Recent Issues
 The Journal About the Journal Editorial Board Editors’ Interests Subscriptions Submission Guidelines Submission Form Policies for Authors Ethics Statement ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
Path cover number, maximum nullity, and zero forcing number of oriented graphs and other simple digraphs

Adam Berliner, Cora Brown, Joshua Carlson, Nathanael Cox, Leslie Hogben, Jason Hu, Katrina Jacobs, Kathryn Manternach, Travis Peters, Nathan Warnberg and Michael Young

Vol. 8 (2015), No. 1, 147–167
Abstract

An oriented graph is a simple digraph obtained from a simple graph by choosing exactly one of the two arcs $\left(u,v\right)$ or $\left(v,u\right)$ to replace each edge $\left\{u,v\right\}$. A simple digraph describes the zero-nonzero pattern of off-diagonal entries of a family of (not necessarily symmetric) matrices. The minimum rank of a simple digraph is the minimum rank of this family of matrices; maximum nullity is defined analogously. The simple digraph zero forcing number and path cover number are related parameters. We establish bounds on the range of possible values of all these parameters for oriented graphs, establish connections between the values of these parameters for a simple graph $G$, for various orientations $\stackrel{\to }{G}$ and for the doubly directed digraph of $G$, and establish an upper bound on the number of arcs in a simple digraph in terms of the zero forcing number.

Keywords
zero forcing number, maximum nullity, minimum rank, path cover number, simple digraph, oriented graph
Mathematical Subject Classification 2010
Primary: 05C50, 05C20, 15A03