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

View/ Open
Date
2013Author
Barrett, Wayne
Fallat, Shaun
Hall, Tracy
Hogben, Leslie
Metadata
Show full item recordAbstract
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.