A vertex v in a graph G = (V,E) is k-simplicial if the neighborhood N(v) of v can be vertex-covered by k or fewer complete graphs. The main result of the paper states that a planar graph of order at least four has at least four 3-simplicial vertices of degree at most five. This result is a strengthening of the classical corollary of Euler's Formula that a planar graph of order at least four contains at least four vertices of degree at most five.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1240,
author = {Endre Boros and Robert E. Jamison and Renu Laskar and Henry Martyn Mulder},
title = {On 3-simplicial vertices in planar graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {24},
year = {2004},
pages = {413-421},
zbl = {1068.05018},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1240}
}
Endre Boros; Robert E. Jamison; Renu Laskar; Henry Martyn Mulder. On 3-simplicial vertices in planar graphs. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 413-421. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1240/
[000] [1] F. Gavril, The intersection graph of subtrees in a tree are exactly the chordal graphs, J. Combin. Theory 16 (1974) 47-56, doi: 10.1016/0095-8956(74)90094-X. | Zbl 0266.05101
[001] [2] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). | Zbl 0541.05054
[002] [3] R.E. Jamison and H.M. Mulder, Tolerance intersection graphs on binary trees with constant tolerance 3, Discrete Math. 215 (2000) 115-131, doi: 10.1016/S0012-365X(99)00231-9. | Zbl 0947.05055
[003] [4] B. Grünbaum and T.S. Motzkin, The number of hexagons and the simplicity of geodesics on certain polyhedra, Canad. J. Math. 15 (1963) 744-751, doi: 10.4153/CJM-1963-071-3. | Zbl 0121.37605
[004] [5] H. Lebesgue, Quelques conséquences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940) 27-43. | Zbl 0024.28701