Cutting lemma and union lemma for the domination game

Paul Dorbec, Michael A. Henning, Sandi Klavžar, Gašper Košmrlj

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

Two new techniques are introduced into the theory of the domination game. The cutting lemma bounds the game domination number of a partially dominated graph with the game domination number of a suitably modified partially dominated graph. The union lemma bounds the S-game domination number of a disjoint union of paths using appropriate weighting functions. Using these tools a conjecture asserting that the so-called three legged spiders are game domination critical graphs is proved. An extended cutting lemma is also derived and all game domination critical trees on 18, 19, and 20 vertices are listed.

Original languageEnglish
Pages (from-to)1213-1222
Number of pages10
JournalDiscrete Mathematics
Volume342
Issue number4
DOIs
Publication statusPublished - Apr 2019

Keywords

  • Domination game
  • Domination game critical graph
  • Tree

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Cutting lemma and union lemma for the domination game'. Together they form a unique fingerprint.

Cite this