×

Total irregularity strength of some cubic graphs. (English) Zbl 1482.05293

Summary: Let \(G = (V,E)\) be a graph. A total labeling \(\psi : V \bigcup E \rightarrow \{1, 2, \dots, k\}\) is called totally irregular total \(k\)-labeling of \(G\) if every two distinct vertices \(u\) and \(v\) in \(V (G)\) satisfy \(wt(u) \neq wt(v)\), and every two distinct edges \(u_1 u_2\) and \(v_1 v_2\) in \(E(G)\) satisfy \(wt(u_1 u_2) \neq wt(v_1 v_2)\) where \(wt(u) = \psi (u) + \sum_{uv \in E(G)} \psi (uv)\) and \(wt(u_1 u_2) = \psi (u_1) + \psi (u_1u_2) + \psi (u_2)\). The minimum \(k\) for which a graph \(G\) has a totally irregular total \(k\)-labeling is called the total irregularity strength of \(G\), denoted by \(ts(G)\). In this paper, we determine the exact value of the total irregularity strength of cubic graphs.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
Full Text: DOI

References:

[1] A. Ahmad, M. Bača, and M. K. Siddiqui, “On edge irregular total labeling of categorical product of two cycles”, Theory of computing systems, vol. 54, no. 1, pp. 1-12, 2014. Doi: 10.1007/s00224-013-9470-3 · Zbl 1284.05232
[2] A. Ahmad , M. Ibrahim, and M. K. Siddiqui, “On the total irregularity strength of Generalized Petersen Graph”, Mathematical reports, vol. 18, no. 2, pp. 197-204, 2016. [On line]. Available: https://bit.ly/36JNCNq · Zbl 1389.05147
[3] A. Ahmad , M. Bača , Y. Bashir and M. K. Siddiqui, “Total edge irregularity strength of strong product of two paths”, Ars combinatoria, vol. 106, pp. 449-459, 2012. [On line]. Available: https://bit.ly/3hSccSO · Zbl 1289.05407
[4] A. Ahmad , S. A. Bokhari, M. Imran, and A. Q. Baig, “Vertex irregular total labeling of cubic graphs”, Utilitas mathematica, vol. 91, pp. 287-299, 2013. [On line]. Available: https://bit.ly/3irw0v9 · Zbl 1300.05272
[5] O. Al-Mushayt, A. Ahmad , and M. K. Siddiqui, “On the total edge irregularity strength of hexagonal grid graphs”, Australasian journal of combinatorics, vol. 53, pp. 263-271, 2012. [On line]. Available: https://bit.ly/2VZpCnr · Zbl 1256.05208
[6] A. Ahmad , O. Al Mushayt, and M. K. Siddiqui, “Total edge irregularity strength of strong product of cycles and paths”, Scientific Bulletin - “Politehnica” University of Bucharest. Series A, Applied mathematics and physics (Online), vol. 76, no. 4, pp. 147-156, 2014. [On line]. Available: https://bit.ly/2UUAEK4 · Zbl 1349.05284
[7] A. Ahmad , M. K. Siddiqui, and D. Afzal, “On the total edge irregularity strength of zigzag graphs”, Australasian journal of combinatorics, vol. 54, pp. 141-149, 2012. [On line]. Available: https://bit.ly/3wLjjAw · Zbl 1278.05204
[8] M. Anholcer and C. Palmer, “Irregular labelings of circulant graphs”, Discrete mathematics, vol. 312, no. 23, pp. 3461-3466, 2012. Doi: 10.1016/j.disc.2012.06.017 · Zbl 1257.05145
[9] M. Bača , S. Jendro’l, M. Miller, and J. Ryan , “On irregular total labellings”, Discrete mathematics, vol. 307, no. 11-12, pp. 1378-1388, 2007. Doi: 10.1016/j.disc.2005.11.075 · Zbl 1115.05079
[10] M. Bača , andM. K. Siddiqui , “Total edge irregularity strength of generalized prism”, Applied mathematics and computation, vol. 235, pp. 168-173, 2014. Doi: 10.1016/j.amc.2014.03.001 · Zbl 1334.05135
[11] G. Chartrand, M. S. Jacobson, J. Lehel, O. R. Oellermann, S. Ruiz, and F. Saba, “Irregular networks”, Congressus numerantium, vol. 64, 1988, pp. 187-192. [On line]. Available: https://bit.ly/2UrP9oS
[12] C. Tong, L. Xiaohui, Y. Yuansheng, and W. Liping, “Irregular total labellings of C_m⎕C_n”, Utilitas mathematica, vol. 81, pp. 3-13, 2010. · Zbl 1207.05175
[13] C. Tong , L. Xiaohui , Y. Yuansheng , andW. Liping , “Irregular total labellings of some families of graphs”, Indian journal of pure and applied mathematics, vol. 40, no. 3, pp. 155-181, 2009. [On line]. Available: https://bit.ly/3xVxMez · Zbl 1185.05123
[14] J. H. Dimitz, D. K. Garnick and A. Gyárfás, “On the irregularity strength of the m × n grid”, Journal of graph theory, vol. 16, no. 4, pp. 355-374, 1992. Doi: 10.1002/jgt.3190160409 · Zbl 0771.05055
[15] J. Ivančo andS. Jendro’l , “Total edge irregularity strength of trees”, Discussiones mathematicae graph theory, vol. 26, no. 3, pp. 449-456, 2006. Doi: 10.7151/dmgt.1337 · Zbl 1135.05066
[16] S. Jendro’l , J. Miškuf, and R. Soták, “Total edge irregularity strength of complete and complete bipartite graphs”, Electronic notes in discrete mathematics, vol. 28, pp. 281-285, 2007. Doi: 10.1016/j.endm.2007.01.041 · Zbl 1291.05175
[17] S. Jendro’l , J. Miškuf , and R. Soták, “Total edge irregularity strength of complete graphs and complete bipartite graphs”, Discrete mathematics, vol. 310, no. 3, pp. 400-407, 2010. Doi: 10.1016/j.disc.2009.03.006 · Zbl 1216.05131
[18] C. C. Marzuki, A. N. M. Salman, andM. Miller , “On the total irregularity strength on cycles and paths”, Far East journal of mathematical sciences, vol. 82, no. 1, pp. 1-21, 2013. · Zbl 1291.05177
[19] J. Miškuf andS. Jendro’l , “On total edge irregularity strength of the grids”, Tatra mountains mathematical publications, vol. 36, pp. 147-151, 2007. · Zbl 1164.05059
[20] Nurdin, E. T. Baskoro, A. N. M. Salman and N. N. Gaos, “On the total vertex irregularity strength of trees”, Discrete mathematics, vol. 310, no. 21, pp. 3043-3048, 2010. Doi: 10.1016/j.disc.2010.06.041 · Zbl 1208.05014
[21] R. Ramdani and A. N. M. Salman, “On the total irregularity strength of some cartesian product graphs”, AKCE International journal of graphs and combinatorics, vol. 10, no. 2, pp. 199-209, 2013. Doi: 10.1080/09728600.2013.12088736 · Zbl 1301.05301
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.