Open Collections

Bounds for the distinguishing index of finite graphs

Banff International Research Station for Mathematical Innovation and Discovery

The distinguishing index $D'(G)$ of a graph $G$ is the least number of colours in an edge colouring that breaks all nontrivial automorphisms of $G$. This invariant is defined only for graphs with at most one isolated vertex and without $K_2$ as a component (we call them admissible graphs). The general upper bound for connected admissible graphs is $D'(G)\leq \Delta(G)$ except for small cycles $C_3,C_4,C_5$. Moreover, it was proved by the second author that the equality holds only for cycles of length at least six, symmetric and bisymmetric trees and for two small graphs $K_4,K_{3,3}$. Recently, we proved with Imrich and Woźniak that $$D'(G)\leq \left\lceil\sqrt{\Delta(G)}\right \rceil+1$$ for every connected graph of order at least seven and without pendant edges. There are classes of graphs with the distinguishing index at most two (perhaps with few known exceptions). For instance, traceable graphs, claw-free graphs, Cartesian powers of connected graphs, and 3-connected planar graphs (the latter result was recently proved by PilŠniak and Tucker). A number of open problems will be formulated. Coauthor: Monika PilŠniak

Mathematics; Combinatorics; Group theory and generalizations; Discrete mathematics

video/mp4

Author affiliation: AGH University of Science and Technology

2019-03-17

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/68825

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/