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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.