Game total domination critical graphs

Michael A. Henning, Sandi Klavžar, Douglas F. Rall

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)

Abstract

In the total domination game played on a graph [Formula presented], players Dominator and Staller alternately select vertices of [Formula presented], as long as possible, such that each vertex chosen increases the number of vertices totally dominated. Dominator (Staller) wishes to minimize (maximize) the number of vertices selected. The game total domination number, [Formula presented], of [Formula presented] is the number of vertices chosen when Dominator starts the game and both players play optimally. If a vertex [Formula presented] of [Formula presented] is declared to be already totally dominated, then we denote this graph by [Formula presented]. In this paper the total domination game critical graphs are introduced as the graphs [Formula presented] for which [Formula presented] holds for every vertex [Formula presented] in [Formula presented]. If [Formula presented], then [Formula presented] is called [Formula presented]-[Formula presented]-critical. It is proved that the cycle [Formula presented] is [Formula presented]-critical if and only if [Formula presented] and that the path [Formula presented] is [Formula presented]-critical if and only if [Formula presented]. 2-[Formula presented]-critical and 3-[Formula presented]-critical graphs are also characterized as well as 3-[Formula presented]-critical joins of graphs.

Original languageEnglish
Pages (from-to)28-37
Number of pages10
JournalDiscrete Applied Mathematics
Volume250
DOIs
Publication statusPublished - 11 Dec 2018

Keywords

  • Critical graphs
  • Game total domination number
  • Paths and cycles
  • Total domination game

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Game total domination critical graphs'. Together they form a unique fingerprint.

Cite this