×

On edge irregular total labeling of categorical product of two cycles. (English) Zbl 1284.05232

Summary: An edge-irregular total \(k\)-labeling \(\varphi :V(G)\cup E(G)\rightarrow \{1,2,\dots ,k\}\) of a graph \(G=(V,E)\) is a labeling of vertices and edges of \(G\) in such a way that for any different edges \(xy\) and \(x^{\prime}y^{\prime}\) their weights \(\varphi (x)+\varphi (xy)+\varphi (y)\) and \(\varphi (x^{\prime})+\varphi (x^{\prime}y^{\prime})+\varphi (y^{\prime})\) are distinct. The total edge irregularity strength, \(\mathrm{tes}(G)\), is defined as the minimum \(k\) for which \(G\) has an edge-irregular total \(k\)-labeling.
In this paper, we determine the exact value of the total edge irregularity strength of the categorical product of two cycles \(C _{n }\) and \(C _{m }\), for \(n,m\geq 3\).

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmad, A., Bača, M.: Total edge irregularity strength of a categorical product of two paths. Ars Comb. (in press) · Zbl 1324.05170
[2] Bača, M., Jendroľ, S., Miller, M., Ryan, J.: On irregular total labellings. Discrete Math. 307, 1378-1388 (2007) · Zbl 1115.05079
[3] Bohman, T., Kravitz, D.: On the irregularity strength of trees. J. Graph Theory 45, 241-254 (2004) · Zbl 1034.05015
[4] Brandt, S., Miškuf, J., Rautenbach, D.: On a conjecture about edge irregular total labellings. J. Graph Theory 57, 333-343 (2008) · Zbl 1188.05109
[5] Chartrand, G., Jacobson, M.S., Lehel, J., Oellermann, O.R., Ruiz, S., Saba, F.: Irregular networks. Congr. Numer. 64, 187-192 (1988) · Zbl 0671.05060
[6] Chunling, T., Xiaohui, L., Yuansheng, Y., Liping, W.: Irregular total labellings of Cm□Cn. Util. Math. 81, 3-13 (2010) · Zbl 1207.05175
[7] Dimitz, J.H., Garnick, D.K., Gyárfás, A.: On the irregularity strength of the m×n grid. J. Graph Theory 16, 355-374 (1992) · Zbl 0771.05055
[8] Haque, K.M.M.: Irregular total labellings of generalized Petersen graphs. Theory Comput. Syst. 50, 537-544 (2012) · Zbl 1254.05172
[9] Ivančo, J., Jendroľ, S.: Total edge irregularity strength of trees. Discuss. Math., Graph Theory 26, 449-456 (2006) · Zbl 1135.05066
[10] Jendroľ, S., Tkáč, M., Tuza, Z.: The irregularity strength and cost of the union of cliques. Discrete Math. 150, 179-186 (1996) · Zbl 0852.05054
[11] Jendroľ, S., Miškuf, J., Soták, R.: Total edge irregularity strength of complete and complete bipartite graphs. Electron. Notes Discrete Math. 28, 281-285 (2007) · Zbl 1291.05175
[12] Jendroľ, S., Miškuf, J., Soták, R.: Total edge irregularity strength of complete graphs and complete bipartite graphs. Discrete Math. 310, 400-407 (2010) · Zbl 1216.05131
[13] Miškuf, J., Jendroľ, S.: On total edge irregularity strength of the grids. Tatra Mt. Math. Publ. 36, 147-151 (2007) · Zbl 1164.05059
[14] Nurdin, Salman, A.N.M., Baskoro, E.T.: The total edge-irregular strengths of the corona product of paths with some graphs. J. Comb. Math. Comb. Comput. 65, 163-175 (2008) · Zbl 1172.05033
[15] Rall, D.F.: Total domination in categorical products of graphs. Discuss. Math., Graph Theory 25(1-2), 35-44 (2005) · Zbl 1074.05068
[16] Tardif, C., Wehlau, D.: Chromatic numbers of products of graphs: the directed and undirected versions of the Poljak-Rödl function. J. Graph Theory 51, 33-36 (2006) · Zbl 1132.05024
[17] Togni, O.: Irregularity strength of the toroidal grid. Discrete Math. 165/166, 609-620 (1997) · Zbl 0883.05083
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.