Geodesic
On the edge-sum distinguishing game
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1449-1469 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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) ∈{1,…, s} to an unlabeled vertex v of a graph G, and the induced edge label ϕ(uv) of an edge uv ∈ E(G) is given by ϕ(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,…, s}, can she also win with {1,…, 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: combinatorial game, graph labeling, labeling game, maker-breaker game, edge-sum distinguishing game 
@article{DMGT_2024_44_4_a11,
     author = {de Oliveira, Deise L. and Artigas, Danilo and Dantas, Simone and Luiz, At{\'\i}lio G.},
     title = {On the edge-sum distinguishing game},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1449--1469},
     year = {2024},
     volume = {44},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a11/}
}
TY  - JOUR
AU  - de Oliveira, Deise L.
AU  - Artigas, Danilo
AU  - Dantas, Simone
AU  - Luiz, Atílio G.
TI  - On the edge-sum distinguishing game
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1449
EP  - 1469
VL  - 44
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a11/
LA  - en
ID  - DMGT_2024_44_4_a11
ER  - 
%0 Journal Article
%A de Oliveira, Deise L.
%A Artigas, Danilo
%A Dantas, Simone
%A Luiz, Atílio G.
%T On the edge-sum distinguishing game
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1449-1469
%V 44
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a11/
%G en
%F DMGT_2024_44_4_a11
de Oliveira, Deise L.; Artigas, Danilo; Dantas, Simone; Luiz, Atílio G. On the edge-sum distinguishing game. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1449-1469. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a11/

[1] 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

[2] E. Boudreau, B. Hartnell, K. Schmeisser and J. Whiteley, A game based on vertex-magic total labelings, Australas. J. Combin. 29 (2004) 67–73.

[3] 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

[4] 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.

[5] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2022) #DS6. https://doi.org/10.37236/27

[6] 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

[7] B. Hartnell and D. Rall, A vertex-magic edge labeling game, Congr. Numer. 161 (2003) 163–167.

[8] N. Hartsfield and G. Ringel, Pearls in Graph Theory (Academic Press, Inc., San Diego, 1990).

[9] 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

[10] B. Liu and X. Zhang, On harmonious labelings of graphs, Ars Combin. 36 (1993) 315–326.

[11] 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

[12] J. Sedláček, Problem 27, in: Theory of Graphs and Its Applications, Proc. Symp. Smolenice 1963, (Nakl. CSAV, Praha 1963) 163–164.

[13] 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

[14] Zs. Tuza, Graph labeling games, Electron. Notes Discrete Math. 60 (2017) 61–68. https://doi.org/10.1016/j.endm.2017.06.009