Szczegóły publikacji
Opis bibliograficzny
Linear bounds on nowhere-zero group irregularity strength and nowhere-zero group sum chromatic number of graphs / Marcin Anholcer, Sylwia CICHACZ, Jakub PRZYBYŁO // Applied Mathematics and Computation ; ISSN 0096-3003. — 2019 — vol. 343, s. 149–155. — Bibliogr. s. 155, Abstr. — Publikacja dostępna online od: 2018-10-12. — S. Cichacz - dod. afiliacja: University of Primorska, Slovenia
Autorzy (3)
- Anholcer Marcin
- AGHCichacz-Przeniosło Sylwia
- AGHPrzybyło Jakub
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 117524 |
|---|---|
| Data dodania do BaDAP | 2018-10-26 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.amc.2018.09.056 |
| Rok publikacji | 2019 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Applied Mathematics and Computation |
Abstract
We investigate the group irregularity strength , s g ( G ), of a graph, i.e., the least integer k such that taking any Abelian group G of order k , there exists a function f : E ( G ) → G so that the sums of edge labels incident with every vertex are distinct. So far the best upper bound on s g ( G ) for a general graph G was exponential in n − c , where n is the order of G and c denotes the number of its components. In this note we prove that s g ( G ) is linear inn, namely not greater than 2 n . In fact, we prove a stronger result, as we additionally forbid the identity element of a group to be an edge label or the sum of labels around a ver- tex. We consider also locally irregular labelings where we require only sums of adjacent vertices to be distinct. For the corresponding graph invariant we prove the general upper bound: ( G ) + col ( G ) − 1 (where col( G ) is the coloring number of G ) in the case when we do not use the identity element as an edge label, and a slightly worse one if we addition- ally forbid it as the sum of labels around a vertex. In the both cases we also provide a sharp upper bound for trees and a constant upper bound for the family of planar graphs.
