|
|||||
 |
|
|
|
|
|
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 or to replace each edge . 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 , for various orientations and for the doubly directed digraph of , 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
|
Milestones
Received: 31 December 2013
Accepted: 30 April 2014
Published: 10 December 2014
Communicated by Chi-Kwong Li
|
Authors |
| Adam Berliner | |
| Department of Mathematics,
Statistics, and Computer Science St. Olaf College Northfield, MN 55057 United States |
|
| Cora Brown | |
| Department of Mathematics Carleton College Northfield, MN 55057 United States |
|
| Joshua Carlson | |
| Department of Mathematics Iowa State University Ames, IA 50011 United States |
|
| Nathanael Cox | |
| Department of Mathematics,
Statistics, and Computer Science St. Olaf College Northfield, MN 55057 United States |
|
| Leslie Hogben | |
| Department of Mathematics Iowa State University Ames, IA 50011 and American Institute of Mathematics 600 East Brokaw Road San Jose, CA 95112 United States |
|
| Jason Hu | |
| Department of Mathematics University of California, Berkeley Berkeley, CA 94720 United States |
|
| Katrina Jacobs | |
| Department of Mathematics Pomona College 610 North College Avenue Claremont, CA 91711 United States |
|
| Kathryn Manternach | |
| Department of Mathematics and
Computer Science Central College Pella, IA 50219 United States |
|
| Travis Peters | |
| Natural and Mathematical Science
Division Culver-Stockton College Canton, MO 63435 United States |
|
| Nathan Warnberg | |
| Department of Mathematics Iowa State University Ames, IA 50011 United States |
|
| Michael Young | |
| Department of Mathematics Iowa State University Ames, IA 50011 United States |
|
|
