Further results on edge irregularity strength of graphs

Muhammad Imran, Adnan Aslam, Sohail Zafar, Waqas Nazeer


A vertex $k$-labelling $\phi:V(G)\longrightarrow \{1,2,\ldots,k\}$ is called irregular $k$-labeling of the graph $G$ if for every two different edges $e$ and $f$, there is $w_{\phi}(e)\neq w_{\phi}(f)$; where the weight of an edge is given by $e=xy\in E(G)$ is $w_{\phi}(xy)=\phi(x)+\phi(y)$. The minimum $k$ for which the graph $G$ has an edge irregular $k$-labelling is called \emph{edge irregularity strength} of $G$, denoted by $es(G)$.\\
In the paper, we determine the exact value of the edge irregularity strength of caterpillars, $n$-star graphs, $(n,t)$-kite graphs, cycle chains and friendship graphs.


irregular assignment, irregular total k-labeling, irregularity strength

Full Text:



Ahmad A., On vertex irregular total labelings of convex polytope graphs, Utilitas Math., 89 (2012), 69–78.

A. Ahmad, O. B. Saeed Al-Mushayt, M. Baca, On edge irregularity strength of graphs, Appl. Math. Comput., 243 (2014) 607-610.

W. C. Chen, H. I. Lu, and Y. N. Yeh, Operations of interlaced trees and graceful trees, Southeast Asian Bull. Math., 21 (1997) 337–348.

M. Truszczynski, Graceful unicyclic graphs, Demonstatio Math., 17 (1984) 377–387.

S. R. Kim and J. Y. Park, On super edge-magic graphs, Ars Combin., 81 (2006) 113–127.

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

M. A. Seoud and E. El Sakhawi, On variations of graceful labelings, Ars Combin., 87(2008) 127–138.

A. Ahmad, A. Q. Baig, M. Imran, On super edge-magicness of graphs, Utilitas Math., 89(2012) 373–380.

M. Baca, Y. Lin, F. A. Muntaner-Batle, Super edge-antimagic labeling of path like trees, Utilitas Math,to appear.

G. S. Bloom, S. W. Golomb, Applications of undirected graphs, Proc. IEEE 65 (1977), 562-570.

G. S. Bloom G. Sand Golomb S. W., Numbered complete graphs, unusual rules, and assorted applications, Theory and Applications of Graphs, Lecture Notes in Math 642. Springer-Verlag (1978), 53-65.

H. Enomoto, A. S. Llado. T. Nakamigawa, and G.R ingle, Super edge-magic graphs, SUT J.Math, 34(1980),105-109.

A. Q. Baig, A. Ahmad, E. T. Baskoro and R. Simanjuntak, On the super edge-magic graphs, SUT J. Math, 86(2001),147-159.

R. M. Figueroa, R. Ichishima and F. A. Muntaner-Batle, The place of super edge-magic labeling among other classes of labeling, Discrete Math. 231(2001), 153-168.

J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Com- bin. 18 #DS6, http://www.combinatorics.org/surveys/ds6.pdf (2010).

M. Hussain, E. T. Baskoro, K. Ali, On super antimagic total labeling of Harary graph, Ars combin., to appear.

M. Hussain, E. T. Baskoro, Slamin, On super edge-magic total labeling of ba- nana trees, Utilitas Math., 79(2009), 243-251.

M. Javed, M. Hussain, K. Ali, K. H. Dar, On super edge-magic total labeling of ba- nana on w-trees, Utilitas Math., 86(2011), 183-191.

S.-R. Kim and J. Y. Park, On super edge-magic graphs, Ars Combin., 81(2006), 113-127.

A. Kotzig and A. Rosa, Magic valuaton of finite graphs, Canad. Math. Bull. 13(4)(1970), 451-461.

J. Y. Park, J. H. Choi and J-H. Bae, On super edge-magic labeling of some graphs, Bull. Korean Math. Soc., 45(2008), No.1, 11-21.

W. D. Wallis, Magic Graphs, Birkh¨auser, Boston, 2001.

W. D.Wallis, E. T. Baskoro, M. Miller, and Slamin, Edge-magic total labelings, Australas. J. Combin.,22(2000), 177-190.

DOI: http://dx.doi.org/10.19184/ijc.2017.1.2.5


  • There are currently no refbacks.

ISSN: 2541-2205

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View IJC Stats