Szczegóły publikacji
Opis bibliograficzny
Nordhaus-Gaddum type inequalities for the distinguishing index / Monika PILŚNIAK // Ars Mathematica Contemporanea ; ISSN 1855-3966. — 2021 — vol. 20 no. 2, s. 223–231. — Bibliogr. s. 230–231, Abstr. — Publikacja dostępna online od: 2021-11-03
Autor
Słowa kluczowe
Dane bibliometryczne
ID BaDAP | 137672 |
---|---|
Data dodania do BaDAP | 2021-11-23 |
Tekst źródłowy | URL |
DOI | 10.26493/1855-3974.2173.71a |
Rok publikacji | 2021 |
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 nontrivial automorphism. This invariant is defined for any graph without K-2 as a connected component and without two isolated vertices, and such a graph is called admissible. We prove the Nordhaus-Gaddum type relation:2 <= D '(G) + D '((G) over bar) <= Delta(G) + 2 for every admissible connected graph G of order |G| >= 7 such that G is also admissible.