2016/04/13 by Alikhani, Saeid, Soltani, Samaneh · 1 citation
#05C15 #05E18 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1604.03839
The distinguishing number (index) D(G) (D'(G)) of a graph G is the least integer d such that G has an vertex labeling (edge labeling) with d labels that is preserved only by a trivial automorphism. For any n ∈ ℕ, the n-subdivision of G is a simple graph G(1)/(n) which is constructed by replacing each edge of G with a path of length n. The mth power of G, is a graph with same set of vertices of G and an edge between two vertices if and only if there is a path of length at most m between them. The fractional power of G, denoted by G(m)/(n) is mth power of the n-subdivision of G or n-subdivision of m-th power of G. In this paper we study the distinguishing number and distinguishing index of natural and fractional powers of G. We show that the natural powers more than two of a graph distinguished by three edge labels. Also we show that for a connected graph G of order n \geqslant 3 with maximum degree Δ(G), D(G(1)/(k))\leqslant min\s: 2k+∑sn=3nk-1\geqslant Δ(G)\ and for m\geqslant 3, D'(G(m)/(k))\leqslant 3.