Relationship between the distinguishing index, minimum degree and maximum degree of graphs

Abstract: Let

d e l t a

and

D e l t a

be the minimum and the maximum degree of the vertices of a simple connected graph

G

, respectively. The distinguishing index of a graph

G

, denoted by

D^{'} (G)

, is the least number of labels in an edge labeling of

G

not preserved by any non-trivial automorphism. Motivated by a conjecture by Pil'sniak (2017) that implies that for any

2

-connected graph

D^{'} (G) l e q l c e i l s q r t D e l t a (G) c e i l + 1

, we prove that for any graph

G

with

d e l t a g e q 2

,

D^{'} (G) l e q l c e i l s q r t [d e l t a] D e l t a c e i l + 1

. Also, we show that the distinguishing index of

k

-regular graphs is at most

2

, for any

k g e q 5

.

This page was built for publication: Relationship between the distinguishing index, minimum degree and maximum degree of graphs