Main Article Content
Abstract
For a simple graph G = (V (G), E(G)), a total labeling ∂ is called an edge irregular total k-labeling of G if ∂ : V (G) ∪ E(G) → {1, 2, . . . , k} such that for any two different edges uv and u'v' in E(G), we have wt∂(uv) not equal to wt∂(u'v') where wt∂(uv) = ∂(u) + ∂(v) + ∂(uv). The minimum k for which G has an edge irregular
total k-labeling is called the total edge irregularity strength, denoted by tes(G). It is known that ceil((|E(G)|+2)/3) is a lower bound for the total edge irregularity strength of a graph G. In this paper we prove that if G is a bipartite graph for which this bound is tight then this is also true for Cartesian product of G with any path.
Keywords
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
- M. Aftiana and D. Indriati, On Edge Irregular Total k-labeling and Total Edge Irregularity Strength of Barbell Graphs, Journal of Physics: Conference Series, (2019), no. 1, 1306:012031.
- A. Ahmad and M, Baˇca, Total edge irregularity strength of categorical product of two paths, Ars Comb. 114 (2014), 203–212.
- A. Ahmad, M. Baˇca and M. K. Siddiqui, On edge irregular total labeling of categorical product of two cycles, Theory of Computing Systems, 54 (2014), no. 1, 1–12.
- O. Al-Mushayt, A. Ahmad, and M. K. Siddiqui, On the total edge irregularity strength of hexagonal grid graphs, Australas. J Comb., 53 (2012), 263–272.
- M. Baˇca, S. Jendroˇl, M. Miller and J. Ryan, On irregular total labellings, Discrete Mathematics 307 (2007), no 11-12, 1378–1388.
- M. Baˇca, M. Lascs´akov´a and M. K. Siddiqui, Total edge irregularity strength of toroidal fullerene, Mathematics in Computer Science 7 (2013), 487–492.
- M. Baˇca and M. K. Siddiqui, Total edge irregularity strength of generalized prism, Applied mathematics and computation 235 (2014), 168–173.
- G. Chartrand, L. Lesniak and P. Zhang Graphs & Digraphs. CRC press 39, 2010.
- G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988), 197–210, 250th.
- J. A. Gallian, A dynamic survey of graph labeling, The electronic journal of combinatorics DS6 (2021), 24th edition.
- J. Ivanˇco and S. Jendroˇl, Total edge irregularity strength of trees, Discussiones Math. Graph Theory 26 (2006), no. 3, 449–456.
- S. Jendroˇl, J.Miˇskuf and R. Sot´ak, Total edge irregularity strength of complete and complete bipartite graphs, Electron. Notes Discrete Math. 28 (2007), 281–285.
- A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium), Rome (1966), 349–355.
- M. K. Siddiqui, On total edge irregularity strength of a categorical product of cycle and path,
- AKCE J. Graphs. Combin 9 (2012), no. 1, 43–52.
- M. K. Siddiqui, On edge irregularity strength of subdivision of star Sn, Int. J. Math. Soft Comput 2 (2012), no. 2, 75–82.
- Y. Susanti, Y. I. Puspitasari and H. Khotimah, On total edge irregularity strength of Staircase graphs and related graphs, Iranian Journal of Mathematical Sciences and Informatics 15(1) (2020), no. 1, 1–13
- Y. Susanti, S. Wahyuni, A. Sutijijana, S. Sutopo, and I. Ernanto, Generalized Arithmetic Staircase Graphs and Their Total Edge Irregularity Strengths, Symmetry 14(9) (2022), no. 9, 1853
References
M. Aftiana and D. Indriati, On Edge Irregular Total k-labeling and Total Edge Irregularity Strength of Barbell Graphs, Journal of Physics: Conference Series, (2019), no. 1, 1306:012031.
A. Ahmad and M, Baˇca, Total edge irregularity strength of categorical product of two paths, Ars Comb. 114 (2014), 203–212.
A. Ahmad, M. Baˇca and M. K. Siddiqui, On edge irregular total labeling of categorical product of two cycles, Theory of Computing Systems, 54 (2014), no. 1, 1–12.
O. Al-Mushayt, A. Ahmad, and M. K. Siddiqui, On the total edge irregularity strength of hexagonal grid graphs, Australas. J Comb., 53 (2012), 263–272.
M. Baˇca, S. Jendroˇl, M. Miller and J. Ryan, On irregular total labellings, Discrete Mathematics 307 (2007), no 11-12, 1378–1388.
M. Baˇca, M. Lascs´akov´a and M. K. Siddiqui, Total edge irregularity strength of toroidal fullerene, Mathematics in Computer Science 7 (2013), 487–492.
M. Baˇca and M. K. Siddiqui, Total edge irregularity strength of generalized prism, Applied mathematics and computation 235 (2014), 168–173.
G. Chartrand, L. Lesniak and P. Zhang Graphs & Digraphs. CRC press 39, 2010.
G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988), 197–210, 250th.
J. A. Gallian, A dynamic survey of graph labeling, The electronic journal of combinatorics DS6 (2021), 24th edition.
J. Ivanˇco and S. Jendroˇl, Total edge irregularity strength of trees, Discussiones Math. Graph Theory 26 (2006), no. 3, 449–456.
S. Jendroˇl, J.Miˇskuf and R. Sot´ak, Total edge irregularity strength of complete and complete bipartite graphs, Electron. Notes Discrete Math. 28 (2007), 281–285.
A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium), Rome (1966), 349–355.
M. K. Siddiqui, On total edge irregularity strength of a categorical product of cycle and path,
AKCE J. Graphs. Combin 9 (2012), no. 1, 43–52.
M. K. Siddiqui, On edge irregularity strength of subdivision of star Sn, Int. J. Math. Soft Comput 2 (2012), no. 2, 75–82.
Y. Susanti, Y. I. Puspitasari and H. Khotimah, On total edge irregularity strength of Staircase graphs and related graphs, Iranian Journal of Mathematical Sciences and Informatics 15(1) (2020), no. 1, 1–13
Y. Susanti, S. Wahyuni, A. Sutijijana, S. Sutopo, and I. Ernanto, Generalized Arithmetic Staircase Graphs and Their Total Edge Irregularity Strengths, Symmetry 14(9) (2022), no. 9, 1853