Triangle-free planar graphs with minimum degree 3 have radius at least 3

• Autorzy: Seog-Jin Kim , Douglas B. West
• Języki publikacji: EN

Abstrakty

EN

We prove that every triangle-free planar graph with minimum degree 3 has radius at least 3; equivalently, no vertex neighborhood is a dominating set.

Słowa kluczowe

EN

planar graph; radius; minimum degree; triangle-free; dominating set

Kategorie tematyczne

• 05C12: Distance in graphs
• 05C10: Planar graphs; geometric and topological aspects of graph theory
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2008
• Tom: 28
• Numer: 3
• Strony: 563-566

Daty

wydano

2008

otrzymano

2008-01-29

zaakceptowano

2008-05-09

Twórcy

autor

Seog-Jin Kim

• Konkuk University, Seoul, Korea

autor

Douglas B. West

• Department of Mathematics, University of Illinois, Urbana, IL 61801, USA

Bibliografia

• [1] P. Erdös, J. Pach, R. Pollack and Zs. Tuza, Radius, diameter, and minimum degree, J. Combin. Theory (B) 47 (1989) 73-79, doi: 10.1016/0095-8956(89)90066-X.
• [2] J. Harant, An upper bound for the radius of a 3-connected planar graph with bounded faces, Contemporary methods in graph theory (Bibliographisches Inst., Mannheim, 1990), 353-358.
• [3] J. Plesník, Critical graphs of given diameter, Acta Fac. Rerum Natur. Univ. Comenian. Math. 30 (1975) 71-93.

Identyfikatory

DOI

10.7151/dmgt.1428