dc.contributor.author |
Broere, Izak
|
|
dc.contributor.author |
Pilsniak, Monika
|
|
dc.date.accessioned |
2015-06-22T13:03:33Z |
|
dc.date.available |
2015-06-22T13:03:33Z |
|
dc.date.issued |
2015-03-30 |
|
dc.description.abstract |
The distinguishing index D0(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 D0(G) 6 (G) for an arbitrary infinite graph. Nonetheless, the distinguish- ing 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. |
en_ZA |
dc.description.librarian |
am2015 |
en_ZA |
dc.description.uri |
http://www.combinatorics.org |
en_ZA |
dc.identifier.citation |
Broere, I & Pilsniak, M 2015, 'The distinguishing index of infinite graphs', The Electronic Journal of Combinatorics, vol. 22, no. 1, pp. 1-10. |
en_ZA |
dc.identifier.issn |
1077-8926 (online) |
|
dc.identifier.uri |
http://hdl.handle.net/2263/45651 |
|
dc.language.iso |
en |
en_ZA |
dc.publisher |
Australian National University, Research School of Computer Science |
en_ZA |
dc.rights |
Research School of Computer Science at the Australian National University |
en_ZA |
dc.subject |
Distinguishing index |
en_ZA |
dc.subject |
Automorphism |
en_ZA |
dc.subject |
Infinite graph |
en_ZA |
dc.subject |
Countable graph |
en_ZA |
dc.subject |
Edge colouring |
en_ZA |
dc.subject |
Infinite Motion Lemma |
en_ZA |
dc.title |
The distinguishing index of infinite graphs |
en_ZA |
dc.type |
Article |
en_ZA |