Note on Nordhaus-Gaddum problems for Colin de Verdiere type parameters

Abstract

We establish the bounds 4 on the Nordhaus- Gaddum sum upper bound multipliers for all graphs G, in connections with certain Colin de Verdi ere type graph parameters. The Nordhaus-Gaddum sum lower bound 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.