Syntax Literate: Jurnal Ilmiah Indonesia p�ISSN: 2541-0849 e-ISSN: 2548-1398

Vol. 7, No. 6, Juni 2022

 

ON EDGE IRREGULAR TOTAL LABELING ALGORITHM OF CYCLE CHAIN GRAPH

 

Gradina Nur Fauziah

Politeknik Ilmu Pelayaran Makassar, Indonesia

Email: gradina.nur.f@pipmakassar.ac.id

 


Abstract

Suppose �is a graph with the vertex set �and edge set �we defined a labeling �to be an edge irregular total labeling of graph �if for every two different edge �and �there is . The minimum �for which the graph �has an edge irregular total labeling is called the total irregularity streghth of the graph . On this research we found that labeling algorithm of Cycle Chain Graph with �block cycle graph is an edge irregular total labeling and

 

Keywords: edge irregular total labeling, , Cycle Chain Graph

 

Introduction

A labeling of graph �with vertex set �and edge set is a map that carries graph elements to the numbers (usually to the positive or non-negative integer). The most common choices of domain are the set of all vertices (known as vertex labeling), the set of edge (edge labeling), or the set of all vertices and edges (total labeling) (Gallian, 1998).

The sum of all label that associated with a graph elemen is called weight of the elements. (Wallis, 2001) on his book define that the weight of a vertex �under total labeling �of element of a graph �is a

And the weight of edge is

The irregular labeling was first introduced by Chartland, et all in 1986. Suppose �is a graph then function �is called irregular -labeling of , if every two different vertice �and �in �have distinct weight, that is

������������

The irregularity strength of , denote by s(G), is the smallest positive natural number �such that �have a irregular labelings [3]

The other types of irregular labeling based of total labeling was introduced by Bača et all in 2007. For , the function �is called vertex irregular total labeling of , if the weight of every vertices are distinct. The total vertex irregularity strength of , , is a smallest positive natural number �such that �have a total vertex irregular labeling (M. Baca, S. Jendrol, M. Miller and J.Ryan, 2007).

Baca et al, on his paper have determined the vertex irregularity strengths of some graphs namely cycles, stars� and also prism.

Beside that Baca et al also introduced the total edge irregularity strengths of graphs. Suppose is a graph, then the function �is called edge irregular total labeling of , if the weight of every edges are distinct. The total edge irregularity strength of , , is a smallest positive natural number �such that �have a total edge irregular labeling.

They also derived a lower bound and an upper bound of the total edge irregularity strength for any graph. These bounds are mentioned in the following theorem.

 

Theorem A. Let , be a graph with a vertex set �and the edge set , then�

By investigating the maximum degree of any graphs, Baca et al. proved the next theorem.

 

Theorem B. Let �be a graphs with maximal degree , then

i.     

ii.    

(J. Ivanco, S. Jendrol, 2006) gave a conjecture about the total edge irregularity strength as follows

 

Conjecture, �Let �be a graphs different of , then

Baca et all proved that this conjecture is true for cycle, paths, stars, wheels and friendships (M. Baca, S. Jendrol, M. Miller and J.Ryan, 2007). This conjecture is also true for other graphs such as graphs of linear size (S. Brandt J. Miskuf, D. Rautenbatch, 2009), trees (J. Ivanco, S. Jendrol, 2006), complete graphs and complete bipartite graphs (S. Jendrol, J. Miskuf, and R. Sotak, 2007), the corona of paths with paths, wheels, cycles, stars,� gears, or friendships (Nurdin, E.T. Baskoro, A.N.M. Salman, 2008), and an amalgamation of two isomorphic cycles (Nurdin, 2013) but the total edge irregularity strength of cycle chain graphs not yet found.

1.     Cycle Chain Graphs

A block of a graph is a maximal connected subgraph with no cut vertex � a subgraph with as many edges as possible and no cut vertex. So a block is either �or is a graph which contains a cycle (Diestel, 2006). Barrientos defined a chain graphs as one with block �such that for every , �and �have a common vertex in such a way that the blok cut point graphs is a path. (Barrientos, 2002).

Cycle chain graphs consist of �blocks of cycle graphs, , that connected by a cut vertex. We choose the cut vertex of this graphs is the �vertice for every �blocks. Cycle chain graphs that consist of �block of cycle graphs, denotes by �In this paper we study about irregular labeling of .

Suppose the vertex set of �is

{ � }

with �

 

and the edge set of this graph

2.     Total Edge Irregularity Strength of Cycle chain Graph

In this section will be determined the total edge irregularity strength of cycle chain graph. The total edge irregularity strength denoted by , is

 

Proof, Since �have �edges, the largest weight of the vertex at least . Since the weight of all edge is the number of three positive integer number, the largest label used is at least . Therefore,

 

Next step we will show that , will be construction the total labeling algorithm �on �as follows :

Algorithm A:

Input : vertices of ,

Step 1 : vertices �receives label 1

Step 2 : vertices �receives label 2

Step 3 : vertices �receives label 3

Let , �then

Case 1 : if ,

(i)    Vertices �and �receives same label as follow:

(ii)  Vertex �(as a cut vertex) receives label as follow:

