Geodesic
On the edge-sum distinguishing game
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1449-1469

Voir la notice de l'article provenant de la source Library of Science

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},
     publisher = {mathdoc},
     volume = {44},
     number = {4},
     year = {2024},
     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
PB  - mathdoc
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
%I mathdoc
%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/