Bounds on minimum semidefinite rank of graphs

Abstract

The minimum semidefinite rank of a graph is defined to be the minimum rank among all Hermitian positive semidefinite matrices associated to the graph. A problem of interest is to find upper and lower bounds for of a graph using known graph parameters such as the independence number and the minimum degree of the graph. We provide a sufficient condition for of a bipartite graph to equal its independence number. The delta conjecture gives an upper bound for of a graph in terms of its minimum degree. We present classes of graphs for which the delta conjecture holds.

Keywords:

• matrix of a graph
• minimum semidefinite rank
• independence number
• connectivity of a graph
• delta conjecture

AMS Subject Classifications:

• 15A18
• 05C50
• 05C07

Acknowledgements

The authors thank the referee for many valuable comments that have improved the quality of this paper. The second author would like to thank Central Michigan University for its support.