The Distinguishing Index of Infinite Graphs

The  distinguishing index $D^\prime(G)$ of a graph $G$ is the least cardinal $d$ such that $G$ has an edge colouring with $d$ colours that is only preserved by the trivial automorphism. This is similar to the notion of the distinguishing number $D(G)$ of a graph $G$, which is defined with respect to...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2015-03, Vol.22 (1)
Main Authors: Broere, Izak, Pilśniak, Monika
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The  distinguishing index $D^\prime(G)$ of a graph $G$ is the least cardinal $d$ such that $G$ has an edge colouring with $d$ colours that is only preserved by the trivial automorphism. This is similar to the notion of the distinguishing number $D(G)$ of a graph $G$, which is defined with respect to vertex colourings.We derive several bounds for infinite graphs, in particular, we prove the general bound $D^\prime(G)\leq\Delta(G)$ for an arbitrary infinite graph. Nonetheless,  the distinguishing index is at most two for many countable graphs, also for the infinite random graph and for uncountable tree-like graphs.We also investigate the concept of the motion of edges and its relationship with the Infinite Motion Lemma. 
ISSN:1077-8926
1077-8926
DOI:10.37236/3933