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

Formale Metadaten

Titel
Bounds for the distinguishing index of finite graphs
Serientitel
Anzahl der Teile
19
Autor
Mitwirkende
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
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.