Szczegóły publikacji
Opis bibliograficzny
Extremal graphs for the distinguishing index / Rafał KALINOWSKI, Monika PILŚNIAK // Discrete Mathematics ; ISSN 0012-365X. — 2022 — vol. 345 iss. 8 art. no. 112905, s. 1–11. — Bibliogr. s. 11, Abstr. — Publikacja dostępna online od: 2022-04-06
Autorzy (2)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 139941 |
|---|---|
| Data dodania do BaDAP | 2022-04-26 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2022.112905 |
| Rok publikacji | 2022 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Mathematics |
Abstract
The distinguishing index D′(G) of a graph G is the least number of colours in an edge colouring, not necessarily proper, such that the identity is the only automorphism preserving it. This invariant is not defined for graphs having K2 as a component or more than one isolated vertex, and all other graphs we call admissible. In this paper we consider the following Turán-type problem: given an integer d≥2, what is a maximum size of an admissible graph G of order n such that D′(G)>d? The main result is the following theorem. If d≥2 and G is an admissible graph of order n≥d+4 and size ‖G‖>(n−d−12)+d+1, then D′(G)≤d except for a few small graphs of order at most 7. We also exhibit all extremal graphs of order n≥9, that is, graphs G with ‖G‖=(n−d−12)+d+1 and D′(G)>d.