On the total domination number of cartesian products of graphs

Michael A. Henning, Douglas F. Rall

Research output: Contribution to journalArticlepeer-review

34 Citations (Scopus)


The most famous open problem involving domination in graphs is Vizing's conjecture which states the domination number of the Cartesian product of any two graphs is at least as large as the product of their domination numbers. In this paper, we investigate a similar problem for total domination. In particular, we prove that the product of the total domination numbers of any nontrivial tree and any graph without isolated vertices is at most twice the total domination number of their Cartesian product, and we characterize the extremal graphs.

Original languageEnglish
Pages (from-to)63-69
Number of pages7
JournalGraphs and Combinatorics
Issue number1
Publication statusPublished - Mar 2005
Externally publishedYes


  • Graph products
  • Total domination
  • Vizing's conjecture

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On the total domination number of cartesian products of graphs'. Together they form a unique fingerprint.

Cite this