-
Wayne Barrett
-
Shaun M. Fallat
-
H. Tracy Hall
-
Leslie Hogben
Keywords:
Nordhaus-Gaddum, Colin de Verdière type parameter, Graph Complement Conjecture, maximum nullity, minimum rank, graph complement
Abstract
We establish the bounds $\frac 4 3 \le b_\nu \le b_\xi\le \sqrt 2$, where $b_\nu$ and $b_\xi$ are the Nordhaus-Gaddum sum upper bound multipliers, i.e., $\nu(G)+\nu(\overline{G})\le b_\nu |G|$ and $\xi(G)+\xi(\overline{G})\le b_\xi | G|$ for all graphs $G$, and $\nu$ and $\xi$ are Colin de Verdiere type graph parameters. The Nordhaus-Gaddum sum lower bound for $\nu$ and $\xi$ is conjectured to be $|G| - 2$, and if these parameters are replaced by the maximum nullity $M(G)$, this bound is called the Graph Complement Conjecture in the study of minimum rank/maximum nullity problems.