Distinguishing number and distinguishing index of lexicographic product of two graphs

preprint2016arXivOpen access

Abstract

The distinguishing number (index) D(G)D(G) (D′(G)D'(G)) of a graph GG is the least integer dd such that GG has an vertex labeling (edge labeling) with dd labels that is preserved only by a trivial automorphism. The lexicographic product of two graphs GG and HH, G[H]G[H] can be obtained from GG by substituting a copy HuH_u of HH for every vertex uu of GG and then joining all vertices of HuH_u with all vertices of HvH_v if uv∈E(G)uv\in E(G). In this paper we obtain some sharp bounds for the distinguishing number and the distinguishing index of lexicographic product of two graphs. As consequences, we prove that if GG is a connected graph with a special condition on automorphism group of G[G]G[G] and D(G)>1D(G)> 1, then for every natural kk, D(G)≤D(Gk)≤D(G)+k−1D(G)\leq D(G^k)\leq D(G)+k-1, where Gk=G[G[...]]G^k=G[G[...]]. Also we prove that all lexicographic powers of GG, GkG^k (k≥2k\geq 2) can be distinguished by at most two edge labels.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.