Edge-Distinguishing Index of a Graph
Rafał Kalinowski, Mariusz Woźniak · Graphs and Combinatorics · 2013
We introduce a concept of edge-distinguishing colourings of graphs. A closed neighbourhood of an edge $${e\in 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 1 and e 2 if there exists an isomorphism φ of N[e 1] onto N[e 2] such that φ(e 1) = e 2 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.