Szczegóły publikacji
Opis bibliograficzny
The optimal general upper bound for the distinguishing index of infinite graphs / Monika PILŚNIAK, Marcin STAWISKI // Journal of Graph Theory ; ISSN 0364-9024. — 2020 — vol. 93 iss. 4, s. 463-469. — Bibliogr. s. 469, Abstr. — Publikacja dostępna online od: 2019-08-16
Autorzy (2)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 128906 |
|---|---|
| Data dodania do BaDAP | 2020-06-16 |
| Tekst źródłowy | URL |
| DOI | 10.1002/jgt.22496 |
| Rok publikacji | 2020 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Journal of Graph Theory |
Abstract
The distinguishing index 𝐷′(𝐺) of a graph 𝐺 is the least cardinal number 𝑑 such that 𝐺 has an edge‐coloring with 𝑑 colors, which is preserved only by the trivial automorphism. We prove a general upper bound 𝐷′(𝐺)≤Δ−1 for any connected infinite graph 𝐺 with finite maximum degree Δ≥3. This is in contrast with finite graphs since for every Δ≥3 there exist infinitely many connected, finite graphs 𝐺 with 𝐷′(𝐺)=Δ. We also give examples showing that this bound is sharp for any maximum degree Δ.
