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)

05C40 Connectivity
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
Full Text: DOI arXiv
[1] Aigner, M; Triesch, E, Irregular assignments of trees and forests, SIAM J Discret Math, 3, 439-449, (1990) · Zbl 0735.05049
[2] Amar, D; Togni, O, Irregularity strength of trees, Discret Math, 190, 15-38, (1998) · Zbl 0956.05092
[3] Anholcer M, Cichacz S (2013) Group sum chromatic number of graphs, preprint, arXiv:1205.2572v3 [math.CO] · Zbl 1333.05100
[4] Beals, R; Gallian, J; Headley, P; Jungreis, D, Harmonious groups, J Combin Theory Ser A, 56, 223-238, (1991) · Zbl 0718.20013
[5] Cavenagh, N; Combe, D; Nelson, AM, Dge-magic group labellings of countable graphs, Electron J Combin, R92, 19, (2006) · Zbl 1111.05085
[6] Chartrand, G; Jacobson, MS; Lehel, J; Oellermann, OR; Ruiz, S; Saba, F, Irregular networks, Congressus Numerantium, 64, 187-192, (1988)
[7] Combe, D; Nelson, AM; Palmer, WD, Magic labellings of graphs over finite abelian groups, Aust J Combin, 29, 259-271, (2004) · Zbl 1050.05107
[8] Edmonds, J, Maximum matching and a polyhedron with 0,1-vertices, J Res Nat Bureau Stand, 69B, 125-130, (1965) · Zbl 0141.21802
[9] Froncek D (2013) Group distance magic labeling of Cartesian products of cycles. Austral J Comp 55:167-174. · Zbl 1278.05210
[10] 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
[11] Graham, RL; Sloane, NJA, On additive bases and harmonious graphs, SIAM J Algebraic Discret Methods, 1, 382-404, (1980) · Zbl 0499.05049
[12] Hovey, M, \(A\)-cordial graphs, Discret Math, 93, 183-194, (1991) · Zbl 0753.05059
[13] 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
[14] Kaplan, G; Lev, A; Roditty, Y, On zero-sum partitions and anti-magic trees, Discret Math, 309, 2010-2014, (2009) · Zbl 1229.05031
[15] 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
[16] Majerski P, Przybyło J (2013) On the irregularity strength of dense graphs (submitted) · Zbl 1293.05341
[17] Stanley, RP, Linear homogeneous Diophantine equations and magic labelings of graphs, Duke Math J, 40, 607-632, (1973) · Zbl 0269.05109
[18] 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
[19] Ż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.