Trees with equal total domination and game total domination numbers

Trees (05C05) Games on graphs (graph-theoretic aspects) (05C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games involving graphs (91A43)

Abstract: In this paper, we continue the study of the total domination game in graphs introduced in [Graphs Combin. 31(5) (2015), 1453--1462], where the players Dominator and Staller alternately select vertices of

G

. Each vertex chosen must strictly increase the number of vertices totally dominated, where a vertex totally dominates another vertex if they are neighbors. This process eventually produces a total dominating set

S

of

G

in which every vertex is totally dominated by a vertex in

S

. Dominator wishes to minimize the number of vertices chosen, while Staller wishes to maximize it. The game total domination number,

g a m m a_{m t g} (G)

, (respectively, Staller-start game total domination number,

g a m m a_{m^{'} t g} (G)

) of

G

is the number of vertices chosen when Dominator (respectively, Staller) starts the game and both players play optimally. For general graphs

G

, sometimes

g a m m a_{m t g} (G) > g a m m a_{m^{'} t g} (G)

. We show that if

G

is a forest with no isolated vertex, then

g a m m a_{m t g} (G) l e g a m m a_{m^{'} t g} (G)

. Using this result, we characterize the trees with equal total domination and game total domination number.

Recommendations

Cites work

Cited in

(23)

This page was built for publication: Trees with equal total domination and game total domination numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2357775)