Dominating and total dominating partitions in cubic graphs

Justin Southey, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

Abstract

In this paper, we continue the study of domination and total domination in cubic graphs. It is known [Henning M. A., Southey J., A note on graphs with disjoint dominating and total dominating sets, Ars Combin., 2008, 89, 159-162] that every cubic graph has a dominating set and a total dominating set which are disjoint. In this paper we show that every connected cubic graph on n vertices has a total dominating set whose complement contains a dominating set such that the cardinality of the total dominating set is at most (n + 2)/2, and this bound is essentially best possible.

Original languageEnglish
Pages (from-to)699-708
Number of pages10
JournalCentral European Journal of Mathematics
Volume9
Issue number3
DOIs
Publication statusPublished - Jun 2011

Keywords

  • Cubic graphs
  • Hypergraph transversal
  • Total domination
  • Vertex partition

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Dominating and total dominating partitions in cubic graphs'. Together they form a unique fingerprint.

Cite this