Article
Orthogonal representations, minimum rank, and graph complements
Linear Algebra and its Applications
Document Type
Article
Disciplines
Publication Version
Submitted Manuscript
Publication Date
6-1-2008
DOI
10.1016/j.laa.2007.12.004
Abstract
Orthogonal representations are used to show that complements of certain sparse graphs have (positive semidefinite) minimum rank at most 4. This bound applies to the complement of a 2-tree and to the complement of a unicyclic graph. Hence for such graphs, the sum of the minimum rank of the graph and the minimum rank of its complement is at most two more than the order of the graph. The minimum rank of the complement of a 2-tree is determined exactly.
Rights
This manuscript version is made available under the CCBY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Owner
Elsevier Inc.
Copyright Date
2007
Language
en
File Format
application/pdf
Citation Information
Leslie Hogben. "Orthogonal representations, minimum rank, and graph complements" Linear Algebra and its Applications Vol. 426 (2008) Available at: http://works.bepress.com/leslie-hogben/56/
This is a manuscript of an article from Linear Algebra and its Applications 428 (2008); 2560, doi:10.1016/j.laa.2007.12.004. Posted with permission.