Geodesic
Note on Nordhaus-Gaddum problems for Colin de Verdière type parameters
Wayne Barrett1 ; Shaun M. Fallat2 ; H. Tracy Hall1 ; Leslie Hogben3
1Brigham Young University
2University of Regina
3Iowa State University and American Institute of Mathematics
The electronic journal of combinatorics, Tome 20 (2013) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We establish the bounds $\frac 4 3 \le b_\nu \le b_\xi\le \sqrt 2$, where $b_\nu$ and $b_\xi$ are the Nordhaus-Gaddum sum upper bound multipliers, i.e., $\nu(G)+\nu(\overline{G})\le b_\nu |G|$ and $\xi(G)+\xi(\overline{G})\le b_\xi | G|$ for all graphs $G$, and $\nu$ and $\xi$ are Colin de Verdiere type graph parameters. The Nordhaus-Gaddum sum lower bound for $\nu$ and $\xi$ 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.
DOI : 10.37236/2570
Classification : 05C50, 05C40, 05C83, 15A03, 15B57
Mots-clés : Nordhaus-Gaddum problem, Colin de Verdière-type parameter, graph complement conjecture, maximum nullity, minimum rank

Wayne Barrett  1   ; Shaun M. Fallat  2   ; H. Tracy Hall  1   ; Leslie Hogben  3

1 Brigham Young University
2 University of Regina
3 Iowa State University and American Institute of Mathematics 
@article{10_37236_2570,
     author = {Wayne Barrett and Shaun M. Fallat and H. Tracy Hall and Leslie Hogben},
     title = {Note on {Nordhaus-Gaddum} problems for {Colin} de {Verdi\`ere} type parameters},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {3},
     doi = {10.37236/2570},
     zbl = {1295.05140},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2570/}
}
TY  - JOUR
AU  - Wayne Barrett
AU  - Shaun M. Fallat
AU  - H. Tracy Hall
AU  - Leslie Hogben
TI  - Note on Nordhaus-Gaddum problems for Colin de Verdière type parameters
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2570/
DO  - 10.37236/2570
ID  - 10_37236_2570
ER  - 
%0 Journal Article
%A Wayne Barrett
%A Shaun M. Fallat
%A H. Tracy Hall
%A Leslie Hogben
%T Note on Nordhaus-Gaddum problems for Colin de Verdière type parameters
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/2570/
%R 10.37236/2570
%F 10_37236_2570
Wayne Barrett; Shaun M. Fallat; H. Tracy Hall; Leslie Hogben. Note on Nordhaus-Gaddum problems for Colin de Verdière type parameters. The electronic journal of combinatorics, Tome 20 (2013) no. 3. doi: 10.37236/2570

Cité par Sources :