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

Author(s):
Article Type:
Research/Original Article (دارای رتبه معتبر)
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∈Ný, ýthe n-subdivision of G is a simple graph G1n 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 in G.ý
ý The fractional power of Gý, ýis the mth power of the n-subdivision of Gý, ýi.e.ý, ý(G1n)m or n-subdivision of m-th power of Gý, ýi.e.ý, ý(Gm)1ný. ý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⩾3 with maximum degree Δ(G)ý, ýand for k⩾2ý, ýD(G1k)⩽⌈Δ(G)−−−−−√k⌉ý. ýFinally we prove that for m⩾2ý, ýthe fractional power of Gý, ýi.e.ý, ý(G1k)m and (Gm)1k are distinguishedý ý by at most three edge labelsý.
Language:
English
Published:
Bulletin of Iranian Mathematical Society, Volume:43 Issue: 7, 2017
Pages:
2471 to 2482
https://www.magiran.com/p1850926  
سامانه نویسندگان
  • Alikhani، Saeid
    Corresponding Author (1)
    Alikhani, Saeid
    Professor Department of Mathematics, Yazd University, University of Yazd, Yazd, Iran
اطلاعات نویسنده(گان) توسط ایشان ثبت و تکمیل شده‌است. برای مشاهده مشخصات و فهرست همه مطالب، صفحه رزومه را ببینید.
مقالات دیگری از این نویسنده (گان)