Geodesic
A New Game Invariant of Graphs: the Game Distinguishing Number
Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 1.

Voir la notice de l'article provenant de la source Episciences

The distinguishing number of a graph $G$ is a symmetry related graph invariant whose study started two decades ago. The distinguishing number $D(G)$ is the least integer $d$ such that $G$ has a $d$-distinguishing coloring. A distinguishing $d$-coloring is a coloring $c:V(G)\rightarrow\{1,...,d\}$ invariant only under the trivial automorphism. In this paper, we introduce a game variant of the distinguishing number. The distinguishing game is a game with two players, the Gentle and the Rascal, with antagonist goals. This game is played on a graph $G$ with a set of $d\in\mathbb N^*$ colors. Alternately, the two players choose a vertex of $G$ and color it with one of the $d$ colors. The game ends when all the vertices have been colored. Then the Gentle wins if the coloring is distinguishing and the Rascal wins otherwise. This game leads to define two new invariants for a graph $G$, which are the minimum numbers of colors needed to ensure that the Gentle has a winning strategy, depending on who starts. These invariants could be infinite, thus we start by giving sufficient conditions to have infinite game distinguishing numbers. We also show that for graphs with cyclic automorphisms group of prime odd order, both game invariants are finite. After that, we define a class of graphs, the involutive graphs, for which the game distinguishing number can be quadratically bounded above by the classical distinguishing number. The definition of this class is closely related to imprimitive actions whose blocks have size $2$. Then, we apply results on involutive graphs to compute the exact value of these invariants for hypercubes and even cycles. Finally, we study odd cycles, for which we are able to compute the exact value when their order is not prime. In the prime order case, we give an upper bound of $3$. 
@article{DMTCS_2017_19_1_a1,
     author = {Gravier, Sylvain and Meslem, Kahina and Schmidt, Simon and Slimani, Souad},
     title = {A {New} {Game} {Invariant} of {Graphs:} the {Game} {Distinguishing} {Number}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-1-2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-2/}
}
TY  - JOUR
AU  - Gravier, Sylvain
AU  - Meslem, Kahina
AU  - Schmidt, Simon
AU  - Slimani, Souad
TI  - A New Game Invariant of Graphs: the Game Distinguishing Number
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-2/
DO  - 10.23638/DMTCS-19-1-2
LA  - en
ID  - DMTCS_2017_19_1_a1
ER  - 
%0 Journal Article
%A Gravier, Sylvain
%A Meslem, Kahina
%A Schmidt, Simon
%A Slimani, Souad
%T A New Game Invariant of Graphs: the Game Distinguishing Number
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-2/
%R 10.23638/DMTCS-19-1-2
%G en
%F DMTCS_2017_19_1_a1
Gravier, Sylvain; Meslem, Kahina; Schmidt, Simon; Slimani, Souad. A New Game Invariant of Graphs: the Game Distinguishing Number. Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 1. doi : 10.23638/DMTCS-19-1-2. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-2/

Cité par Sources :