Domination in planar graphs with small diameter*

Abstract

Abstract MacGillivray and Seyffarth (J Graph Theory 22 ( 1996 ), 213–229) proved that planar graphs of diameter two have domination number at most three and planar graphs of diameter three have domination number at most ten. They also give examples of planar graphs of diameter four having arbitrarily large domination numbers. In this paper we improve on their results. We prove that there is in fact a unique planar graph of diameter two with domination number three, and all other planar graphs of diameter two have domination number at most two. We also prove that every planar graph of diameter three and of radius two has domination number at most six. We then show that every sufficiently large planar graph of diameter three has domination number at most seven. Analogous results for other surfaces are discussed. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 1–25, 2002