The Vertex and Edge Irregular Total Labeling of an Amalgamation of Two Isomorphic Cycles

Authors: Nurdin

Abstract:

Suppose G(V,E) is a graph, a function f : V \cup E \to \{1, 2, 3, \cdots, k\} is called the total edge(vertex) irregular k-labelling for G such that for each two edges are different having distinct weights. The total edge(vertex) irregularity strength of G, denoted by tes(G)(tvs(G), is the smallest k positive integers such that G has a total edge(vertex) irregular k-labelling. In this paper, we determined the total edge(vertex) irregularity strength of an amalgamation of two isomorphic cycles. The total edge irregularity strength and the total vertex irregularity strength of two isomorphic cycles on n vertices are \lceil (2n+2)/3 \rceil and \lceil 2n/3 \rceil for n \geq 3, respectively.

Keywords: Amalgamation of graphs, irregular labelling, irregularity strength.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1079964

References:

[1] M. Baca, S. Jendrol, M. Miller, and J. Ryan, "On irregular total labellings", Discrete Mathematics, 2007, 307:1-12, pp. 1378ÔÇö1388.
[2] S. Brandt J. Miskuf, D. Rautenbach, "Edge irregular total labellings for graphs of linear size", Discrete Math. 2009, 309:12, pp. 3786-3792.
[3] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz, and F. Saba, "Irregular network", Congressus Numerantium, 1988, 64, pp. 197ÔÇö210.
[4] J. Ivanco, S. Jendrol, "The total edge irregularity strength of trees", Discuss. Mat. Graph Theory, 2006, 26, pp. 449-456
[5] S. Jendrol, J. Miskuf, and R. Sotak, "Total edge irregularity strength of complete graphs and complete bipartite graphs", 2007, Elec. Notes in Discrete Math. 28, pp. 281-285.
[6] A. Kotzig, and A. Rosa, "Magic valuations of finite graphs", Canadian Mathematical Bulletin, 1970, 13, pp. 451ÔÇö323.
[7] N. Murugesan and R. Uma, "A Conjecture on Amalgamation of Graceful Graphs with Star Graphs", Int. J. Contemp. Math. Sciences, 2012, 7:39, pp. 1909--1919.
[8] Nurdin, E.T. Baskoro, A.N.M. Salman, "The total edge irregular strengths of the corona product of paths with some graphs", J. Combin. Math. Combin. Comput. 2008, 65, pp. 163-176.
[9] Nurdin, E.T. Baskoro, A.N.M. Salman, N.N. Gaos, "On total vertexirregular labellings for several types of trees", Util. Math., 2010, 83.
[10] J. Sedlacek, Problem 27 in Thery of Graphs and Its Applications in Proceedings of the Symposium Smolenice, 1963, pp.163ÔÇö167.
[11] B. M. Stewart, Magic Graphs, Canadian Journal of Mathematics, 1996, 18, pp. 1031ÔÇö1059.
[12] K. Wijaya, Slamin, Surahmat, and S. Jendrol, "Total vertex irregular labeling of complete bipartite graphs", J. Combin. Math. Combin. Comput., 2005, 55, pp. 129--136.