Minimum rank with zero diagonal
Cheryl Grood, Johannes Harmse, Leslie Hogben, Thomas P. Hunter, Bonnie C. Jacob, Andrew J. Klimas, Sharon McCathern · Electronic Journal of Linear Algebra · 2014
Associated with a simple graph G is a family of real, symmetric zero diagonal matrices with the same nonzero pattern as the adjacency matrix of G.The minimum of the ranks of the matrices in this family is denoted mr 0 (G).We characterize all connected graphs G with extreme minimum zero-diagonal rank: a connected graph G has mr 0 (G) ≤ 3 if and only if it is a complete multipartite graph, and mr 0 (G) = |G| if and only if it has a unique spanning generalized cycle (also called a perfect [1, 2]-factor).We present an algorithm for determining whether a graph has a unique spanning generalized cycle.In addition, we determine maximum zero-diagonal rank and show that for some graphs, not all ranks between minimum and maximum zero-diagonal ranks are allowed.