Research PaperNo Access

On $H$ -irregularity strength of cycles and diamond graphs

Faculty of Mathematics, Laboratory L’IFORCE, University of Sciences and Technology Houari Boumediene (USTHB), B. P. 32 El-Alia, Bab-Ezzouar, 16111 Algiers, Algeria

E-mail Address: hlabane@usthb.dz

E-mail Address: hayatlabane@gmail.com

Search for more papers by this author

Isma Bouchemakh

Faculty of Mathematics, Laboratory L’IFORCE, University of Sciences and Technology Houari Boumediene (USTHB), B. P. 32 El-Alia, Bab-Ezzouar, 16111 Algiers, Algeria

E-mail Address: ibouchemakh@usthb.dz

E-mail Address: isma_bouchemakh2001@yahoo.fr

Corresponding author.

Search for more papers by this author

, and

Andrea Semaničová-Feňovčíková

Department of Applied Mathematics and Informatics, Technical University, Košice, Slovakia

E-mail Address: andrea.fenovcikova@tuke.sk

Search for more papers by this author

https://doi.org/10.1142/S1793830921501573Cited by:1 (Source: Crossref)

Abstract

A simple graph $G = (V (G), E (G))$ admits an $H$ -covering if every edge in $E (G)$ belongs to at least one subgraph of $G$ isomorphic to a given graph $H$ . The graph $G$ admits an $H$ -irregular total $k$ -labeling $f : V (G) \cup E (G) \to {1, 2, \dots, k}$ if $G$ admits an $H$ -covering and for every two different subgraphs $H^{'}$ and $H^{″}$ isomorphic to $H$ , there is ${wt}_{f} (H^{'}) \neq {wt}_{f} (H^{″})$ , where ${wt}_{f} (H) = \sum_{v \in V (H)} f (v) + \sum_{e \in E (H)} f (e)$ is the associated $H$ -weight. The total $H$ -irregularity strength of $G$ is $ths (G, H) = min {k : G has an H -irregular total k -labeling}$ .

In this paper, we give the exact values of $ths (C_{n}, P_{m})$ , where $m \in {3, \frac{n}{2}, \frac{n}{2} + 1, n}$ . For the versions edge and vertex $H$ -irregularity strength $ehs$ and $vhs$ , respectively, we determine the exact values of $ehs ({Br}_{n}, C_{3})$ , $ehs ({Br}_{n}, {Br}_{m})$ and $vhs ({Br}_{n}, {Br}_{m})$ , where ${Br}_{n}$ is the diamond graph.

Communicated by Xiaofeng Gao

Keywords:

AMSC: 05C70, 05C78

References

