# TOTAL VERTEX IRREGULARITY STRENGTH OF LADDER RELATED GRAPHS.

Byline: Ashfaq Ahmad, Syed Ahtsham ul Haq Bokhary, Roslan Hasni and
Slamin

1. INTRODUCTION AND DEFINITIONSAs a standard notation, assume that G = G (V, E) is a finite, simple and undirected graph with p vertices and q edges. A labeling of a graph is any mapping that sends some set of graph elements to a set of numbers (usually positive integers). If the domain is the vertex-set or the edge-set, the labeling are called respectively vertex-labeling or edge-labeling. If the domain is V E then we call the labeling atotal labeling. In many cases it is interesting to consider thesum of all labels associated with a graph element. This will be called the weight of element.Motivated by total labeling mentioned in a book of Wallis [10], Baca et al. in [5] introduced a vertex irregular total labeling of graphs. For a simple graph G = (V, E) withvertex set V and edge set E, a labeling : V E {1, 2, . . ., k} is called total k-labeling. The associated vertex weightof a vertex x V (G) under a total k-labeling is defined aswhere N(x) is the set of neighbors of x. A total k-labeling is defined to be a vertex irregular total labeling of a graph Gif for every two different vertices x and y of G,wt(x) wt(y)The minimum k for which a graph G has a vertex irregular total k-labeling is called the total vertex irregularity strength of G, tvs(G).In this paper, we study properties of the vertex irregular total labeling and determine a value of the total vertex irregularity strength for classes of ladder related graphs, such as triangular ladder, diagonal ladder, triangular snake anddouble triangular snake.Triangular Ladder, denoted by TLn, is the graph obtained from ladder by adding single diagonal to each rectangle.Thus the vertex set of TLn is {vi,j |1 = i = 2, 1 = j = n} and the edge set of Ln isj = n} {vi,jvi+1,j+1|i = 1, 1 = j = n - 1}Diagonal Ladder, denoted by DLn, is the graph obtainedfrom ladder by adding two diagonals to each rectangle. Thusthe vertex set of DLn is {vi,j |1 = i = 2, 1 = j = n} and the edge set of DLn isE (G) = {vi,jvi,j+1|1 = i = 2, 1 = j = n-1}{vi,jvi+1,j |i = 1, 1 = j= n}{vi,jvi+1,j+1|i = 1, 1 = j = n - 1} {vi,jvi+1,j-1|i = 1, 2 = j = n}Triangular Snake, denoted by TSn, is the graph obtainedfrom a non-trivial path Pn: v1, v2, . . . , vn by adding newvertices u1, u2, . . . , un-1 joining each ui with vi and vi+1 (1 = i= n - 1). Thus the vertex set of TSn is

{vi, uj|1 = i = n, 1 = j = n - 1}

and the edge set of TSn is

{vivi+1, viui, uivi+1|1 = i = n - 1}

Double Triangular Snake, denoted by DTSn, is the graph obtained from a triangular snake TSn by adding new vertices w1,w2, . . . ,wn-1 joining each wi with vi and vi+1 (1 = i = n - 1). Thus the vertex set of DTSn is{vi, uj,wj |1 = i = n, 1 = j = n - 1}and the edge set of DTSn is{vivi+1, viui, uivi+1, viwi,wivi+1|1 = i = n - 1}

2. KNOWN RESULTS

The following theorem proved in [5], establishes lower and upper bound for the total vertex irregularity strength of a (p, q)-graph.

Theorem 1 [5] Let G be a (p, q)-graph with minimum degree d = d (G) and maximum degree = (G). ThenFor a regular Hamiltonian (p, q) graph G, it was showed in[5] that tvs(G) p 2 . Thus for cycle Cp we have thatRecently, a much stronger upper bound on total vertexirregularity strength of graphs has been established in [4]. In6, 7, 8], Nurdin et al. found the exact values of total vertex irregularity strength of trees, several types of trees and disjoint union of t copies of path. Whereas the total vertexirregularity strength of cubic graphs, wheel related graphs,Jahangir graph Jn,2 for n = 4 and circulant graph Cn(1, 2) for n = 5 has been determined by Ahmad et al. [1, 2, 3]. K. Wijaya et al. [11, 12] found the exact value of the totalvertex irregularity strength of wheels, fans, suns, friendship, and complete bipartite graphs. Slamin et al. [9] determined the total vertex irregularity strength of disjoint union of sungraphs.3. MAIN RESULTWe start this section with the result on the total vertexirregularity strength of triangular ladder TLn graph in the following theorem.

