Linear bounds on nowhere-zero group irregularity strength and nowhere-zero group sum chromatic number of graphs

Marcin Anholcer , Sylwia Cichacz , Jakub Przybyło

Abstract

We investigate the group irregularity strength, sg(G), of a graph, i.e., the least integer k such that taking any Abelian group of order k, there exists a function so that the sums of edge labels incident with every vertex are distinct. So far the best upper bound on sg(G) for a general graph G was exponential in where n is the order of G and c denotes the number of its components. In this note we prove that sg(G) is linear in n, namely not greater than 2n. 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 vertex. 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: (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 additionally 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.
Author Marcin Anholcer (WIiGE / KBO)
Marcin Anholcer,,
- Department of Operations Research
, Sylwia Cichacz - AGH University of Science and Technology
Sylwia Cichacz,,
-
, Jakub Przybyło - AGH University of Science and Technology (AGH)
Jakub Przybyło,,
-
Journal seriesApplied Mathematics and Computation, ISSN 0096-3003, e-ISSN 1873-5649, (N/A 100 pkt)
Issue year2019
Vol343
Pages149-155
Publication size in sheets0.5
Keywords in EnglishIrregularity strength, Sum chromatic number, Coloring number, Arboricity, Abelian group
ASJC Classification2604 Applied Mathematics; 2605 Computational Mathematics
DOIDOI:10.1016/j.amc.2018.09.056
URL https://www.sciencedirect.com/science/article/abs/pii/S009630031830835X
Languageen angielski
Score (nominal)100
Score sourcejournalList
ScoreMinisterial score = 100.0, 04-03-2020, ArticleFromJournal
Publication indicators WoS Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.544; WoS Impact Factor: 2018 = 3.092 (2) - 2018=2.429 (5)
Citation count*1 (2020-06-25)
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?