Szczegóły publikacji
Opis bibliograficzny
Improving upper bounds for the distinguishing index / Monika PILŚNIAK // Ars Mathematica Contemporanea ; ISSN 1855-3966. — 2017 — vol. 13 no. 2, s. 259–274. — Bibliogr. s. 273–274, Abstr. — Publikacja dostępna online od: 2017-03-06
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 104846 |
|---|---|
| Data dodania do BaDAP | 2017-04-25 |
| Tekst źródłowy | URL |
| DOI | 10.26493/1855-3974.981.ff0 |
| Rok publikacji | 2017 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | Ars Mathematica Contemporanea |
Abstract
The distinguishing index of a graph G, denoted by D' (G), is the least number of colours in an edge colouring of G not preserved by any non-trivial automorphism. We characterize all connected graphs G with D' (G) >= Delta(G). We show that D'(G) <= 2 if G is a traceable graph of order at least seven, and D'(G) <= 3 if G is either claw-free or 3-connected and planar. We also investigate the Nordhaus-Gaddum type relation: 2 <= D'(G) + D'((G) over bar) <= max { Delta(G); Delta((G) over bar)} + 2 and we confirm it for some classes of graphs.