Discussiones Mathematicae Graph Theory 32(3) (2012)
427-434
DOI: https://doi.org/10.7151/dmgt.1619
Total Vertex Irregularity Strength of Disjoint Union of Helm Graphs
Ali Ahmad
College of Computer Science and Information Systems | E.T. Baskoro
Combinatorial Mathematics Research Group | M. Imran
Center for Advanced Mathematics and Physics (CAMP) |
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
Close