Campus Units

Mathematics

Document Type

Article

Publication Version

Published Version

Publication Date

6-2014

Journal or Book Title

Electronic Journal of Linear Algebra

Volume

27

First Page

458

Last Page

477

DOI

10.13001/1081-3810.1630

Abstract

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 mr0(G) = vertical bar G vertical bar if and only if it has a unique spanning generalized cycle (also called a perfect vertical bar 1,2 vertical bar-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.

Comments

This article is published as Grood, Cheryl, Johannes Harmse, Leslie Hogben, Thomas Hunter, Bonnie Jacob, Andrew Klimas, and Sharon McCathern. "Minimum rank with zero diagonal." The Electronic Journal of Linear Algebra 27 (2014): 458-477. DOI: 10.13001/1081-3810.1630. Posted with permission.

Copyright Owner

The Author(s)

Language

en

File Format

application/pdf

Included in

Algebra Commons

Share

COinS