Discussiones Mathematicae Graph Theory 32(3) (2012) 427-434
doi: 10.7151/dmgt.1619

[BIBTex] [PDF] [PS]

Total Vertex Irregularity Strength of Disjoint Union of Helm Graphs

Ali Ahmad

College of Computer Science and Information Systems
Jazan University, Jazan
Kingdom of Saudi Arabia

E.T. Baskoro

Combinatorial Mathematics Research Group
Faculty of Mathematics and Natural Sciences
Institut Teknologi Bandung, Indonesia

M. Imran

Center for Advanced Mathematics and Physics (CAMP)
National University of Science and Technology (NUST)
H-12 Sector, Islamabad, Pakistan

Abstract

A total vertex irregular k-labeling φ of a graph G is a labeling of the vertices and edges of G with labels from the set {1,2, ..., k} in such a way that for any two different vertices x and y their weights wt(x) and wt(y) are distinct. Here, the weight of a vertex x in G is the sum of the label of x and the labels of all edges incident with the vertex x. The minimum k for which the graph G has a vertex irregular total k-labeling is called the total vertex irregularity strength of G. We have determined an exact value of the total vertex irregularity strength of disjoint union of Helm graphs.

Keywords: vertex irregular total k-labeling, Helm graphs, total vertex irregularity strength

2010 Mathematics Subject Classification: 05C78.

References

[1]A. Ahmad and M. Bača, On vertex irregular total labelings, Ars Combin. (to appear).
[2]A. Ahmad, K.M. Awan, I. Javaid, and Slamin, Total vertex irregularity strength of wheel related graphs, Australas. J. Combin. 51 (2011) 147--156.
[3]M. Anholcer, M. Kalkowski and J. Przybyło, A new upper bound for the total vertex irregularity strength of graphs, Discrete Math. 309 (2009) 6316--6317, doi: 10.1016/j.disc.2009.05.023.
[4]M. Bača, S. Jendrol', M. Miller and J. Ryan, On irregular total labellings, Discrete Math. 307 (2007) 1378--1388, doi: 10.1016/j.disc.2005.11.075.
[5]T. Bohman and D. Kravitz, On the irregularity strength of trees, J. Graph Theory 45 (2004) 241--254, doi: 10.1002/jgt.10158.
[6]G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988) 187--192.
[7]R.J. Faudree, M.S. Jacobson, J. Lehel and R.H. Schlep, Irregular networks, regular graphs and integer matrices with distinct row and column sums, Discrete Math. 76 (1988) 223--240, doi: 10.1016/0012-365X(89)90321-X.
[8]A. Frieze, R.J. Gould, M. Karoński, and F. Pfender, On graph irregularity strength, J. Graph Theory 41 (2002) 120--137, doi: 10.1002/jgt.10056.
[9]A. Gyárfás, The irregularity strength of Km,m is 4 for odd m, Discrete Math. 71 (1988) 273--274, doi: 10.1016/0012-365X(88)90106-9.
[10]S. Jendrol', M. Tkáč and Zs. Tuza, The irregularity strength and cost of the union of cliques, Discrete Math. 150 (1996) 179--186, doi: 10.1016/0012-365X(95)00186-Z.
[11]M. Kalkowski, M. Karoński and F. Pfender, A new upper bound for the irregularity strength of graphs, SIAM J. Discrete Math. 25 (2011) 139--1321, doi: 10.1137/090774112.
[12]T. Nierhoff, A tight bound on the irregularity strength of graphs, SIAM J. Discrete Math. 13 (2000) 313--323, doi: 10.1137/S0895480196314291.
[13]Nurdin, E.T. Baskoro, A.N.M. Salamn and N.N. Goas, On the total vertex irregularity strength of trees, Discrete Math. 310 (2010) 3043--3048, doi: 10.1016/j.disc.2010.06.041.
[14]J. Przybyło, Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J. Discrete Math. 23 (2009) 511--516, doi: 10.1137/070707385.
[15]K. Wijaya and Slamin, Total vertex irregular labeling of wheels, fans, suns and friendship graphs, J. Combin. Math. Combin. Comput. 65 (2008) 103--112.
[16]K. Wijaya, Slamin, Surahmat and S. Jendrol, Total vertex irregular labeling of complete bipartite graphs, J. Combin. Math. Combin. Comput. 55 (2005) 129--136.

Received 12 April 2011
Revised 20 July 2011
Accepted 25 July 2011