Szczegóły publikacji
Opis bibliograficzny
The distinguishing index of infinite graphs / Izak Broere, Monika PILŚNIAK // The Electronic Journal of Combinatorics [Dokument elektroniczny]. — Czasopismo elektroniczne ; ISSN 1077-8926. — 2015 — vol. 22 iss. 1 art. no. P1.78, s. 1–10. — Bibliogr. s. 10, Abstr.
Autorzy (2)
- Broere Izak
- AGHPilśniak Monika
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 88786 |
|---|---|
| Data dodania do BaDAP | 2015-04-25 |
| Tekst źródłowy | URL |
| Rok publikacji | 2015 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | The Electronic Journal of Combinatorics |
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.