(iii)                    Let label of vertex , then vertices �receives label in the order

(iv) Let label of vertex , then vertices �receives label in the order

Case 2 : if ,

(i)    Vertices �and �receives same label as follow:

(ii)   Vertex �(as a cut vertex) receives label as follow:

(iii) Vertices �and �receives same label as follow:

(iv) Let label of vertex , then vertices �receives label in the order

(v)   Let label of vertex , then vertices �receives label in the order

 

Case 3 : if ,

(i)    Vertices �and �receives same label as follow:

(ii)   Vertex �(as a cut vertex) receives label as follow:

(iii) Let label of vertex , then vertices �receives label in the order

(iv) Let label of vertex , then vertices �receives label in the order

Let block �is the last block of .then

 

Case 1 : if ,

(i)    Vertices �and �receives same label as follow:

(ii)  Vertex �(as an end vertex) receives label as follow:

(iii)                    Let label of vertex , then vertices �receives label in the order

(iv) Let label of vertex , then vertices ��receives label in the order

 

Case 2 : if ,

(i)    Vertices �and �receives same label as follow:

(ii)  Vertex �(as an end vertex) receives label as follow:

(iii)                    Vertices �and �receives same label as follow:

(iv) Let label of vertex , then vertices �receives label in the order

(v)   Let label of vertex , then vertices �receives label in the order

 

Case 3 : if ,

(i)    Vertices �and �receives same label as follow:

(ii)  Vertex �(as an end vertex) receives label as follow:

(iii)                    Let label of vertex , then vertices �receives label in the order

(iv) Let label of vertex , then vertices �receives label in the order

 

Algorithm B:

Input : edges of ,

Step 1: edge �and edge ��receives label 1

Step 2 : edge �receives label 2

Let , then

(i)    edge �receives label

(ii)  edges� , , receives label in the order

(iii)                    edge� receives label

Let , �then

 

Case 1: if ,

(i)    Let label of vertex , then edge �receives label �and� edges �receives label in the order

(ii)  Let label of vertex , then edges �receives label in the order

 

Case 2: if ,

(i)    Let label of vertex , then edges �and ��receives label �and� edges �receives label in the order

(ii)  Let label of vertex , then edges �receives label in the order

 

Case 3: if ,

(i)    Let label of vertex , then edge �receives label �and �edges �receives label in the order

(ii)   Let label of vertex , then edges �receives label in the order

Output:

By the algorithm labeling above, we found that the weight of all edges are

(i)   

(ii) 

(iii)                   

(iv)

(v)  

(vi)

(vii)                  

(viii)                 For ,

(a)  

(b)  

(c)  

(ix)For ,

(a)  

(b)  

(c)  

(x)  For ,

(a)  

(b)  

(c)  

(xi)  if ,

(a)  

(b)  

(c)  

(xii)If ,

(a)  

(b)  

(c)  

(xiii)                   if ,

(a)  

(b)  

(c)  

The weight of the edge successively attain value �when the vertex and the edge receives label from the set �also . Hence the weight of the edges are distinct. The maximum label used is . Hence

 

Conclusion

In this paper, we concluded that the total edge irregularity strength of a circle chain graph �of �blocks is .


BIBLIOGRAPHY

 

Barrientos, C. (2002). Graceful labeling of chain and corona graphs. Bulettin ICA, 34, 17-26.

 

Diestel, R. (2006). Graph Theory, 3rd Edition. Springer Science and Business Media.

 

G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz, and F. Saba. (1988). Irregular Network. Congressus Numerantium, 197 - 210.

 

Gallian, J. (1998). Graph Labeling. Electron J Combin, 5.

 

Gathen, Joachim Von Zur; Panario, Daniel;. (2001). Factoring Polynomials over Finite Fields. Simbolik Computation, 3-17.

 

J. Ivanco, S. Jendrol. (2006). The total edge irregularity stregths of trees. Discuss. Mat. Graph Theory, 26, pp. 449-456.

 

M. Baca, S. Jendrol, M. Miller and J.Ryan. (2007). On irregular total labelings. Discrete Mathematics, 307:1-12, pp. 1378-1388.

 

Nurdin. (2013). The vertex and edge irregular total labeling of amalgamation of two isomorphic cycle. International Journal of Mathematical, Computational, Pshysical, Electrical and Computer Engineering, Vol :7 , No. 6, 1063-1066.

 

Nurdin, E.T. Baskoro, A.N.M. Salman. (2008). The total edge irregular strengths of the corona products of paths with some graphs. Math. Combin. Comput., 65. pp. 163-176.

 

S. Brandt J. Miskuf, D. Rautenbatch. (2009). Edge irregular total labeling for graphs of linear size. Discrete Maths, 309:12, pp. 3786-3792.

 

S. Jendrol, J. Miskuf, and R. Sotak. (2007). Total edge Irregularity stregth of complete graphs and complete bipartite graphs. Elec. Notes in Discrete Math., 28, pp. 281-285.

 

Wallis, W. (2001). Magic Graphs. Boston: Birkhauser.

 

Copyright holder:

Gradina Nur Fauziah (2022)

 

First publication right:

Syntax Literate: Jurnal Ilmiah Indonesia

 

This article is licensed under: