Geodesic
Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph
Lon Mitchell1 ; Lynne Yengulalp2
1American Mathematical Society
2University of Dayton
The electronic journal of combinatorics, Tome 23 (2016) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We prove that a $k$-tree can be viewed as a subgraph of a special type of $(k+1)$-tree that corresponds to a stacked polytope and that these "stacked'' $(k+1)$-trees admit representations by orthogonal spheres in $\mathbb{R}^{k+1}$. As a result, we derive lower bounds for Colin de Verdière's $\mu$ of complements of partial $k$-trees and prove that $\mu(G) + \mu(\overline{G}) \geq |G| - 2$ for all chordal $G$.
DOI : 10.37236/4444
Classification : 05C50, 05C10
Mots-clés : Colin de Verdière invariant, chordal graphs, sphere representations, stacked polytopes

Lon Mitchell  1   ; Lynne Yengulalp  2

1 American Mathematical Society
2 University of Dayton 
@article{10_37236_4444,
     author = {Lon Mitchell and Lynne Yengulalp},
     title = {Sphere representations, stacked polytopes, and the {Colin} de {Verdi\`ere} number of a graph},
     journal = {The electronic journal of combinatorics},
     year = {2016},
     volume = {23},
     number = {1},
     doi = {10.37236/4444},
     zbl = {1329.05195},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4444/}
}
TY  - JOUR
AU  - Lon Mitchell
AU  - Lynne Yengulalp
TI  - Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph
JO  - The electronic journal of combinatorics
PY  - 2016
VL  - 23
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4444/
DO  - 10.37236/4444
ID  - 10_37236_4444
ER  - 
%0 Journal Article
%A Lon Mitchell
%A Lynne Yengulalp
%T Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/4444/
%R 10.37236/4444
%F 10_37236_4444
Lon Mitchell; Lynne Yengulalp. Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph. The electronic journal of combinatorics, Tome 23 (2016) no. 1. doi: 10.37236/4444

Cité par Sources :