Edge-Distinguishing Index of a Graph

We introduce a concept of edge-distinguishing colourings of graphs. A closed neighbourhood of an edge ({ein E(G)}) is a subgraph N[e] induced by e and all edges adjacent to it. We say that a colouring c : E(G) → C does not distinguish two edges e ₁ and e ₂ if there exists an isomorphism φ of N[e ₁] onto N[e ₂] such that φ(e ₁) = e ₂ and φ preserves colours of c. An edge-distinguishing index of a graph G is the minimum number of colours in a proper colouring which distinguishes every two distinct edges of G. We determine the edge-distinguishing index for cycles, paths and complete graphs.