Article in press
Authors:
Danilo Artigas
RIC, Universidade Federal Fluminense, Rio das Ostras, Brazil
email: daniloartigas@id.uff.br
Title:
On the edge-sum distinguishing game
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2022-11-25 , Revised: 2023-06-07 , Accepted: 2023-06-11 , Available online: 2023-07-08 , https://doi.org/10.7151/dmgt.2502
Abstract:
The Edge-Sum Distinguishing game (ESD game) is a graph labeling game
proposed by Tuza in $2017$. In such a game, the players, traditionally called
Alice and Bob, alternately assign an unused label $f(v) \in \{1,\ldots, s\}$ to
an unlabeled vertex $v$ of a graph $G$, and the induced edge label $\phi(uv)$ of
an edge $uv \in E(G)$ is given by $\phi(uv) = f(u) + f(v)$. Alice's goal is to
end up with an injective vertex labeling of all vertices of $G$ that induces
distinct edge labels, and Bob's goal is to prevent this. Tuza also posed the
following questions about the ESD game: given a simple graph $G$, for which
values of $s$ can Alice win the ESD game? And if Alice wins the ESD game with
the set of labels $\{1,\ldots, s\}$, can she also win with $\{1,\ldots, s+1\}$?
In this work, we partially answer these questions by presenting bounds on the
number of consecutive non-negative integer labels necessary for Alice to win the
ESD game on general and classical families of graphs.
Keywords:
graph labeling, labeling game, maker-breaker game, edge-sum distinguishing game, combinatorial game
References:
- J. Bok and N. Jedličková, Edge-sum distinguishing labeling, Comment. Math. Univ. Carolin. 62 (2021) 135–149.
https://doi.org/10.14712/1213-7243.2021.010 - E. Boudreau, B. Hartnell, K. Schmeisser and J. Whiteley, A game based on vertex-magic total labelings, Australas. J. Combin. 29 (2004) 67–73.
- H. Enomoto, A. Lhadó, T. Nakamigawa and G. Ringel, Super edge-magic graphs, SUT J. Math. 34 (1998) 105–109.
https://doi.org/10.55937/sut/991985322 - L. Frickes, S. Dantas and A.G. Luiz, The graceful game, in: Proc. 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, (Enschede, Netherlands 2019) 45–48.
- J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2022) #DS6.
https://doi.org/10.37236/27 - R.L. Graham and N.J. Sloane, On additive bases and harmonious graphs, SIAM J. Alg. Discrete Meth. 1 (1980) 382–404.
https://doi.org/10.1137/0601045 - B. Hartnell and D. Rall, A vertex-magic edge labeling game, Congr. Numer. 161 (2003) 163–167.
- N. Hartsfield and G. Ringel, Pearls in Graph Theory (Academic Press, Inc., San Diego, 1990).
- A. Kotzig and A. Rosa, Magic valuations of finite graphs, Canad. Math. Bull. 13 (1970) 451–461.
https://doi.org/10.4153/CMB-1970-084-1 - B. Liu and X. Zhang, On harmonious labelings of graphs, Ars Combin. 36 (1993) 315–326.
- D.L. Oliveira, S. Dantas and A.G. Luiz, Results on the graceful game and range-relaxed graceful game, in: Extended Abstracts EuroComb 2021, Trends in Mathematics 14, J. Nešetřil, G. Perarnau, J. Rué and O. Serra (Ed(s)), (Birkhauser, Cham 2021) 214–220.
https://doi.org/10.1007/978-3-030-83823-2_34 - J. Sedláček, Problem $27$, in: Theory of Graphs and Its Applications, Proc. Symp. Smolenice 1963, (Nakl. CSAV, Praha 1963) 163–164.
- E. Sidorowicz, Colouring game and generalized colouring game on graphs with cut-vertices, Discuss. Math. Graph Theory 30 (2010) 499–533.
https://doi.org/10.7151/dmgt.1510 - Zs. Tuza, Graph labeling games, Electron. Notes Discrete Math. 60 (2017) 61–68.
https://doi.org/10.1016/j.endm.2017.06.009
Close