Alikhani, S., Soltani, S. (2017). Distinguishing number and distinguishing index of natural and fractional powers of graphs. Bulletin of the Iranian Mathematical Society, 43(7), 2471-2482.

S. Alikhani; S. Soltani. "Distinguishing number and distinguishing index of natural and fractional powers of graphs". Bulletin of the Iranian Mathematical Society, 43, 7, 2017, 2471-2482.

Alikhani, S., Soltani, S. (2017). 'Distinguishing number and distinguishing index of natural and fractional powers of graphs', Bulletin of the Iranian Mathematical Society, 43(7), pp. 2471-2482.

Alikhani, S., Soltani, S. Distinguishing number and distinguishing index of natural and fractional powers of graphs. Bulletin of the Iranian Mathematical Society, 2017; 43(7): 2471-2482.

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

^{1}Department of Mathematics, Yazd University, 89195-741, Yazd, Iran.

^{2}Department of Mathematics, Yazd University, Yazd, Iran.

Receive Date: 04 October 2016,
Revise Date: 18 September 2017,
Accept Date: 19 September 2017

Abstract

The distinguishing number (resp. index) $D(G)$ ($D'(G)$) of a graph $G$ is the least integer $d$
such that $G$ has an vertex labeling (resp. 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 in $G$.
The fractional power of $G$, is the $m^{th}$ power of the $n$-subdivision of $G$, i.e., $(G^{\frac{1}{n}})^m$ or $n$-subdivision of $m$-th power of $G$, i.e., $(G^m)^{\frac{1}{n}}$. In this paper we study the distinguishing number and the distinguishing index of the natural and the fractional powers of $G$. We show that the natural powers more than one of a graph are distinguished by at most three edge labels. We also show that for a connected graph $G$ of order $n \geqslant 3$ with maximum degree $\Delta (G)$, and for $k\geqslant 2$, $D(G^{\frac{1}{k}})\leqslant \lceil \sqrt[k]{\Delta (G)} \rceil$. Finally we prove that for $m\geqslant 2$, the fractional power of $G$, i.e., $(G^{\frac{1}{k}})^m$ and $(G^m)^{\frac{1}{k}}$ are distinguished by at most three edge labels.

G. Agnarsson and M.M. Halldorsson, Coloring powers of planar graphs, SIAM J. Discrete Math. 16 (2003), no. 4, 651--662.

M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996), no. 11, Research Paper 18, 17 pages.

S. Alikhani and S. Soltani, Distinguishing number and distinguishing index of certain graphs, Filomat 31 (2017), no. 14, 4393--4404.

X. An and B. Wu, The wiener index of the kth power of a graph, Appl. Math. Lett. 21 (2008), no. 5, 436--440.

M. Chan, The distinguishing number of the augmented cube and hypercube powers, Discrete Math. 308 (2008), no. 11, 2330--2336.

G. Chartrand, S.F. Kapoor and D.R. Lick, n-hamiltonian graphs, J. Combin. Theory 9 (1970), no. 3, 308--312.

R. Faudree, E. Flandrin and Z. Ryjacek, Claw-free graphs--a survey, Discrete Math. 164 (1997), no. 1-3, 87--147.

R.H. Hammack, W. Imrich, S. Klavzar, W. Imrich and S. Klavzar, Handbook of Product Graphs, CRC Press, Boca Raton, 2011.

A.M. Hobbs, Some hamiltonian results in powers of graphs, J. Res. Nat. Bur. Standards Sect. B 77 (1973) 1--10.

W. Imrich, J. Jerebic and S. Klavzar, The distinguishing number of cartesian products of complete graphs, European J. Combin. 29 (2008), no. 4, 922--929.

M.N. Iradmusa, On colorings of graph fractional powers, Discrete Math. 310 (2010), no. 10, 1551--1556.

M.N. Iradmusa, Domination number of graph fractional powers, Bull. Iranian Math. Soc. 40 (2014), no. 6, 1479--1489.

R. Kalinowski and M. Pilsniak, Distinguishing graphs by edge-colourings, European J. Combin. 45 (2015), 124--131.

R. Kalinowski, M. Pilsniak and M. Wozniak, Distinguishing graphs by total colourings, Ars Math. Contemp. 11 (2015), no. 1, 79--89.

S. Klavzar and X. Zhu, Cartesian powers of graphs can be distinguished by two labels, European J. Combin. 28 (2007), no. 1, 303--310.

D. Kral', Coloring powers of chordal graphs, SIAM J. Discrete Math. 18 (2004), no. 3, 451--461.

O. Ore, Hamiltonian connected graphs, J. Math. Pures Appl. 42 (1963), 121--127.

M. Pilsniak, Improving upper bounds for the distinguishing index, Ars Math. Contemp. 13 (2017), no. 2, 259--274.

M. Sekanina, On an ordering of the vertices of a graph, Casopis pro pestovan matematiky 88 (1963), no. 3, 265--282.