On 3-simplicial vertices in planar graphs

• Autorzy: Endre Boros , Robert E. Jamison , Renu Laskar , Henry Martyn Mulder
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

planar graph; outerplanar graph; 3-simplicial vertex

Kategorie tematyczne

• 05C75: Structural characterization of families of graphs
• 05C99: None of the above, but in this section

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2004
• Tom: 24
• Numer: 3
• Strony: 413-421

Daty

wydano

2004

otrzymano

2003-02-25

poprawiono

2004-02-05

Twórcy

autor

Endre Boros

• RUTCOR, Rutgers, The State University of New Jersey, 640 Bartholomew Road, Piscataway, NJ 08854-8003, USA

autor

Robert E. Jamison

• Department of Mathematical Sciences, Clemson University, Clemson, SC 29634-0975, USA

autor

Renu Laskar

• Department of Mathematical Sciences, Clemson University, Clemson, SC 29634-0975, USA

autor

Henry Martyn Mulder

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

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1240