Maker–Breaker domination number for Cartesian products of path graphs P2 and Pn

Једноставна страница ставке
dc.citation.epage32
dc.citation.spage1
dc.citation.volume25
dc.contributor.authorForcan, Jovana
dc.contributor.authorQi, Jiayue
dc.date.accessioned2024-11-13T13:12:52Z
dc.date.available2024-11-13T13:12:52Z
dc.date.issued2023
dc.description.abstractWe 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) (γ′ M B(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 γ′ M B(P2□Pn) = n for n ≥ 1, γMB(P2□Pn) equals n, n − 1, n − 2, for 1 ≤ n ≤ 4, 5 ≤ n ≤ 12, and n ≥ 13, respectively. For the disjoint union of P2□Pns, we show that γ′ M B(˙∪k i=1(P2□Pn)i) = k · n (n ≥ 1), and that γMB(˙∪k i=1(P2□Pn)i) equals k · n, k · n − 1, k · n − 2 for 1 ≤ n ≤ 4, 5 ≤ n ≤ 12, and n ≥ 13, respectively.
dc.identifier.urihttps://vaseljena.ues.rs.ba/handle/123456789/1292
dc.language.isoen
dc.publisherMaison de l'informatique et des mathematiques discretes
dc.sourceDiscrete Mathematics and Theoretical Computer Science
dc.subjectPositional game, Maker–Breaker domination game, Maker–Breaker domination number for grids, winning strategy on grids
dc.titleMaker–Breaker domination number for Cartesian products of path graphs P2 and Pn
dc.typeArticle
Датотеке
Оригинални завежљај
Сада се приказује 1 - 1 од 1
Сличица
Име:
Maker–Breaker domination number for.pdf
Величина:
1 MB
Формат:
Adobe Portable Document Format
Опис:
Преузимање
Свежањ лиценце
Сада се приказује 1 - 1 од 1
Сличица
Име:
license.txt
Величина:
1.71 KB
Формат:
Item-specific license agreed to upon submission
Опис:
Преузимање
Колекције
Филозофски факултет [Научни радови] / Faculty of Philosophy [Scientific papers]