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

Document Type : Research Paper

Authors

1 Department of Mathematics‎, ‎Yazd University‎, ‎89195-741‎, ‎Yazd‎, ‎Iran.

2 Department of Mathematics‎, ‎Yazd University‎, ‎Yazd‎, ‎Iran.

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‎.

Keywords

Main Subjects

References

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.
Bulletin of the Iranian Mathematical Society
Volume 43, Issue 7
December 2017
Pages 2471-2482

Files

History

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

Share

How to cite

Statistics