Total domination in planar graphs of diameter two

Michael A. Henning, John McCoy

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

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 languageEnglish
Pages (from-to)6181-6189
Number of pages9
JournalDiscrete Mathematics
Volume309
Issue number21
DOIs
Publication statusPublished - 6 Nov 2009
Externally publishedYes

Keywords

  • Diameter
  • Planar graphs
  • Total domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Total domination in planar graphs of diameter two'. Together they form a unique fingerprint.

Cite this