On the graph complement conjecture for minimum rank

F. Barioli, W. Barrett, S.M. Fallat, H.T. Hall, L. Hogben, H. Holst, van der

Research output: Contribution to journalArticleAcademicpeer-review

20 Citations (Scopus)


The minimum rank of a graph has been an interesting and well studied parameter investigated by many researchers over the past decade or so. One of the many unresolved questions on this topic is the so-called graph complement conjecture, which grew out of a workshop in 2006. This conjecture asks for an upper bound on the sum of the minimum rank of a graph and the minimum rank of its complement, and may be classified as a Nordhaus–Gaddum type problem involving the graph parameter minimum rank. The conjectured bound is the order of the graph plus two. Other variants of the graph complement conjecture are introduced here for the minimum semidefinite rank and the Colin de Verdière type parameter ¿. We show that if the ¿-graph complement conjecture is true for two graphs then it is true for the join of these graphs. Related results for the graph complement conjecture (and the positive semidefinite version) for joins of graphs are also established. We also report on the use of recent results on partial k-trees to establish the graph complement conjecture for graphs of low minimum rank.
Original languageEnglish
Pages (from-to)4373-4391
JournalLinear Algebra and Its Applications
Issue number12
Publication statusPublished - 2012


Dive into the research topics of 'On the graph complement conjecture for minimum rank'. Together they form a unique fingerprint.

Cite this