On The Total Irregularity Strength of Regular Graphs

Authors

  • Rismawati Ramdani Department of Mathematics, Faculty of Sciences and Technologies, Universitas Islam Negeri Sunan Gunung Djati, Jalan A.H. Nasution No. 105,
  • A.N.M. Salman Combinatorial Mathematics Research Group, Department of Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesha No. 10, Bandung 40132, Indonesia
  • Hilda Assiyatun Combinatorial Mathematics Research Group, Department of Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesha No. 10, Bandung 40132, Indonesia

DOI:

https://doi.org/10.5614/j.math.fund.sci.2015.47.3.6

Keywords:

cycle, dual labeling, path, prism, regular graph, the total irregularity strength, totally irregular total k-labeling.

Abstract

Let ðº = (ð‘‰, ð¸) be a graph. A total labeling ð‘“: 𑉠∪ ð¸ → {1, 2, ⋯ , ð‘˜} is
called a totally irregular total ð‘˜-labeling of ðº if every two distinct vertices ð‘¥ and
𑦠in 𑉠satisfy ð‘¤ð‘“(ð‘¥) ≠ ð‘¤ð‘“(ð‘¦) and every two distinct edges ð‘¥1ð‘¥2 and ð‘¦1ð‘¦2 in ð¸
satisfy ð‘¤ð‘“(ð‘¥1ð‘¥2) ≠ ð‘¤ð‘“(ð‘¦1ð‘¦2), where ð‘¤ð‘“(ð‘¥) = ð‘“(ð‘¥) + Σð‘¥ð‘§âˆˆð¸(ðº) ð‘“(ð‘¥ð‘§) and
ð‘¤ð‘“(ð‘¥1ð‘¥2) = ð‘“(ð‘¥1) + ð‘“(ð‘¥1ð‘¥2) + ð‘“(ð‘¥2). The minimum 𑘠for which a graph ðº has
a totally irregular total ð‘˜-labeling is called the total irregularity strength of ðº,
denoted by ð‘¡ð‘ (ðº). In this paper, we consider an upper bound on the total
irregularity strength of ð‘š copies of a regular graph. Besides that, we give a dual labeling of a totally irregular total ð‘˜-labeling of a regular graph and we consider the total irregularity strength of ð‘š copies of a path on two vertices, ð‘š copies of a cycle, and ð‘š copies of a prism ð¶ð‘› â–¡ ð‘ƒ2.

References

BaÄa, M., JendroÄ­, S., Miller, M. & Ryan, J., On Irregular Total Labeling, Discrete Math., 307, pp. 1378-1388, 2007.

Nurdin, Baskoro, E.T., Salman, A.N.M. & Gaos, N.N., On the Total Vertex Irregularity Strength of Trees, Discrete Math., 310, pp. 3043-3048, 2010.

Majerski, P. & Przybylo, J., Total Vertex Irregularity Strength of Dense Graphs, J. Graph Theory, 76(1), pp. 34-41, 2014.

Anholcer, M., Kalkowski, M. & Przybylo, J., A New Upper Bound for the Total Vertex Irregularity Strength of Graphs. Discrete Math., 309, pp. 6316-6317, 2009.

Nurdin, Baskoro, E.T., Salman, A.N.M. & Gaos, N.N., On the Total Vertex Irregular Labelings for Several Types of Trees, Utilitas Mathematica, 83, pp. 277-290, 2010.

Nurdin, Salman, A.N.M., Gaos, N.N. & Baskoro, E.T., On the Total Vertex-Irregular Strength of a Disjoint Union of T Copies of a Path, J. Combin. Math. Combin. Comput., 71, pp. 227-233, 2009.

Wijaya, K. & Slamin, Total Vertex Irregular Labeling of Wheels, Fans, Suns and Friendship Graphs, J. Combin. Math. Combin. Comput., 65, pp. 103-112, 2008.

Wijaya, K., Slamin, Surahmat & JendroÄ­, S., Total Vertex Irregular Labeling of Complete Bipartite Graphs, J. Combin. Math. Combin. Comput., 55, pp. 129-136, 2005.

IvanÄo, J. & JendroÄ­, S., Total Edge Irregularity Strength of Trees, Discussiones Math. Graph Theory, 26, pp. 449-456, 2006.

Nurdin, Salman, A.N.M. & Baskoro, E.T., The Total Edge-Irregular Strengths of the Corona Product of Paths with some Graphs, J. Combin. Math. Combin. Comput., 65, pp. 163-175, 2008.

BaÄa, M. & Siddiqui, M.K., Total Edge Irregularity Strength of Generalized Prism, Applied Math. Comput., 235, pp. 168-173, 2014.

JendroÄ­, S., MiÅ¡kuf, J. & SotaÌk, R., Total Edge Irregularity Strength of Complete and Complete Bipartite Graphs, Electron Notes Discrete Math., 28, pp. 281-285, 2007.

JendroÄ­, S., MiÅ¡kuf, J. & SotaÌk, R., Total Edge Irregularity Strength of Complete Graphs and Complete Bipartite Graphs, Discrete Math., 310, pp. 400-407, 2010.

Miškuf, J. & Jendroĭ, S., On Total Edge Irregularity Strength of the Grids, Tatra Mt. Math. Publ., 36, pp. 147-151, 2007.

Marzuki, C.C., Salman, A.N.M. & Miller, M., On the Total Irregularity Strength on Cycles and Paths, Far East Journal of Mathematical Sciences, 82(1), pp. 1-21, 2013.

Ramdani, R. & Salman, A.N.M., On the Total Irregularity Strength of Some Cartesian Product Graphs, AKCE Int. J. Graphs Comb., 10(2), pp. 199-209, 2013.

Downloads

Published

2015-12-01

Issue

Section

Articles