Distinguishing graphs by edge-colourings

作者：Kalinowski Rafal^*; Pilsniak Monika

来源：European Journal of Combinatorics, 2015, 45: 124-131.

DOI：10.1016/j.ejc.2014.11.003

We introduce the distinguishing index D'(G) of a graph Gas the least number d such that G has an edge-colouring with d colours that is only preserved by the trivial automorphism. This is an analog to the notion of the distinguishing number D(G) of a graph G, which is defined for colourings of vertices. We obtain a general upper bound D'(G) <= Delta (G) unless G is a small cycle C-3, C-4 or C-5.
We also introduce the distinguishing chromatic index X'(D)(G) defined for proper edge-colourings of a graph G. A correlation with distinguishing vertices by colour walks introduced in Kalinowski et al. (2004) is shown. We prove that X'(D)(G) <= Delta(G) + 1 except for four small graphs C-4, C-4, C-6 and K-3,K-3. It follows that each connected Class 2 graph G admits a minimal proper edge-colouring, i.e., with x'(G) colours, preserved only by the trivial automorphism.

• 出版日期2015-4