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

DOI10.1016/J.AMC.2018.09.056zbMATH Open1428.05261arXiv1805.05204OpenAlexW2799329590WikidataQ129096450 ScholiaQ129096450MaRDI QIDQ2008185FDOQ2008185

Authors: Marcin Anholcer, Sylwia Cichacz, Jakub Przybyło 

Publication date: 22 November 2019

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Abstract: We investigate the extit{group irregularity strength}, $s_g(G)$, of a graph, i.e. the least integer $k$ such that taking any Abelian group $mathcalG$ of order $k$, there exists a function $f:E(G)ightarrowmathcalG$ 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 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: $Delta(G)+mcol(G)-1$ (where $mcol(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.

Full work available at URL: https://arxiv.org/abs/1805.05204

Recommendations

• Group irregularity strength of connected graphs
• Note on group irregularity strength of disconnected graphs
• Note on the group edge irregularity strength of graphs
• Group irregular labelings of disconnected graphs
• Linear bound on the irregularity strength and the total vertex irregularity strength of graphs

zbMATH Keywords

abelian grouparboricityirregularity strengthcoloring numbersum chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• On vertex-coloring 13-edge-weighting
• Edge weights and vertex colours
• Vertex-colouring edge-weightings
• Degree constrained subgraphs
• Title not available (Why is that?)
• Decomposition of Finite Graphs Into Forests
• Vertex-coloring edge-weightings: towards the 1-2-3-conjecture
• Group sum chromatic number of graphs
• A Tight Bound on the Irregularity Strength of Graphs
• Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties
• Irregularity strength of trees
• A new upper bound for the irregularity strength of graphs
• Irregular Assignments of Trees and Forests
• On the irregularity strength of dense graphs
• Nowhere-zero 6-flows
• On chromatic number of graphs and set-systems
• The 3-flow conjecture, factors modulo \(k\), and the 1-2-3-conjecture
• Claw‐decompositions and tutte‐orientations
• On modular edge-graceful graphs
• Title not available (Why is that?)
• An iterative approach to graph irregularity strength
• Note on group irregularity strength of disconnected graphs
• Group irregularity strength of connected graphs
• Group irregular labelings of disconnected graphs
• Nowhere-zero modular edge-graceful graphs

Cited In (5)

• Group sum chromatic number of graphs
• Note on group irregularity strength of disconnected graphs
• Group irregular labelings of disconnected graphs
• Group irregularity strength of connected graphs
• Realization of digraphs in Abelian groups and its consequences

This page was built for publication: Linear bounds on nowhere-zero group irregularity strength and nowhere-zero group sum chromatic number of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2008185)