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
Hogben, Leslie
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Department
Electrical and Computer EngineeringMathematics
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.

Comments

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.

Description
Keywords
Citation
DOI
Collections