Group irregularity strength of connected graphs
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\ne 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.
irregularity strength abelian group graph labelling 05c15 05c78