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/