# zbMATH — the first resource for mathematics

Group irregularity strength of connected graphs. (English) Zbl 1316.05078
Summary: 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)\to \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\neq 4k+2$$ and $$s_g(G)\leq 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.
Reviewer: Reviewer (Berlin)

##### MSC:
 05C40 Connectivity 05C78 Graph labelling (graceful graphs, bandwidth, etc.)
##### Keywords:
irregularity strength; graph labelling; abelian group
Full Text:
##### References:
  Aigner, M; Triesch, E, Irregular assignments of trees and forests, SIAM J Discret Math, 3, 439-449, (1990) · Zbl 0735.05049  Amar, D; Togni, O, Irregularity strength of trees, Discret Math, 190, 15-38, (1998) · Zbl 0956.05092  Anholcer M, Cichacz S (2013) Group sum chromatic number of graphs, preprint, arXiv:1205.2572v3 [math.CO] · Zbl 1333.05100  Beals, R; Gallian, J; Headley, P; Jungreis, D, Harmonious groups, J Combin Theory Ser A, 56, 223-238, (1991) · Zbl 0718.20013  Cavenagh, N; Combe, D; Nelson, AM, Dge-magic group labellings of countable graphs, Electron J Combin, R92, 19, (2006) · Zbl 1111.05085  Chartrand, G; Jacobson, MS; Lehel, J; Oellermann, OR; Ruiz, S; Saba, F, Irregular networks, Congressus Numerantium, 64, 187-192, (1988)  Combe, D; Nelson, AM; Palmer, WD, Magic labellings of graphs over finite abelian groups, Aust J Combin, 29, 259-271, (2004) · Zbl 1050.05107  Edmonds, J, Maximum matching and a polyhedron with 0,1-vertices, J Res Nat Bureau Stand, 69B, 125-130, (1965) · Zbl 0141.21802  Froncek D (2013) Group distance magic labeling of Cartesian products of cycles. Austral J Comp 55:167-174. · Zbl 1278.05210  Ferrara, M; Gould, RJ; Karoński, M; Pfender, F, An iterative approach to graph irregularity strength, Discret Appl Math, 158, 1189-1194, (2010) · Zbl 1213.05119  Graham, RL; Sloane, NJA, On additive bases and harmonious graphs, SIAM J Algebraic Discret Methods, 1, 382-404, (1980) · Zbl 0499.05049  Hovey, M, $$A$$-cordial graphs, Discret Math, 93, 183-194, (1991) · Zbl 0753.05059  Kalkowski, M; Karoński, M; Pfender, F, A new upper bound for the irregularity strength of graphs, SIAM J Discret Math, 25, 1319-1321, (2011) · Zbl 1237.05183  Kaplan, G; Lev, A; Roditty, Y, On zero-sum partitions and anti-magic trees, Discret Math, 309, 2010-2014, (2009) · Zbl 1229.05031  Mihǎilescu, P, Primary cyclotomic units and a proof of catalan’s conjecture, Journal für die reine und angewandte Mathematik, 572, 167-195, (2004) · Zbl 1067.11017  Majerski P, Przybyło J (2013) On the irregularity strength of dense graphs (submitted) · Zbl 1293.05341  Stanley, RP, Linear homogeneous Diophantine equations and magic labelings of graphs, Duke Math J, 40, 607-632, (1973) · Zbl 0269.05109  Togni O. (1998) Force des graphes. Indice optique des réseaux, Thèse présentée pour obtenir le grade de docteur, Université de Bordeaux 1, École doctorale de mathematiques et d’informatique 141. · Zbl 0499.05049  Żak, A, Harmonious orders of graphs, Discret Math, 309, 6055-6064, (2009) · Zbl 1188.05138
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.