Group Irregular Labelings of Disconnected Graphs


  • Marcin Anholcer
  • Sylwia Cichacz-Przenioslo AGH University of Science and Technology



Irregularity strength, Graph weighting, Graph labeling, Abelian group


We investigate the \textit{group irregularity strength} ($s_g(G)$) of graphs, i.e. the smallest value of $s$ such that taking any Abelian group $\gr$ of order $s$, there exists a function $f:E(G)\rightarrow \gr$ such that the sums of edge labels at every vertex are distinct. We give the exact values and bounds on $s_g(G)$ for chosen families of disconnected graphs. In addition we present some results for the \textit{modular edge gracefulness} $k(G)$, i.e. the smallest value of $s$ such that there exists a function $f:E(G)\rightarrow \zet_s$ such that the sums of edge labels at every vertex are distinct.


M. Aigner and E. Triesch, Irregular assignments of trees and forests, SIAM J. Discrete Math. 3 (1990), 439-449.

D. Amar and O. Togni, Irregularity strength of trees, Discrete Math. 190 (1998), 15-38.

M. Anholcer, S. Cichacz, and M. Milanic, Group irregularity strength of connected graphs, J. Comb. Optim. 30 (2015), 1-17.

G. Chartrand, M. S. Jacobson, J. Lehel, O. R. Oellermann, S. Ruiz, and F. Saba, Irregular networks, Congr. Numer. 64 (1988), 187-192.

M. Ferrara, R. J. Gould, M. Karonski, and F. Pfender, An iterative approach to graph irregularity strength, Discrete Appl. Math. 158 (2010), 1189-1194.

F. Fujie-Okamoto, R. Jones, K. Kolasinski, and P. Zhang, On modular edge-graceful graphs, Graphs Combin. 29 (2013), 901-912.

J. Gallian, Contemporary abstract algebra, seventh ed., Brooks/Cole Cengage Learning, 2010.

R. Jones, Modular and graceful edge colorings of graphs, Ph.D. thesis, Western Michigan University, 2011.

R. Jones and P. Zhang, Nowhere-zero modular edge-graceful graphs, Discuss. Math. Graph Theory 32 (2012), 487-505.

M. Kalkowski, M. Karonski, and F. Pfender, A new upper bound for the irregularity strength of graphs, SIAM J. Discrete Math. 25 (2011), 1319-1321.

G. Kaplan, A. Lev, and Y. Roditty, On zero-sum partitions and anti-magic trees, Discrete Math. 309 (2009), 2010-2014.

J. Lehel, Facts and quests on degree irregular assignments, Graph Theory, combinatorics and applications : proc. of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, Wiley, New York, 1991, pp. 765-782.

S. P. Lo, On edge-graceful labelings of graphs, Congr. Numer. 50 (1985), 231-241.

P. Majerski and J. Przyby lo, On the irregularity strength of dense graphs, SIAM J. Discrete Math. 28 (2014), no. 1, 197-205.

O. Togni, Force des graphes. indice optique des reseaux, Ph.D. thesis, Universite de Bordeaux 1, Ecole doctorale de mathematiques et d'informatique, 1998.