Techniques for determining the minimum rank of a small graph

Date
2010-06-01
Authors
DeLoss, Laura
Grout, Jason
Hogben, Leslie
Hogben, Leslie
McKay, Tracy
Smith, Jason
Tims, Geoff
Journal Title
Journal ISSN
Volume Title
Publisher
Source URI
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Abstract

The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. Minimum rank is a difficult parameter to compute. However, there are now a number of known reduction techniques and bounds that can be programmed on a computer; we have developed a program using the open-source mathematics software Sage to implement several techniques. We have also established several additional strategies for computation of minimum rank. These techniques have been used to determine the minimum ranks of all graphs of order 7.

Description
<p>This is a manuscript of an article from <em>Linear Algebra and its Applications </em>432 (2010): 2995, doi:<a href="http://dx.doi.org/10.1016/j.laa.2010.01.008" target="_blank">10.1016/j.laa.2010.01.008</a>. Posted with permission.</p>
Keywords
Minimum rank, Maximum nullity, Mathematical software, Symmetric matrix
Citation
Collections