Vol. 8, No. 1, 2015

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

Volume 11
Issue 2, 181–359
Issue 1, 1–179

Volume 10, 5 issues

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
About the Journal
Subscriptions
Editorial Board
Editors’ Addresses
Editors’ Interests
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
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 (u,v) or (v,u) to replace each edge {u,v}. 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 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
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