Bounds on the sum of minimum semidefinite rank of a graph and its complement

Sivaram K. Narayan, Yousra Sharawi

Research output: Contribution to journalArticlepeer-review

Abstract

The minimum semi-definite rank (msr) of a graph is the minimum rank among all positive semi-definite matrices associated to the graph. The graph complement conjecture gives an upper bound for the sum of the msr of a graph and the msr of its complement. It is shown that when the msr of a graph is equal to its independence number, the graph complement conjecture holds with a better upper bound. Several sufficient conditions are provided for the msr of different classes of graphs to equal to its independence number.

Original languageEnglish
Article number31
Pages (from-to)399-406
Number of pages8
JournalElectronic Journal of Linear Algebra
Volume34
DOIs
StatePublished - 2018

Keywords

  • Graph complement conjecture
  • Independence number
  • Matrix of a graph
  • Minimum semidefinite rank

Fingerprint

Dive into the research topics of 'Bounds on the sum of minimum semidefinite rank of a graph and its complement'. Together they form a unique fingerprint.

Cite this