## Abstract

MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213-229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. Henning, Domination in planar graphs with small diameter, J. Graph Theory 40 (2002) 1-25] showed that there is a unique planar graph of diameter two with domination number three. It follows that the total domination number of a planar graph of diameter two is at most three. In this paper, we consider the problem of characterizing planar graphs with diameter two and total domination number three. We say that a graph satisfies the domination-cycle property if there is some minimum dominating set of the graph not contained in any induced 5-cycle. We characterize the planar graphs with diameter two and total domination number three that satisfy the domination-cycle property and show that there are exactly thirty-four such planar graphs.

Original language | English |
---|---|

Pages (from-to) | 6181-6189 |

Number of pages | 9 |

Journal | Discrete Mathematics |

Volume | 309 |

Issue number | 21 |

DOIs | |

Publication status | Published - 6 Nov 2009 |

Externally published | Yes |

## Keywords

- Diameter
- Planar graphs
- Total domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics