Maker-Breaker domination number for Cartesian products of path graphs $P_2$ and $P_n$
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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2024-04-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/10465/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850278337859026944 |
|---|---|
| author | Jovana Forcan Jiayue Qi |
| author_facet | Jovana Forcan Jiayue Qi |
| author_sort | Jovana Forcan |
| collection | DOAJ |
| description | 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 $\gamma_{MB}(G)$ ($\gamma '_{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'_{MB}(P_2\square P_n)=n$ for $n\geq 1$, $\gamma_{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 $\gamma_{MB}'(\dot\cup_{i=1}^k(P_2\square P_n)_i)=k\cdot n$ ($n\geq 1$), and that $\gamma_{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. |
| format | Article |
| id | doaj-art-9495cacfc54746d0a76b54608e57853f |
| institution | OA Journals |
| issn | 1365-8050 |
| language | English |
| publishDate | 2024-04-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-9495cacfc54746d0a76b54608e57853f2025-08-20T01:49:32ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502024-04-01vol. 25:2Graph Theory10.46298/dmtcs.1046510465Maker-Breaker domination number for Cartesian products of path graphs $P_2$ and $P_n$Jovana ForcanJiayue QiWe 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 $\gamma_{MB}(G)$ ($\gamma '_{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'_{MB}(P_2\square P_n)=n$ for $n\geq 1$, $\gamma_{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 $\gamma_{MB}'(\dot\cup_{i=1}^k(P_2\square P_n)_i)=k\cdot n$ ($n\geq 1$), and that $\gamma_{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.http://dmtcs.episciences.org/10465/pdfmathematics - combinatorics91a24, 05c69, 05c57 |
| spellingShingle | Jovana Forcan Jiayue Qi Maker-Breaker domination number for Cartesian products of path graphs $P_2$ and $P_n$ Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics 91a24, 05c69, 05c57 |
| title | Maker-Breaker domination number for Cartesian products of path graphs $P_2$ and $P_n$ |
| title_full | Maker-Breaker domination number for Cartesian products of path graphs $P_2$ and $P_n$ |
| title_fullStr | Maker-Breaker domination number for Cartesian products of path graphs $P_2$ and $P_n$ |
| title_full_unstemmed | Maker-Breaker domination number for Cartesian products of path graphs $P_2$ and $P_n$ |
| title_short | Maker-Breaker domination number for Cartesian products of path graphs $P_2$ and $P_n$ |
| title_sort | maker breaker domination number for cartesian products of path graphs p 2 and p n |
| topic | mathematics - combinatorics 91a24, 05c69, 05c57 |
| url | http://dmtcs.episciences.org/10465/pdf |
| work_keys_str_mv | AT jovanaforcan makerbreakerdominationnumberforcartesianproductsofpathgraphsp2andpn AT jiayueqi makerbreakerdominationnumberforcartesianproductsofpathgraphsp2andpn |