Let $ G(V, E) $ be a graph, where $ V(G) $ is the vertex set and $ E(G) $ is the edge set. Let $ k $ be a natural number, a total k-labeling $ \varphi:V(G)\bigcup E(G)\rightarrow \{0, 1, 2, 3, ..., k\} $ is called an edge irregular reflexive $ k $-labeling if the vertices of $ G $ are labeled with the set of even numbers from $ \{0, 1, 2, 3, ..., k\} $ and the edges of $ G $ are labeled with numbers from $ \{1, 2, 3, ..., k\} $ in such a way for every two different edges $ xy $ and $ x^{'}y^{'} $ their weights $ \varphi(x)+\varphi(xy)+\varphi(y) $ and $ \varphi(x^{'})+\varphi(x^{'}y^{'})+\varphi(y^{'}) $ are distinct. The reflexive edge strength of $ G $, $ res(G) $, is defined as the minimum $ k $ for which $ G $ has an edge irregular reflexive $ k $-labeling. In this paper, we determine the exact value of the reflexive edge strength for the $ r $-th power of the path $ P_{n} $, where $ r\geq2 $, $ n\geq r+4 $.
Citation: Mohamed Basher. Edge irregular reflexive labeling for the $ r $-th power of the path[J]. AIMS Mathematics, 2021, 6(10): 10405-10430. doi: 10.3934/math.2021604
Let $ G(V, E) $ be a graph, where $ V(G) $ is the vertex set and $ E(G) $ is the edge set. Let $ k $ be a natural number, a total k-labeling $ \varphi:V(G)\bigcup E(G)\rightarrow \{0, 1, 2, 3, ..., k\} $ is called an edge irregular reflexive $ k $-labeling if the vertices of $ G $ are labeled with the set of even numbers from $ \{0, 1, 2, 3, ..., k\} $ and the edges of $ G $ are labeled with numbers from $ \{1, 2, 3, ..., k\} $ in such a way for every two different edges $ xy $ and $ x^{'}y^{'} $ their weights $ \varphi(x)+\varphi(xy)+\varphi(y) $ and $ \varphi(x^{'})+\varphi(x^{'}y^{'})+\varphi(y^{'}) $ are distinct. The reflexive edge strength of $ G $, $ res(G) $, is defined as the minimum $ k $ for which $ G $ has an edge irregular reflexive $ k $-labeling. In this paper, we determine the exact value of the reflexive edge strength for the $ r $-th power of the path $ P_{n} $, where $ r\geq2 $, $ n\geq r+4 $.
| [1] | A. Ahmad, M. Bača, Y. Bashir, M. K. Siddiqui, Total edge irregularity strength of strong product of two paths, Ars Comb., 106 (2012), 449–459. |
| [2] |
A. Ahmad, M. Bača, M. K. Siddiqui, On edge irregular total labeling of categorical product of two cycles, Theory Comput. Syst., 54 (2014), 1–12. doi: 10.1007/s00224-013-9470-3
|
| [3] | A. Ahmad, M. K. Siddiqui, D. Afzal, On the total edge irregularity strength of zigzag graphs, Australas. J. Comb., 54 (2012), 141–150. |
| [4] | A. Ahmad, M. Bača, On Vertex Irregular Total Labelings, Ars Comb., 112 (2013), 129–139. |
| [5] |
D. Amar, O. Togni, Irregularity strength of trees, Discrete Math., 190 (1998), 15–38. doi: 10.1016/S0012-365X(98)00112-5
|
| [6] |
I. H. Agustin, I. Utoyo, M. Venkatachalam, Edge irregular reflexive labeling of some tree graphs, J. Phys.: Conf. Ser., 1543 (2020), 012008. doi: 10.1088/1742-6596/1543/1/012008
|
| [7] |
M. Bača, S. Jendrol, M. Miller, J. Ryan, On irregular total labellings, Discrete Math., 307 (2007), 1378–1388. doi: 10.1016/j.disc.2005.11.075
|
| [8] | M. Bača, M. K. Siddiqui, Total edge irregularity strength of generalized prism, Appl. Math. Comput., 235 (2014), 168–173. |
| [9] | M. Bača, M. K. Siddiqui, On total edge irregularity strength of strong product of two cycles, Util. Math., 104 (2017), 255–275. |
| [10] | M. Bača, M. Irfan, J. Ryan, A. Semaničovǎ-Feňovčkovǎ, D. Tanna, On edge irregular reflexive labelings for the generalized friendship graphs, Mathematics, 67 (2017), 2–11. |
| [11] |
M. Basher, On the reflexive edge strength of the circulant graphs, AIMS Math., 6 (2021), 9342–9365. doi: 10.3934/math.2021543
|
| [12] | G. Chartrand, M. S. Jacobson, J. Lehel, O. R. Oellermann, S. Ruiz, F. Saba, Irregular networks, Congr. Numer., 64 (1988), 197–210. |
| [13] |
J. H. Dimitz, D. T. Garnick, A. Gyárfás, On the irregularity of $m\times n$ grid, J. Graph Theory, 16 (1992), 355–374. doi: 10.1002/jgt.3190160409
|
| [14] |
A. Gyárfás, The irregularity strength of $K_{m, m}$ is 4 for odd $m$, Discrete Math., 71 (1988), 273–274. doi: 10.1016/0012-365X(88)90106-9
|
| [15] |
Y. Ke, M. J. A. Khan, M. Ibrahim, M. K. Siddiqui, On edge irregular reflexive labeling for Cartesian product of two graphs, Eur. Phys. J. Plus, 136 (2021), 1–13. doi: 10.1140/epjp/s13360-020-01001-7
|
| [16] | J. Lahel, Facts and quests on degree irregular assignment, In: Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, New York, NY, USA, 1991,765–782. |
| [17] |
T. Nierhoff, A tight bound on the irregularity strength of graphs, SIAM. J. Discret. Math., 13 (2000), 313–323. doi: 10.1137/S0895480196314291
|
| [18] | J. Ryan, B. Munasinghe, D. Tanna, Reflexive irregular labelings, (2017), preprint. |
| [19] | N. K. Sudev, Some new results on equitable coloring parameters of graphs, Acta Math. Univ. Comenianae, 89 (2020), 109–122. |
| [20] | D. Tanna, J. Ryan, A. Semaničovǎ-Feňovčkovǎ, A reflexive edge irregular labelings of prisms and wheels, Australas. J. Combin., 69 (2017), 394–401. |
| [21] | K. K. Yoong, R. Hasni, M. Irfan, I. Taraweh, A. Ahmad, S. M. Lee, On the edge irregular reflexive labeling of corona product of graphs with path, AKCE Int. J. Graphs Combinatorics, (2021), 1–7. |
| [22] |
X. Zhang, M. Ibrahim, S. A. Bokhary, M. K. Siddiqui, Edge irregular reflexive labeling for the disjoint union of gear graphs and prism graphs, Mathematics, 6 (2018), 142. doi: 10.3390/math6090142
|
Figures(12)
Mohamed Basher. Edge irregular reflexive labeling for the $ r $-th power of the path[J]. AIMS Mathematics, 2021, 6(10): 10405-10430. doi: 10.3934/math.2021604
DownLoad: