Abstract | ||
---|---|---|
The distinguishing index D '(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 '(G) <= 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. |
Year | Venue | Keywords |
---|---|---|
2015 | ELECTRONIC JOURNAL OF COMBINATORICS | distinguishing index,automorphism,infinite graph,countable graph,edge colouring,Infinite Motion Lemma |
Field | DocType | Volume |
Graph automorphism,Random regular graph,Discrete mathematics,Combinatorics,Vertex-transitive graph,Line graph,Forbidden graph characterization,Symmetric graph,Universal graph,1-planar graph,Mathematics | Journal | 22.0 |
Issue | ISSN | Citations |
1.0 | 1077-8926 | 2 |
PageRank | References | Authors |
0.44 | 4 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Izak Broere | 1 | 143 | 31.30 |
Monika Pilsniak | 2 | 2 | 0.44 |