1. A. Ahmad and M. Bača, Total edge irregularity strength of a categorical product of two paths, Ars Combin. 114 (2014) 203–212. Google Scholar
2. A. Ahmad and M. Bača, On vertex irregular total labelings, Ars Combin. 112 (2013) 129–7139. Google Scholar
3. A. Ahmad, M. Bača and M. K. Siddiqui, On edge irregular total labeling of categorical product of two cycles, Theory Comput. Syst. 54(1) (2014) 1–12. Crossref, Google Scholar
4. A. Ahmad, M. Bača and Y. Bashir, Total vertex irregularity strength of certain classes of unicyclic graphs, Bull. Math. Soc. Sci. Math. Roumanie 57(2) (2014) 147–152. Google Scholar
5. A. Ahmad, E. Baskoro and M. Imran, Total vertex irregularity strength of disjoint union of helm graphs, Discuss. Math. Graph Theory 32 (2012) 427–434. Crossref, Google Scholar
6. A. Ahmad, S. A. Bokhary, R. Hasni and S. Slamin, Total vertex irregularity strength of ladder related graphs, Sci. Int. (Lahore) 26(1) (2014) 1–5. Google Scholar
7. M. Anholcer and C. Palmer, Irregular labelings of circulant graphs, Discrete Math. 312 (2012) 3461–3466. Crossref, Google Scholar
8. F. Ashraf, M. Bača, M. Lascsáková and A. Semaničová-Feňovčíková, On $H$ -irregularity strength of graphs, Discuss. Math. Graph Theory 37 (2017) 1067–1078. Crossref, Google Scholar
9. F. Ashraf, M. Bača, S. C. López, F. A. Muntaner-Batle, A. Oshima and A. Semaničová-Feňovčíková, On total $H$ -irregularity strength of the disjoint union of the graphs, Discuss. Math. Graph Theory 40(1) (2020) 181–194. Crossref, Google Scholar
10. F. Ashraf, M. Bača, Z. Kimáková and A. Semaničová-Feňovčíková, On vertex and edge $H$ -irregularity strengths of graphs, Discrete Math. Algorithms Appl. 8(4) (2016) 13 p. Link, Google Scholar
11. F. Ashraf, M. Bača, A. Semaničová-Feňovčíková and S. W. Saputro, On cycle-irregularity strength of ladders and fan graphs, Electron. J. Graph Theory Appl. 8(1) (2020) 181–194. Crossref, Google Scholar
12. F. Ashraf, M. Bača, A. Semaničová-Feňovčíková and A. Shabbir, On $H$ -irregularity strengths of $𝒢$ -amalgamation of graphs, Electron. J. Graph Theory Appl. 5(2) (2017) 325–334. Crossref, Google Scholar
13. F. Ashraf, M. Bača, A. Semaničová-Feňovčíková and M. K. Siddique, On $H$ -irregularity strength of ladders and fan graphs, AKCE Int. J. Graphs Comb. 64 (2019) 1–7. Google Scholar
14. M. Bača, S. Jendrol’, M. Miller and J. Ryan, On irregular total labelings, Discrete Math. 307 (2007) 1378–1388. Crossref, Google Scholar
15. M. Bača and M. K. Siddiqui, Total edge irregularity strength of generalized prism, Appl. Math. Comput. 235 (2014) 168–173. Crossref, Google Scholar
16. S. Brandt, J. Miškuf and D. Rautenbach, On a conjecture about edge irregular total labelings, J. Graph Theory 57 (2008) 333–343. Crossref, Google Scholar
17. K. N. M. Haque, Irregular total labelings of generalized Petersen graphs, Theory Comput. Syst. 50 (2012) 537–544. Crossref, Google Scholar
18. N. Hinding, E. T. Baskoro and A. N. M. Salman, The total edge irregular strengths of union graphs of $K_{2, 3}$ , J. Math. Saint 11(3) (2006) 105–109. Google Scholar
19. N. Hinding, E. T. Baskoro, A. N. M. Salman and N. N. Gaos, On the total vertex irregularity strength of trees, Discrete Math. 310 (2010) 3043–3048. Crossref, Google Scholar
20. N. Hinding, A. N. M. Salman and E. T. Baskoro, The total edge-irregular strengths of the corona product of paths with some graphs, J. Combin. Math. Combin. Comput. 65 (2008) 163–175. Google Scholar
21. N. Hinding, D. Firmayasari, H. Basir, M. Bača and A. Semaničová-Feňovčíková, On irregularity strength of diamond network, AKCE Int. J. Graphs Comb. 15(3) (2018) 291–297. Crossref, Google Scholar
22. J. Ivančo and S. Jendrol’, Total edge irregularity strength of trees, Discuss. Math. Graph Theory 26 (2006) 449–456. Crossref, Google Scholar
23. D. Indriati, I. E. W. Widodo and K. A. Sugeng, On the total edge irregularity strength of generalized Helm, AKCE Int. J. Graphs Comb. 10(2) (2013) 147–155. Google Scholar
24. S. Jendroll’, J. Miškuf and R. Soták, Total edge irregularity strength of complete graphs and complete bipartite graphs, Discrete Math. 310 (2010) 400–407. Crossref, Google Scholar
25. P. Jeyanthi and A. Sudha, Total edge irregularity strength of disjoint union of wheel graphs, Electron. Notes Discrete Math. 48 (2015) 175–182. Crossref, Google Scholar
26. P. Jeyanthi and A. Sudha, Some results on edge irregular total labeling, J. Int. Math. Virtual Inst. 9 (2019) 73–91. Google Scholar
27. J. Miškuf and S. Jendrol’, On total edge irregularity strength of the grids, Tatra Mt. Math. Publ. 36 (2007) 147–151. Google Scholar
28. M. Naeem, M. K. Siddiqui, M. Bača, A. Semaničová-Feňovčíková and F. Ashraf, On edge $H$ -irregularity strengths of some graphs, Discuss. Math. Graph Theory 37 (2017) 1067–1078. Crossref, Google Scholar
29. R. W. Putra and Y. Susanti, On total edge irregularity strength of centralized uniform theta graphs, AKCE Int. J. Graphs Comb. 15(1) (2018) 7–13. Crossref, Google Scholar
30. R. Nisviasari, D. Dafik and I. H. Agustin, The total $H$ -irregularity strength of triangular ladder and grid graphs, J. Phys. Conf. Ser. 1211 (2019) 012005. Crossref, Google Scholar
31. L. Ratnasarin and Y. Susanti, Total edge irregularity strength of ladder-related graphs, Asian-Eur. J. Math. 13(1) (2020) 2050072. Link, Google Scholar
32. H. D. Wahyuna and D. Indriati, On the total edge irregularity strength of generalized butterfly graph, J. Phys. Conf. Ser. 1008 (2018) 012027. Crossref, Google Scholar