Theorem 2 The total vertex irregular strength of triangular ladder TLn, for n = 8, isProof.Recall that the vertex set and edge set of triangular ladder areEquationThe triangular ladder TLn has 2 vertices of degree 2, 2 vertices of degree 3, and 2n - 2 vertices of degree 4. The lower bound of the total vertex irregular strength ofWe now prove the upper bound by providing labelling construction for TLn.The proof is now complete.The illustration of the Theorem 2 is shown in Figure 1.Let DLn be a diagonal ladder graph, we find the total vertex irregularity strength of such a ladder in the followingtheorem.Proof. Recall that the vertex set of DLn is {vi,j |1 = i =2, 1 = j = n} and the edge set of DLn isWe now prove the upper bound by providing labelling construction for DLn.We label the vertices and the edges of DLn in the following way.Combining with the lower bound, we conclude thatLet T Sn be a triangular snake graph, we find the totalvertex irregularity strength of such a graph in the following theorem.Theorem 4The total vertex irregular strength oftriangular snake graph T Sn, for n greater than 7 isTheorem 5 The total vertex irregular strength of double triangular snake graph DT Sn, for n = 4 is Proof. Recall that the vertex set of DT Sn is{vivi+1 , viui, uivi+1 , viwi, wivi+1 |1 = i = n - 1}Thus the double triangular snake graph DTSn has 2n - 2vertices of degree 2, 2 vertices of degree 3 and n - 2 verticesof degree 6. The smallest weight of DTSn must be 3, so the largest weight of vertices of degree 2 is at least 2n, the largest weight of vertices of degree 3 is at least 2n + 2. Moreover, the largest weight of n - 2 vertices of degree 6 is3n. Consequently, the largest label of one of vertices orWe now prove the upper bound by providing labelling construction for DT Sn.LetIt is easy to check that the weight of the vertices are different. This labelling construction shows thatCombining with the lower bound, we conclude that4. REFERENCES[1] A. Ahmad, M. Baca, "On vertex irregular total labelings", Ars Combin., 112: 129-139(2013)[2] A. Ahmad, K.M. Awan, I. Javaid, Slamin, " Total vertex irregularity strength of wheel related graphs", Australas. J. Combin., 51: 147-156 (2011).[3] A. Ahmad, S.A. Bokhary, M. Imran, A.Q. Baig, " Total vertex irregularity strength of cubic graphs", Utilitas Math., 91: 287-299(2013)[4] M. Anholcer, M. Kalkowski, J. Przybylo, "A new upper bound for the total vertex irregularity strength of graphs", Discrete Math. 309: 63166317(2009). [6] Nurdin, E.T. Baskoro, A.N.M. Salman, N.N. Gaos, "Onthe total vertex irregularity strength of trees", DiscreteMath, 310: 30433048(2010). Nurdin, E.T. Baskoro, A.N.M" On total vertex- irregular labellings for several types of trees", Util. Math, 83: 277290(2010).[8] Nurdin, A. N. M. Salman, N. N. Gaos, E. T. Baskoro," On the total vertex-irregular strength of a disjointunion of t copies of a path", JCMCC, 71: 227[9] Slamin, Dafik, W. Winnona, "Total Vertex IrregularityStrength of the Disjoint Union of Sun Graphs",InternationalJournalofCombinatorics,doi:10.1155/2012/284383.[10] W.D. Wallis, "Magic Graphs", Birkhauser, Boston,2001.[11] K. Wijaya, Slamin, "Total vertex irregular labeling of wheels, fans, suns and friendship graphs", JCMCC, 65:[12] K. Wijaya, Slamin, Surahmat, S. Jendrol, "Total vertex irregular labeling of complete bipartite graphs",JCMCC 55: 129136 (2005).

