Note on Nordhaus-Gaddum Problems for Colin de Verdière type Parameters

Date
2013-10-07
Authors
Barrett, Wayne
Fallat, Shaun
Hall, H. Tracy
Hogben, Leslie
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Abstract

We establish the bounds 4 3 6 b 6 b 6 p 2, where b and b are the Nordhaus-Gaddum sum upper bound multipliers, i.e., (G)+(G) 6 bjGj and (G)+(G) 6 bjGj for all graphs G, and and are Colin de Verdiere type graph parameters. The Nordhaus-Gaddum sum lower bound for and is conjectured to be jGj 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.

Description

This article is published as Barrett, Wayne, Shaun M. Fallat, H. Tracy Hall, and Leslie Hogben. "Note on Nordhaus-Gaddum Problems for Colin de Verdière type Parameters." The Electronic Journal of Combinatorics 20, no. 3 (2013): P56. DOI: 10.37236/2570. Posted with permission.

Keywords
Nordhaus-Gaddum, Colin de Verdière type parameter, Graph Complement Conjecture, maximum nullity, minimum rank, graph complement
Citation
DOI
Collections