Szczegóły publikacji
Opis bibliograficzny
Distant total irregularity strength of graphs via random vertex ordering / Jakub PRZYBYŁO // Discrete Mathematics ; ISSN 0012-365X. — 2018 — vol. 341 iss. 4, s. 1098–1102. — Bibliogr. s. 1102, Abstr. — Publikacja dostępna online od: 2017-11-16
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 117884 |
|---|---|
| Data dodania do BaDAP | 2018-11-10 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2017.10.028 |
| Rok publikacji | 2018 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Mathematics |
Abstract
Let c : V boolean OR E -> {1, 2, ..., k} be a (not necessarily proper) total colouring of a graph G = (V, E) with maximum degree d. Two vertices u, v is an element of V are sum distinguished if they differ with respect to sums of their incident colours, i.e. c(u)+ Sigma(e(sic)u) c(e) not equal c(v)+Sigma(e(sic)u) c(e). The least integer k admitting such colouring c under which every u, v E V at distance 1 <= d(u, v) <= r in G are sum distinguished is denoted by tsr(G). Such graph invariants link the concept of the total vertex irregularity strength of graphs with so-called 1-2-Conjecture, whose concern is the case of r = 1. Within this paper we combine probabilistic approach with purely combinatorial one in order to prove that ts(r)(G) <= (2 + 0(1))Delta(r-1) for every integer r >= 2 and each graph G, thus improving the previously best result: ts(r)(G) <= 3 Delta(r-1) (C) 2017 Elsevier B.V. All rights reserved.