1. INTRODUCTION AND DEFINITIONSAs a standard notation, assume that G = G (V, E) is a finite, simple and undirected graph with p vertices and q edges. A labeling of a graph is any mapping that sends some set of graph elements to a set of numbers (usually positive integers). If the domain is the vertex-set or the edge-set, the labeling are called respectively vertex-labeling or edge-labeling. If the domain is V E then we call the labeling atotal labeling. In many cases it is interesting to consider thesum of all labels associated with a graph element. This will be called the weight of element.Motivated by total labeling mentioned in a book of Wallis [10], Baca et al. in [5] introduced a vertex irregular total labeling of graphs. For a simple graph G = (V, E) withvertex set V and edge set E, a labeling : V E {1, 2, . . ., k} is called total k-labeling. The associated vertex weightof a vertex x V (G) under a total k-labeling is defined aswhere N(x) is the set of neighbors of x. A total k-labeling is defined to be a vertex irregular total labeling of a graph Gif for every two different vertices x and y of G,wt(x) wt(y)The minimum k for which a graph G has a vertex irregular total k-labeling is called the total vertex irregularity strength of G, tvs(G).In this paper, we study properties of the vertex irregular total labeling and determine a value of the total vertex irregularity strength for classes of ladder related graphs, such as triangular ladder, diagonal ladder, triangular snake anddouble triangular snake.Triangular Ladder, denoted by TLn, is the graph obtained from ladder by adding single diagonal to each rectangle.Thus the vertex set of TLn is {vi,j |1 = i = 2, 1 = j = n} and the edge set of Ln isj = n} {vi,jvi+1,j+1|i = 1, 1 = j = n - 1}Diagonal Ladder, denoted by DLn, is the graph obtainedfrom ladder by adding two diagonals to each rectangle. Thusthe vertex set of DLn is {vi,j |1 = i = 2, 1 = j = n} and the edge set of DLn isE (G) = {vi,jvi,j+1|1 = i = 2, 1 = j = n-1}{vi,jvi+1,j |i = 1, 1 = j= n}{vi,jvi+1,j+1|i = 1, 1 = j = n - 1} {vi,jvi+1,j-1|i = 1, 2 = j = n}Triangular Snake, denoted by TSn, is the graph obtainedfrom a non-trivial path Pn: v1, v2, . . . , vn by adding newvertices u1, u2, . . . , un-1 joining each ui with vi and vi+1 (1 = i= n - 1). Thus the vertex set of TSn is

{vi, uj|1 = i = n, 1 = j = n - 1}

and the edge set of TSn is

{vivi+1, viui, uivi+1|1 = i = n - 1}

Double Triangular Snake, denoted by DTSn, is the graph obtained from a triangular snake TSn by adding new vertices w1,w2, . . . ,wn-1 joining each wi with vi and vi+1 (1 = i = n - 1). Thus the vertex set of DTSn is{vi, uj,wj |1 = i = n, 1 = j = n - 1}and the edge set of DTSn is{vivi+1, viui, uivi+1, viwi,wivi+1|1 = i = n - 1}

2. KNOWN RESULTS

The following theorem proved in [5], establishes lower and upper bound for the total vertex irregularity strength of a (p, q)-graph.

Theorem 1 [5] Let G be a (p, q)-graph with minimum degree d = d (G) and maximum degree = (G). ThenFor a regular Hamiltonian (p, q) graph G, it was showed in[5] that tvs(G) p 2 . Thus for cycle Cp we have thatRecently, a much stronger upper bound on total vertexirregularity strength of graphs has been established in [4]. In6, 7, 8], Nurdin et al. found the exact values of total vertex irregularity strength of trees, several types of trees and disjoint union of t copies of path. Whereas the total vertexirregularity strength of cubic graphs, wheel related graphs,Jahangir graph Jn,2 for n = 4 and circulant graph Cn(1, 2) for n = 5 has been determined by Ahmad et al. [1, 2, 3]. K. Wijaya et al. [11, 12] found the exact value of the totalvertex irregularity strength of wheels, fans, suns, friendship, and complete bipartite graphs. Slamin et al. [9] determined the total vertex irregularity strength of disjoint union of sungraphs.3. MAIN RESULTWe start this section with the result on the total vertexirregularity strength of triangular ladder TLn graph in the following theorem.

