Szczegóły publikacji
Opis bibliograficzny
Distant irregularity strength of graphs / Jakub PRZYBYŁO // Discrete Mathematics ; ISSN 0012-365X. — 2013 — vol. 313 iss. 24, s. 2875–2880. — Bibliogr. s. 2880, Abstr.
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 77272 |
|---|---|
| Data dodania do BaDAP | 2013-11-13 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2013.08.031 |
| Rok publikacji | 2013 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Mathematics |
Abstract
Let G = (V, E) be a graph, and let c : V -> {1, 2, . . . , k} be a not necessarily proper edge colouring. The weight, or the weighted degree, of v is an element of V is then defined as w(v) = Sigma(u is an element of N(v)) c(vu). The colouring c is said to be irregular if w(u) not equal w(v) for every two distinct vertices u, v is an element of V. The smallest k for which such a colouring exists is called the irregularity strength of a graph, denoted by s(G). In this paper we further develop the study of irregular colourings, and require that the colouring c provides distinct weights only for vertices at distance at most r. The corresponding parameter is then called the r-distant irregularity strength, and denoted by sr(G). This notion binds the known 1-2-3 Conjecture posed by Karonski Luczak and Thomason, whose objective is s(1) (G), with the irregularity strength, as it is justified to write s(G) = s(infinity)(G) in this context. We prove that for each positive integer r, s(r) (G) <= 6 Delta(r-1). We also investigate a total version of the problem, where given a colouring c : VUE -> {1, 2, . . . , k} of G, we define t(v) = c(v) + Sigma(u is an element of N(u)) c(uv) for v is an element of V. The smallest k for which such a colouring c exists with t(u) not equal t(v) for every pair of distinct vertices at distance at most r in G is called the r-distant total irregularity strength of G, and denoted by ts(r)(G). We prove that tsr (G) <= 3 Delta(r-1) and we discuss that the bounds obtained for both problems are of the right magnitude. This direction of research is inspired by the concept of distant chromatic numbers. The results obtained are also strongly related with the study on the Moore bound. (C) 2013 Elsevier B.V. All rights reserved.
