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.
