Maker-Breaker Metric Resolving Games on Graphs

DOI10.1142/S1793830923500064MaRDI QIDQ6408124zbMATH OpenOpenAlexFDO

Authors Cong X. Kang, Eunjeong Yi

Publication date 17 August 2022

Full work available at URL https://doi.org/10.1142/s1793830923500064

Mathematics Subject Classification ID

Distance in graphs (05C12) Games on graphs (graph-theoretic aspects) (05C57)

Abstract: Let $d(x,y)$ denote the length of a shortest path between vertices $x$ and $y$ in a graph $G$ with vertex set $V$. For a positive integer $k$, let $d_k(x,y)=mind(x,y),k+1$ and $R_{k}x,y=zinV:d_k(x,z)eq{d}_k(y,z)$. A set $SsubseteqV$ is a emph{distance-$k$ resolving set} of $G$ if $Scap{R}_{k}x,yeqemptyset$ for distinct $x,yinV$. In this paper, we study the maker-breaker distance-$k$ resolving game (MB$k$RG) played on a graph $G$ by two players, Maker and Breaker, who alternately select a vertex of $G$ not yet chosen. Maker wins by selecting vertices which form a distance-$k$ resolving set of $G$, whereas Breaker wins by preventing Maker from winning. We denote by $O_{R,k}(G)$ the outcome of MB$k$RG. Let $mathcalM$, $mathcalB$ and $mathcalN$, respectively, denote the outcome for which Maker, Breaker, and the first player has a winning strategy in MB$k$RG. Given a graph $G$, the parameter $O_{R,k}(G)$ is a non-decreasing function of $k$ with codomain $-1=mathcalB,0=mathcalN,1=mathcalM$. We exhibit pairs $G$ and $k$ such that the ordered pair $(O_{R,k}(G),O_{R,k+1}(G))$ realizes each member of the set $(mathcalB,mathcalN),(mathcalB,mathcalM),(mathcalN,mathcalM)$; we provide graphs $G$ such that $O_{R,1}(G)=mathcalB$, $O_{R,2}(G)=mathcalN$ and $O_{R,k}(G)=mathcalM$ for $kge3$. Moreover, we obtain some general results on MB$k$RG and study the MB$k$RG played on some graph classes.

Recommendations

• Maker-breaker resolving game
• Fast winning strategies for the maker-breaker domination game
• Maker-breaker domination number
• The graph distance game

Cited in

(3)

• On distance-s locating and distance-t dominating sets in graphs
• Maker-breaker resolving game played on corona products of graphs
• Maker-breaker resolving game played on lexicographic products of graphs

This page was built for publication: Maker-Breaker Metric Resolving Games on Graphs

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