Graph complement conjecture for classes of shadow graphs

Monsikarn Jansrang, Sivaram K. Narayan

Research output: Contribution to journalArticlepeer-review

Abstract

The real minimum semidefinite rank of a graph G, denoted mr +(G), is defined to be the minimum rank among all real symmetric positive semidefinite matrices whose zero/nonzero pattern corresponds to the graph G. The inequality mr +(G)+mr +(G) ≤ |G|+2 is called the graph complement conjecture, denoted GCC+, where G is the complement of G and |G| is the number of vertices in G. A known definition of shadow graph S(G) and a variant of this definition denoted Shad(G) are given. It is shown that S(G) satisfies GCC+ when G is a tree or a unicyclic graph or a complete graph. Under additional conditions on G, it is shown that S(G) satisfies GCC+ when G is a k -tree or a chordal graph. Moreover, whenever G satisfies GCC+ and G does not contain any isolated vertices, it is shown that Shad(G) satisfies GCC+.

Original languageEnglish
Article numberOaM-15-40
Pages (from-to)589-614
Number of pages26
JournalOperators and Matrices
Volume15
Issue number2
DOIs
StatePublished - Jun 2021

Fingerprint

Dive into the research topics of 'Graph complement conjecture for classes of shadow graphs'. Together they form a unique fingerprint.

Cite this