Distinguishing number and distinguishing index of natural and fractional powers of graphs

Abstract

The distinguishing number (index) $D(G)$ ($D^{\prime }(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\in \mathbb{N}$, the $n$-subdivision of $G$ is a simple graph $G^{\frac{1}{n}}$ which is constructed by replacing each edge of $G$ with a path of length $n$. The $m^{th}$ 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^{\frac{m}{n}}$ is $m^{th}$ 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⩾3$ with maximum degree $\Delta (G)$, $D(G^{\frac{1}{k}})⩽min\{s:2^k+{\sum }_{n=3}^s{n}^{k-1}⩾\Delta (G)\}$ and for $m⩾3$, $D^{\prime }(G^{\frac{m}{k}})⩽3$.

13 pages