Theorem 2 The total vertex irregular strength of triangular ladder TLn, for n = 8, isProof.Recall that the vertex set and edge set of triangular ladder areEquationThe triangular ladder TLn has 2 vertices of degree 2, 2 vertices of degree 3, and 2n - 2 vertices of degree 4. The lower bound of the total vertex irregular strength ofWe now prove the upper bound by providing labelling construction for TLn.The proof is now complete.The illustration of the Theorem 2 is shown in Figure 1.Let DLn be a diagonal ladder graph, we find the total vertex irregularity strength of such a ladder in the followingtheorem.Proof. Recall that the vertex set of DLn is {vi,j |1 = i =2, 1 = j = n} and the edge set of DLn isWe now prove the upper bound by providing labelling construction for DLn.We label the vertices and the edges of DLn in the following way.Combining with the lower bound, we conclude thatLet T Sn be a triangular snake graph, we find the totalvertex irregularity strength of such a graph in the following theorem.Theorem 4The total vertex irregular strength oftriangular snake graph T Sn, for n greater than 7 isTheorem 5 The total vertex irregular strength of double triangular snake graph DT Sn, for n = 4 is Proof. Recall that the vertex set of DT Sn is{vivi+1 , viui, uivi+1 , viwi, wivi+1 |1 = i = n - 1}Thus the double triangular snake graph DTSn has 2n - 2vertices of degree 2, 2 vertices of degree 3 and n - 2 verticesof degree 6. The smallest weight of DTSn must be 3, so the largest weight of vertices of degree 2 is at least 2n, the largest weight of vertices of degree 3 is at least 2n + 2. Moreover, the largest weight of n - 2 vertices of degree 6 is3n. Consequently, the largest label of one of vertices orWe now prove the upper bound by providing labelling construction for DT Sn.LetIt is easy to check that the weight of the vertices are different. This labelling construction shows thatCombining with the lower bound, we conclude that4. REFERENCES[1] A. Ahmad, M. Baca, "On vertex irregular total labelings", Ars Combin., 112: 129-139(2013)[2] A. Ahmad, K.M. Awan, I. Javaid, Slamin, " Total vertex irregularity strength of wheel related graphs", Australas. J. Combin., 51: 147-156 (2011).[3] A. Ahmad, S.A. Bokhary, M. Imran, A.Q. Baig, " Total vertex irregularity strength of cubic graphs", Utilitas Math., 91: 287-299(2013)[4] M. Anholcer, M. Kalkowski, J. Przybylo, "A new upper bound for the total vertex irregularity strength of graphs", Discrete Math. 309: 63166317(2009). [6] Nurdin, E.T. Baskoro, A.N.M. Salman, N.N. Gaos, "Onthe total vertex irregularity strength of trees", DiscreteMath, 310: 30433048(2010). Nurdin, E.T. Baskoro, A.N.M" On total vertex- irregular labellings for several types of trees", Util. Math, 83: 277290(2010).[8] Nurdin, A. N. M. Salman, N. N. Gaos, E. T. Baskoro," On the total vertex-irregular strength of a disjointunion of t copies of a path", JCMCC, 71: 227[9] Slamin, Dafik, W. Winnona, "Total Vertex IrregularityStrength of the Disjoint Union of Sun Graphs",InternationalJournalofCombinatorics,doi:10.1155/2012/284383.[10] W.D. Wallis, "Magic Graphs", Birkhauser, Boston,2001.[11] K. Wijaya, Slamin, "Total vertex irregular labeling of wheels, fans, suns and friendship graphs", JCMCC, 65:[12] K. Wijaya, Slamin, Surahmat, S. Jendrol, "Total vertex irregular labeling of complete bipartite graphs",JCMCC 55: 129136 (2005).

Printer friendly Cite/link Email Feedback | |

Publication: | Science International |
---|---|

Article Type: | Technical report |

Date: | Mar 31, 2014 |

Words: | 1345 |

Previous Article: | THE CAUSATION BETWEEN FATHER'S AUTHORITARIANISM AND TEST ANXIETY: AN EMPIRICAL STUDY AMONG ADOLESCENTS. |

Next Article: | AN ALGORITHM FOR CONSTRUCTING REDUCED ALTERNATING ACHIRAL KNOTS. |

Topics: |