- Tytuł:
- On the edge-sum distinguishing game
- Autorzy:
-
de Oliveira, Deise L.
Artigas, Danilo
Dantas, Simone
Luiz, Atílio G. - Tematy:
-
graph labeling
labeling game
maker-breaker game
edge-sum distinguishing game
combinatorial game - Pokaż więcej
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Powiązania:
- https://bibliotekanauki.pl/articles/60017700.pdf Link otwiera się w nowym oknie
- Opis:
- 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.
- Dostawca treści:
- Biblioteka Nauki
Artykuł