Group irregularity strength of connected graphs
Marcin Anholcer, Sylwia Cichacz, Martin Milanič · Journal of Combinatorial Optimization · 2013
We investigate the group irregularity strength ( $$s_g(G)$$ ) of graphs, that is, we find the minimum value of $$s$$ such that for any Abelian group $$\mathcal G $$ of order $$s$$ , there exists a function $$f:E(G)\rightarrow \mathcal G $$ such that the sums of edge labels at every vertex are distinct. We prove that for any connected graph $$G$$ of order at least $$3$$ , $$s_g(G)=n$$ if $$n e 4k+2$$ and $$s_g(G)\le n+1$$ otherwise, except the case of an infinite family of stars. We also prove that the presented labelling algorithm is linear with respect to the order of the graph.