The distinguishing index of the Cartesian product of countable graphs

Izak Broere, Monika Pilśniak

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 preserved only by the trivial automorphism.

We derive some bounds for this parameter for infinite graphs. In particular, we investigate the distinguishing index of the Cartesian product of countable graphs.

Finally, we prove that Dʹ(K20) = 2, where K20 is the infinite dimensional hypercube.


Keywords


Distinguishing index, automorphism, infinite graph, edge colouring, infinite dimensional hypercube

Full Text:

PDF ABSTRACTS (EN/SI)


ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications