Distinguishing number and distinguishing index of natural and fractional powers of graphs
Saeid Alikhani, Samaneh Soltani · arXiv (Cornell University) · 2016
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 \\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 \\geqslant 3$ with maximum degree $\\Delta (G)$, $D(G^{\\frac{1}{k}})\\leqslant min\\{s: 2^k+\\sum^s_{n=3}n^{k-1}\\geqslant \\Delta (G)\\}$ and for $m\\geqslant 3$, $D'(G^{\\frac{m}{k}})\\leqslant 3$.