We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Bounds for the distinguishing index of finite graphs

Formal Metadata

Title
Bounds for the distinguishing index of finite graphs
Title of Series
Number of Parts
19
Author
Contributors
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
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 K2 as a component (we call them admissible graphs). The general upper bound for connected admissible graphs is D′(G)≤Δ(G) except for small cycles C3,C4,C5. 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 K4,K3,3. Recently, we proved with Imrich and Woźniak that D′(G)≤⌈Δ(G)√⌉+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.