DMGT

Discussiones Mathematicae Graph Theory 24(3) (2004) 413-421
DOI: https://doi.org/10.7151/dmgt.1240

ON 3-SIMPLICIAL VERTICES IN PLANAR GRAPHS

Endre Boros

RUTCOR, Rutgers
The State University of New Jersey
640 Bartholomew Road, Piscataway, NJ 08854-8003, USA
e-mail: boros@rutcor.rutgers.edu

Robert E. Jamison

Department of Mathematical Sciences
Clemson University
Clemson, SC 29634-0975, USA
e-mail: rejam@clemson.edu

Renu Laskar

Department of Mathematical Sciences
Clemson University
Clemson, SC 29634-0975, USA
e-mail: rclsk@clemson.edu

Henry Martyn Mulder

Econometrisch Instituut, Erasmus Universiteit
P.O. Box 1738, NL-3000 DR Rotterdam, The Netherlands

e-mail: hmmulder@few.eur.nl

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.

Keywords: planar graph, outerplanar graph, 3-simplicial vertex.

2000 Mathematics Subject Classification: 05C99, 05C75.

References

[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.
[2]	M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980).
[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.
[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.
[5]	H. Lebesgue, Quelques conséquences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940) 27-43.

Received 25 February 2003
Revised 5 February 2004