Skip to main content
Article
Path cover number, maximum nullity, and zero forcing number of oriented graphs and other simple digraphs
Involve
  • Adam Berliner, Saint Olaf College
  • Cora Brown, Carleton College
  • Joshua Carlson, Iowa State University
  • Nathanael Cox, Saint Olaf College
  • Leslie Hogben, Iowa State University
  • Jason Hu, University of California, Berkeley
  • Katrina Jacobs, Pomona College
  • Kathryn Manternach, Central College
  • Travis Peters, Culver-Stockton College
  • Nathan Warnberg, Iowa State University
  • Michael Young, Iowa State University
Document Type
Article
Publication Version
Published Version
Publication Date
1-1-2015
DOI
10.2140/involve.2015.8.147
Abstract

An oriented graph is a simple digraph obtained from a simple graph by choosing exactly one of the two arcs (u,v)(u,v) or (v,u)(v,u) to replace each edge {u,v}{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 GG, for various orientations G→G→ and for the doubly directed digraph of GG, and establish an upper bound on the number of arcs in a simple digraph in terms of the zero forcing number.

Comments

This is an article from Involve 8 (2015): 147, doi:10.2140/involve.2015.8.147. Posted with permission.

Copyright Owner
The Authors
Language
en
File Format
application/pdf
Citation Information
Adam Berliner, Cora Brown, Joshua Carlson, Nathanael Cox, et al.. "Path cover number, maximum nullity, and zero forcing number of oriented graphs and other simple digraphs" Involve Vol. 8 (2015)
Available at: http://works.bepress.com/leslie-hogben/61/