Edge-Distinguishing of Star-Free Graphs

Abstract

The distinguishing index $D'(G)$ of a graph $G$ is the least number $k$ such that $G$ has an edge colouring with $k$ colours that is only preserved by the trivial automorphism. Pilśniak proved that a connected, claw-free graph has the distingushing index at most three. In this paper, we show that the distingushing index of a connected, claw-free graph with at least six vertices is bounded from above by two. We also consider more general graphs in this sense. Namely, we prove that if $G$ is a connected, $K_{1,s}$-free graph of order at least six, then $D'(G) \leq s-1$.