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

摘要

We investigate the group irregularity strength, sg(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 sg(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 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: Δ(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 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.