Haemers' Minimum Rank

Thumbnail Image
Date
2013-01-01
Authors
Tims, Geoff
Major Professor
Advisor
Leslie Hogben
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Mathematics
Abstract

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.

Comments
Description
Keywords
Citation
Source
Subject Categories
Copyright
Tue Jan 01 00:00:00 UTC 2013