Cutting lemma and union lemma for the domination game

被引：3

作者：

Dorbec, Paul ^{[1
]}

Henning, Michael A. ^{[2
]}

Klavzar, Sandi ^{[3
,4
,5
]}

Kosmrlj, Gasper ^{[5
,6
]}

机构：

[1] Normandie Univ, GREYC, CNRS, ENSICAEN,UNICAEN, F-14000 Caen, France

[2] Univ Johannesburg, Dept Pure & Appl Math, ZA-2006 Auckland Pk, South Africa

[3] Univ Ljubljana, Fac Math & Phys, Ljubljana, Slovenia

[4] Univ Maribor, Fac Nat Sci & Math, Maribor, Slovenia

[5] Inst Math Phys & Mech, Ljubljana, Slovenia

[6] Abelium R&D, Ljubljana, Slovenia

来源：

DISCRETE MATHEMATICS | 2019年 / 342卷 / 04期

基金：

新加坡国家研究基金会;

关键词：

Domination game; Domination game critical graph; Tree; EXTREMAL FAMILIES; GRAPHS; 3/5-CONJECTURE;

D O I：

10.1016/j.disc.2019.01.007

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (C) 2019 Elsevier B.V. All rights reserved.

引用

页码：1213 / 1222

页数：10