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

preprint2016arXivOpen access

Abstract

The distinguishing number (index) D(G)D(G) (D′(G)D'(G)) of a graph GG is the least integer dd such that GG has an vertex labeling (edge labeling) with dd labels that is preserved only by a trivial automorphism. For any n∈Nn \in \mathbb{N}, the nn-subdivision of GG is a simple graph G1nG^{\frac{1}{n}} which is constructed by replacing each edge of GG with a path of length nn. The mthm^{th} power of GG, is a graph with same set of vertices of GG and an edge between two vertices if and only if there is a path of length at most mm between them. The fractional power of GG, denoted by GmnG^{\frac{m}{n}} is mthm^{th} power of the nn-subdivision of GG or nn-subdivision of mm-th power of GG. In this paper we study the distinguishing number and distinguishing index of natural and fractional powers of GG. 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 GG of order n⩾3n \geqslant 3 with maximum degree Δ(G)Δ(G), D(G1k)⩽min{s:2k+∑n=3snk−1⩾Δ(G)}D(G^{\frac{1}{k}})\leqslant min\{s: 2^k+\sum^s_{n=3}n^{k-1}\geqslant Δ(G)\} and for m⩾3m\geqslant 3, D′(Gmk)⩽3D'(G^{\frac{m}{k}})\leqslant 3.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.