Paper Info
Title
Edge motion and the distinguishing index.
Abstract
The distinguishing index D′(G) of a graph G is the least number d such that G has an edge colouring with d colours that is preserved only by the trivial automorphism. We investigate the edge motion of a graph with respect to its automorphisms and compare it with the vertex motion. We prove an analog of the Motion Lemma of Russell and Sundaram, and we use it to determine the distinguishing index of powers of complete graphs and of cycles with respect to the Cartesian, direct and strong product.
Year
DOI
Venue
2017
10.1016/j.tcs.2017.02.032
Theoretical Computer Science
Keywords
Field
DocType
Symmetry breaking,Distinguishing index,Motion Lemma,Product graphs
Discrete mathematics,Graph,Combinatorics,Symmetry breaking,Vertex (geometry),Automorphism,Lemma (mathematics),Mathematics,Cartesian coordinate system
Journal
Volume
ISSN
Citations 
678
0304-3975
0
PageRank 
References 
Authors
0.34
7
1
Name
Order
Citations
PageRank
Monika Pilśniak1289.31