Discussiones Mathematicae Graph Theory 28(3) (2008) 563-566
doi: 10.7151/dmgt.1428

[BIBTex] [PDF] [PS]

TRIANGLE-FREE PLANAR GRAPHS WITH MINIMUM DEGREE 3 HAVE RADIUS AT LEAST 3

Seog-Jin Kim

Mathematics Education Department
Konkuk University, Seoul, Korea
e-mail: skim12@konkuk.ac.kr

Douglas B. West

Department of Mathematics
University of Illinois
Urbana, IL 61801, USA
e-mail: west@math.uiuc.edu

Abstract

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.

Keywords: planar graph, radius, minimum degree, triangle-free, dominating set.

2000 Mathematics Subject Classification: 05C10, 05C12, 05C69.

References

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

Received 29 January 2008
Accepted 9 May 2008