Haemers' Minimum Rank
Is Version Of
Haemers' minimum rank was first defined by Willem Haemers in 1979. He created this graph parameter as an upper bound for the Shannon capacity of a graph, and to answer some questions asked by Lovasz in his famous paper where he determined the Shannon capacity of a 5-cycle.
In this thesis, new techniques are introduced that may be helpful for calculating Haemers' minimum rank for some graphs. These techniques are used to show the Haemers minimum rank is equal to the vertex clique cover number of a graph G for all graphs of order 10 or less, and also for some graph families, including all graphs with vertex clique cover number equal to 1, 2, 3, |G| - 2, |G| - 1, or |G|. Also, in the case of the cut-vertex reduction formula for Haemers' minimum rank, we show how this can be used to find the Shannon capacity of new graphs.