PDF
Discussiones Mathematicae Graph Theory 28(3) (2008)
563-566
DOI: https://doi.org/10.7151/dmgt.1428
TRIANGLE-FREE PLANAR GRAPHS WITH MINIMUM DEGREE 3 HAVE RADIUS AT LEAST 3
Seog-Jin Kim
Mathematics Education Department | Douglas B. West
Department of Mathematics |
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
Close