论文标题
PATH图的笛卡尔产品$ P_2 $和$ P_N $
Maker-Breaker domination number for Cartesian products of path graphs $P_2$ and $P_n$
论文作者
论文摘要
我们研究了由Dominator和Staller在给定图的顶点集上进行的制造商破坏者统治游戏。当他声称形成一组图表的顶点时，主导者会获胜。如果史塔勒（Staller）使统治者不可能获胜或等同地赢得胜利，那么她就能声称某些顶点及其所有邻居。制造商 - 破坏者统治数$γ_{MB}（G）$（$γ'_{MB}（G）$）的图$ G $定义为Dominator的最小动作数量，以确保他在首次比赛时（第二次）赢得胜利。我们研究了任何两个图的笛卡尔产品的这两个不变性。我们获得了两个任意图的笛卡尔产物的制造商 - 破坏者统治数。同样，我们为完整图的笛卡尔产品的制造商破坏者支配数和一个任意图提供了上限。最重要的是，我们证明$γ'_ {mb}（p_2 \ square p_n）= n $ for $ n \ geq 1 $，$γ_{mb}（p_2 \ square p_n）$等于$ n $，$ n $，$ n-1 $，$ n-1 $，$ n-2 $，$ n-2 $，$ n \ leq n \ leq leq 4 $ quq 4 $ 5分别为13美元。对于$ p_2 \ square p_n $ s的分离联合，我们表明$γ_{mb}'（\ dot \ cup_ {i = 1}^k（p_2 \ square p_n）_i）= k \ cdot n $（$ n \ geq 1 $） $γ_{MB}(\dot\cup_{i=1}^k(P_2\square P_n)_i)$ equals $k\cdot n$, $k\cdot n-1$, $k\cdot n-2$ for $1\leq n\leq 4$, $5\leq n\leq 12$, and $n\geq 13$, respectively.
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 $γ_{MB}(G)$ ($γ'_{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 $γ'_{MB}(P_2\square P_n)=n$ for $n\geq 1$, $γ_{MB}(P_2\square P_n)$ equals $n$, $n-1$, $n-2$, for $1\leq n\leq 4$, $5\leq n\leq 12$, and $n\geq 13$, respectively. For the disjoint union of $P_2\square P_n$s, we show that $γ_{MB}'(\dot\cup_{i=1}^k(P_2\square P_n)_i)=k\cdot n$ ($n\geq 1$), and that $γ_{MB}(\dot\cup_{i=1}^k(P_2\square P_n)_i)$ equals $k\cdot n$, $k\cdot n-1$, $k\cdot n-2$ for $1\leq n\leq 4$, $5\leq n\leq 12$, and $n\geq 13$, respectively.
