TY - JOUR

T1 - Graph complement conjecture for classes of shadow graphs

AU - Jansrang, Monsikarn

AU - Narayan, Sivaram K.

N1 - Funding Information:
The first author thanks Central Michigan University for its support.
Publisher Copyright:
© 2021, Element D.O.O.. All rights reserved.

PY - 2021/6

Y1 - 2021/6

N2 - 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+.

AB - 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+.

UR - http://www.scopus.com/inward/record.url?scp=85111011493&partnerID=8YFLogxK

U2 - 10.7153/oam-2021-15-40

DO - 10.7153/oam-2021-15-40

M3 - Article

AN - SCOPUS:85111011493

VL - 15

SP - 589

EP - 614

JO - Operators and Matrices

JF - Operators and Matrices

SN - 1846-3886

IS - 2

M1 - OaM-15-40

ER -