Geodesic
The Distinguishing Number and Distinguishing Index of the Lexicographic Product of Two Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 853-865.

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

The distinguishing number (index) D(G) (D′(G)) of a graph G is the least integer d such that G has a vertex labeling (edge labeling) with d labels that is preserved only by the trivial automorphism. The lexicographic product of two graphs G and H, G[H] can be obtained from G by substituting a copy Hu of H for every vertex u of G and then joining all vertices of Hu with all vertices of Hv if uv ∈ E(G). In this paper we obtain some sharp bounds for the distinguishing number and the distinguishing index of the lexicographic product of two graphs. As consequences, we prove that if G is a connected graph with Aut(G[G]) = Aut(G)[Aut(G)], then for every natural number k, D(G) ≤ D(Gk) ≤ D(G) + k − 1 and all lexicographic powers of G, Gk (k ≥ 2) can be distinguished by two edge labels, where Gk = G[G[. . . ]].
Keywords: distinguishing index, distinguishing number, lexicographic 
@article{DMGT_2018_38_3_a14,
     author = {Alikhani, Saeid and Soltani, Samaneh},
     title = {The {Distinguishing} {Number} and {Distinguishing} {Index} of the {Lexicographic} {Product} of {Two} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {853--865},
     publisher = {mathdoc},
     volume = {38},
     number = {3},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a14/}
}
TY  - JOUR
AU  - Alikhani, Saeid
AU  - Soltani, Samaneh
TI  - The Distinguishing Number and Distinguishing Index of the Lexicographic Product of Two Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 853
EP  - 865
VL  - 38
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a14/
LA  - en
ID  - DMGT_2018_38_3_a14
ER  - 
%0 Journal Article
%A Alikhani, Saeid
%A Soltani, Samaneh
%T The Distinguishing Number and Distinguishing Index of the Lexicographic Product of Two Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 853-865
%V 38
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a14/
%G en
%F DMGT_2018_38_3_a14
Alikhani, Saeid; Soltani, Samaneh. The Distinguishing Number and Distinguishing Index of the Lexicographic Product of Two Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 853-865. http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a14/

[1] M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996) #R18.

[2] S. Alikhani and S. Soltani, Distinguishing number and distinguishing index of certain graphs, Filomat 31 (2017) 4393–4404. doi:10.2298/FIL1714393A

[3] E. Bird, G. Curtis and D.J. Kleitman, Automorphisms of lexicographic products, Discrete Math. 11 (1975) 191-198. doi:10.1016/0012-365X(75)90036-9

[4] M. Chan, The distinguishing number of the direct product and wreath product action, J. Algebraic Combin. 24 (2006) 331–345. doi:10.1007/s10801-006-0006-7

[5] A. Gorzkowska, R. Kalinowski and M. Pilśniak, The distinguishing index of the Cartesian product of finite graphs, Ars Math. Contemp. 12 (2017) 77–87.

[6] F. Harary, On the group of the composition of two graphs, Duke Math. J. 26 (1959) 29–34. doi:10.1215/S0012-7094-59-02603-1

[7] R. Kalinowski and M. Pilśniak, Distinguishing graphs by edge colourings, European J. Combin. 45 (2015) 124–131. doi:10.1016/j.ejc.2014.11.00

[8] S. Klav̌zar and X. Zhu, Cartesian powers of graphs can be distinguished by two labels, European J. Combin. 28 (2007) 303–310. doi:10.1016/j.ejc.2005.07.001

[9] F. Michael and I. Garth, Distinguishing colorings of Cartesian products of complete graphs, Discrete Math. 308 (2008) 2240–2246. doi:10.1016/j.disc.2007.04.070

[10] G. Sabidussi, The composition of graphs, Duke Math. J. 26 (1959) 693–696. doi:10.1215/S0012-7094-59-02667-5