The Distinguishing Number and Distinguishing Index of the Lexicographic Product of Two Graphs

摘要

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 H_(u) of H for every vertex u of G and then joining all vertices of H_(u) with all vertices of H_(v) 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 ( G~(k) ) ≤ D ( G ) + k ? 1 and all lexicographic powers of G , G~(k) ( k ≥ 2) can be distinguished by two edge labels, where G~(k) = G [ G [. . ]].