On 3-simplicial vertices in planar graphs

Endre Boros; Robert E. Jamison; Renu Laskar; Henry Martyn Mulder

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 3, page 413-421
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Endre Boros, et al. "On 3-simplicial vertices in planar graphs." Discussiones Mathematicae Graph Theory 24.3 (2004): 413-421. <http://eudml.org/doc/270616>.

@article{EndreBoros2004,
abstract = {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.},
author = {Endre Boros, Robert E. Jamison, Renu Laskar, Henry Martyn Mulder},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {planar graph; outerplanar graph; 3-simplicial vertex},
language = {eng},
number = {3},
pages = {413-421},
title = {On 3-simplicial vertices in planar graphs},
url = {http://eudml.org/doc/270616},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Endre Boros
AU - Robert E. Jamison
AU - Renu Laskar
AU - Henry Martyn Mulder
TI - On 3-simplicial vertices in planar graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 3
SP - 413
EP - 421
AB - 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.
LA - eng
KW - planar graph; outerplanar graph; 3-simplicial vertex
UR - http://eudml.org/doc/270616
ER -

References

top
  1. [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. Zbl0266.05101
  2. [2] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). Zbl0541.05054
  3. [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. Zbl0947.05055
  4. [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. Zbl0121.37605
  5. [5] H. Lebesgue, Quelques conséquences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940) 27-43. Zbl0024.28701

NotesEmbed ?

top

You must be logged in to post comments.