Degree Type

Dissertation

Date of Award

2013

Degree Name

Doctor of Philosophy

Department

Mathematics

First Advisor

Leslie Hogben

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.

DOI

https://doi.org/10.31274/etd-180810-3393

Copyright Owner

Geoff Tims

Language

en

File Format

application/pdf

File Size

70 pages

Included in

Mathematics Commons

Share

COinS