A labeling of a graph is an assignment that carries some sets of graph elements into numbers (usually the non negative integers). The total $ k $-labeling is an assignment $ f_{e} $ from the edge set to the set $ \{1, 2, ..., k_{e} \} $ and assignment $ f_{v} $ from the vertex set to the set $ \{0, 2, 4, ..., 2k_{v} \} $, where $ k = max\{k_{e}, 2k_{v} \} $. An edge irregular reflexive $ k $-labeling of the graph $ G $ is the total $ k $-labeling, if distinct edges have distinct weights, where the edge weight is defined as the sum of label of that edge and the labels of the end vertices. The minimum $ k $ for which the graph $ G $ has an edge irregular reflexive $ k $-labeling is called the reflexive edge strength of the graph $ G $, denoted by $ res(G) $. In this paper we study the edge reflexive irregular $ k $-labeling for some cases of circulant graphs and determine the exact value of the reflexive edge strength for several classes of circulant graphs.
Citation: Mohamed Basher. On the reflexive edge strength of the circulant graphs[J]. AIMS Mathematics, 2021, 6(9): 9342-9365. doi: 10.3934/math.2021543
A labeling of a graph is an assignment that carries some sets of graph elements into numbers (usually the non negative integers). The total $ k $-labeling is an assignment $ f_{e} $ from the edge set to the set $ \{1, 2, ..., k_{e} \} $ and assignment $ f_{v} $ from the vertex set to the set $ \{0, 2, 4, ..., 2k_{v} \} $, where $ k = max\{k_{e}, 2k_{v} \} $. An edge irregular reflexive $ k $-labeling of the graph $ G $ is the total $ k $-labeling, if distinct edges have distinct weights, where the edge weight is defined as the sum of label of that edge and the labels of the end vertices. The minimum $ k $ for which the graph $ G $ has an edge irregular reflexive $ k $-labeling is called the reflexive edge strength of the graph $ G $, denoted by $ res(G) $. In this paper we study the edge reflexive irregular $ k $-labeling for some cases of circulant graphs and determine the exact value of the reflexive edge strength for several classes of circulant graphs.
| [1] | A. Ahmad, O. B. S. Al-Mushayt, M. Baća, On edge irregularity strength of graphs, Appl. Math. Comput., 243 (2014), 607–610. |
| [2] | 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. |
| [3] |
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
|
| [4] | A. Ahmad, M. K. Siddiqui, D. Afzal, On the total edge irregularity strength of zigzag graphs, Australas. J. Comb., 54 (2012), 141–150. |
| [5] | A. Ahmad, M. Baća, On Vertex Irregular Total Labelings, Ars Comb., 112 (2013), 129–139. |
| [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. Aigner, E. Triesch, Irregular assignments of trees and forests, SIAM J. Discrete Math., 3 (1990), 439–449. doi: 10.1137/0403038
|
| [8] | O. B. S. Al-Mushayt, A. Ahmad, M. K. Siddiqui, On the total edge irregularity strength of hexagonal grid graphs, Australas. J. Comb., 53 (2012), 263–272. |
| [9] |
D. Amar, O. Togni, Irregularity strength of trees, Discrete Math., 190 (1998), 15–38. doi: 10.1016/S0012-365X(98)00112-5
|
| [10] |
M. Anholcer, M. Kalkowski, J. Przybyło, A new upper bound for the total vertex irregularity strength of graphs, Discrete Math., 309 (2009), 6316–6317. doi: 10.1016/j.disc.2009.05.023
|
| [11] |
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
|
| [12] | M. Baća, M. K. Siddiqui, Total edge irregularity strength of generalized prism, Appl. Math. Comput., 235 (2014), 168–173. |
| [13] | M. Baća, M. K. Siddiqui, On total edge irregularity strength of strong product of two cycles, Util. Math., 104 (2017), 255–275. |
| [14] | 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. |
| [15] |
M. Baća, Y. Bashir, M. F. Nadeem, A. Shabbir, On super edge-antimagicness of circulant graphs, Graphs Comb., 31 (2015), 2019–2028. doi: 10.1007/s00373-014-1505-2
|
| [16] |
E. T. Baskoro, A. N. M. Salman, N. N. Gaos, On the total vertex irregularity strength of trees, Discrete Math., 310 (2010), 3043–3048. doi: 10.1016/j.disc.2010.06.041
|
| [17] |
J. C. Bermond, F. Comellas, D. F. Hsu, Distributed loop computer-networks: a survey, J. Parallel Distrib. Comput., 24 (1995), 2–10. doi: 10.1006/jpdc.1995.1002
|
| [18] |
T. Bohman, D. Kravitz, On the irregularity strength of trees, J. Graph Theory, 45 (2004), 241–254. doi: 10.1002/jgt.10158
|
| [19] |
R. E. Burkard, W. Sandholzer, Efficiently solvable special cases of bottleneck travelling salesman problems, Discrete Appl. Math., 32 (1991), 61–76. doi: 10.1016/0166-218X(91)90024-Q
|
| [20] | G. Chartrand, M. S. Jacobson, J. Lehel, O. R. Oellermann, S. Ruiz, F. Saba, Irregular networks, Congr. Numer, 64 (1988), 250. |
| [21] |
R. J. Faudree, R. H. Schelp, M. S. Jacobson, J. Lehel, Irregular networks, regular graphs and integer matrices with distinct row and column sums, Discrete Math., 76 (1989), 223–240. doi: 10.1016/0012-365X(89)90321-X
|
| [22] | A. Frieze, R. J. Gould, M. Karoński, F. Pfender, On graph irregularity strength, J. Graph Theory, 41 (2002), 120–137. |
| [23] |
K. M. M. Haque, Irregular total labellings of generalized Petersen graphs, Theory Comput. Syst., 50 (2012), 537–544. doi: 10.1007/s00224-011-9350-7
|
| [24] |
C. Heuberger, On planarity and colorability of circulant graphs, Discrete Math., 268 (2003), 153–169. doi: 10.1016/S0012-365X(02)00685-4
|
| [25] | P. Jalilolghadr, A. P. Kazemi, A. Khodkar, Total dominator coloring of circulant graphs $ C_n (a, b) $, arXiv preprint, (2019), arXiv: 1905.00211. |
| [26] |
M. Kalkowski, M. Karoński, F. Pfender, A new upper bound for the irregularity strength of graphs, SIAM J. Discrete Math., 25 (2011), 1319–1321. doi: 10.1137/090774112
|
| [27] |
A. Kotzig, A. Rosa, Magic valuations of finite graphs, Can. Math. Bull., 13 (1970), 451–461. doi: 10.4153/CMB-1970-084-1
|
| [28] |
P. Majerski, J. Przybyło, Total vertex irregularity strength of dense graphs, J. Graph Theory, 76 (2014), 34–41. doi: 10.1002/jgt.21748
|
| [29] |
M. Meszka, R. Nedela, A. Rosa, The chromatic number of 5-valent circulants, Discrete Math., 308 (2008), 6269–6284. doi: 10.1016/j.disc.2007.11.065
|
| [30] |
J. Miškuf, R. Soták, Total edge irregularity strength of complete graphs and complete bipartite graphs, Discrete Math., 310 (2010), 400–407. doi: 10.1016/j.disc.2009.03.006
|
| [31] | J. Ryan, B. Munasinghe, D. Tanna, Reflexive irregular labelings, 2017, preprint. |
| [32] | J. Sedláček, Problem 27 in Thery of Graphs and Its Applications in Proceedings of the Symposium Smolenice, 1963,163–167. |
| [33] | B. M. Stewart, Magic graphs, Can. J. Math., 18 (1966), 1031–1059. |
| [34] | N. Sudev, Some new results on equitable coloring parameters of graphs, Acta Math. Univ. Comenianae, 89 (2019), 109–122. |
| [35] | D. Tanna, J. Ryan, A. Semaničovǎ-Feňovčkovǎ, A reflexive edge irregular labelings of prisms and wheels, Australas. J. Comb., 69 (2017), 394–401. |
| [36] |
I. Tarawneh, R. Hasni, A. Ahmad, On the edge irregularity strength of corona product of cycle with isolated vertices, AKCE Int. J. Graphs Comb., 13 (2016), 213–217. doi: 10.1016/j.akcej.2016.06.010
|
| [37] | H. G. Yeh, X. Zhu, 4-colorable 6-regular graphs, Discrete Math., 273 (2003), 261–274. |
| [38] |
X. Zhang, M. Ibrahim, 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(4)
Mohamed Basher. On the reflexive edge strength of the circulant graphs[J]. AIMS Mathematics, 2021, 6(9): 9342-9365. doi: 10.3934/math.2021543
DownLoad: