Maker-Breaker domination number for Cartesian products of path graphs P₂ and P_n

DOI10.46298/DMTCS.10465arXiv2004.13126MaRDI QIDQ6507490FDOQ6507490

Authors: Jovana Forcan, Jiayue Qi 

Abstract: We study the Maker--Breaker domination game played by Dominator and Staller on the vertex set of a given graph. Dominator wins when the vertices he has claimed form a dominating set of the graph. Staller wins if she makes it impossible for Dominator to win, or equivalently, she is able to claim some vertex and all its neighbours. Maker--Breaker domination number $gamm{a}_{MB}(G)$ ($gamma{\text{'}}_{MB}(G)$) of a graph $G$ is defined to be the minimum number of moves for Dominator to guarantee his winning when he plays first (second). We investigate these two invariants for the Cartesian product of any two graphs. We obtain upper bounds for the Maker--Breaker domination number of the Cartesian product of two arbitrary graphs. Also, we give upper bounds for the Maker--Breaker domination number of the Cartesian product of the complete graph with two vertices and an arbitrary graph. Most importantly, we prove that $gamma{\text{'}}_{MB}(P_{2}square{P}_n)=n$ for $ngeq1$, $gamm{a}_{MB}(P_{2}square{P}_n)$ equals to $n$, $n-1$, $n-2$ for $1leqnleq4$, $5leqnleq12$, and $ngeq13$ respectively. For the disjoint union of $P_{2}square{P}_n$s, we show that $gamm{a}_{M^{\prime }B}(dotcu{p}_{i=1}^k(P_{2}square{P}_n{)}_i)=kcdotn$ ($ngeq1$), and that $gamm{a}_{MB}(dotcu{p}_{i=1}^k(P_{2}square{P}_n{)}_i)$ equals to $kcdotn$, $kcdotn-1$, $kcdotn-2$ for $1leqnleq4$, $5leqnleq12$, and $ngeq13$ respectively.

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games on graphs (graph-theoretic aspects) (05C57) Positional games (pursuit and evasion, etc.) (91A24)

This page was built for publication: Maker-Breaker domination number for Cartesian products of path graphs $P_2$ and $P_n$

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