Program for calculating bounds on the minimum rank of a graph using Sage

Abstract

The minimum rank of a simple graph $G$ is defined to be the smallest possible rank over all symmetric real matrices whose $ij$th entry (for $i\ne 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. In this note, we provide the source code for this program.

30 pages, 1 Sage program