Volume 19, Issue No.1

KEY WORDS

Edge irregular total labeling, vertex irregular total labeling, totally irregular total labeling, total edge irregularity strength, total vertex irregularity strength.

ABSTRACT

For a simple graph G=(V(G),E(G)), a total labeling f: V(G)υE(G) → {1,2,...,k} is called k-labeling. The weight of an edge xy in G, denoted by wtf(xy), is the sum of the edge label itself and the labels of end vertices x and y, i.e. wtf(xy)=f(x)+f(xy)+f(y). A total k-labeling is defined to be an edge irregular total k-labeling of the graph G if for every two different edges xy and x′y′ there is wtf(xy)≠wtf(x′y′). The minimum k for which the graph G has an edge irregular total k-labeling is called the total edge irregularity strength of G, denoted by tes(G). In this paper, we estimate the upper bound of the total edge irregularity strength of disjoint union of multiple copies of a graph and we prove that this upper bound is tight.

CITATION INFORMATION

Acta Mechanica Slovaca. Volume 19, Issue 1, Pages 60–65, ISSN 1335-2393

DOWNLOAD

 On the Total Edge Irregularity Strength of Disjoint Union of Graphs

REFERENCES

[1] Ahmad A., Bača M., On vertex irregular total labelings, Ars Combin., vol 112, 2013, p. 129-139.

[2] Ahmad A., Bača M., Total edge irregularity strength of a categorical product of two paths, Ars Combin., vol 114, 2014, p. 203-212.

[3] Ahmad A., Bača M., Bashir Y., Siddiqui M.K., Total edge irregularity strength of strong product of two paths, Ars Combin., vol 106, 2012, p. 449-459.

[4] Ahmad A., Bača M., Siddiqui M.K., On edge irregular total labeling of categorical product of two cycles, Theory Comput. Syst., vol 54(1), 2014, p. 1-12.

[5] Amar D., Togni O., Irregularity strength of trees, Discrete Math., vol 190, 1998, p. 15-38.

[6] Anholcer M., Kalkowski M., Przybylo J., A new upper bound for the total vertex irregularity strength of graphs, Discrete Math., vol 309, 2009, p. 6316-6317.

[7] Anholcer M., Palmer C., Irregular labellings of Circulant graphs, Discrete Math. vol 312, 2012, p. 3461-3466.

[8] Bača M., Jendroľ S., Miller M., Ryan J., On irregular total labellings, Discrete Math., vol 307, 2007, p. 1378-1388.

[9] Bača M., Lascsáková M., Siddiqui M.K., Total edge irregularity strength of toroidal fullerene, Math. Comput. Science, vol 7, 2013, p. 487-492.

[10] Bača M., Siddiqui M.K., Total edge irregularity strength of generalized prism, Applied Math. Comput., vol 235, 2014, p. 168-173.

[11] Bloom G.S., Golomb S.W., Applications of numbered undirected graphs, Proc. IEEE, vol 65, 1977, p. 562-570.

[12] Bloom G.S., Golomb S.W., Numbered complete graphs, unusual rules, and assorted applications, Theory and Applications of Graphs, Lecture Notes in Math. vol 642, 1978, p. 53-65.

[13] Bohman T., Kravitz D., On the irregularity strength of trees, J. Graph Theory, vol 45, 2004, p. 241-254.

[14] Brandt S., Miškuf J., Rautenbach D., On a conjecture about edge irregular total labellings, J. Graph Theory, vol 57, 2008, p. 333-343.

[15] Chartrand G., Jacobson M.S., Lehel J., Oellermann O.R., Ruiz S., Saba F., Irregular networks, Congr. Numer., vol 64, 1988, p. 187-192.

[16] Faudree R.J., Jacobson M. S., Lehel J., Schlep R.H., Irregular networks, regular graphs and integer matrices with distinct row and column sums, Discrete Math. vol 76, 1988, p. 223-240.

[17] Frieze A., Gould R.J., Karonski M., Pfender F., On graph irregularity strength, J. Graph Theory, vol 41, 2002, p. 120-137.

[18] Haque M.K.M., Irregular total labellings of generalized Petersen graphs, Theory Comput. Syst., vol 50, 2012, 537-544.

[19] Ivančo J., Jendroľ S., Total edge irregularity strength of trees, Discussiones Math. Graph Theory, vol 26, 2006, 449-456.

[20] Jendroľ S., Miškuf J., Soták R., Total edge irregularity strength of complete and complete bipartite graphs, Electron. Notes Discrete Math., vol. 28, 2007, p. 281-285.

[21] Jendroľ S., Miškuf J., Soták R., Total edge irregularity strength of complete graphs and complete bipartite graphs, Discrete Math., vol 310, 2010, p. 400-407.

[22] Kalkowski M., Karonski M., Pfender F., A new upper bound for the irregularity strength of graphs, SIAM J. Discrete Math., vol 25(3), 2011, p. 1319-1321.

[23] Majerski P., Przybylo J., Total vertex irregularity strength of dense graphs, J. Graph Theory, vol 76(1), 2014, p. 34-41.

[24] Majerski P., Przybylo J., On the irregularity strength of dense graphs, SIAM J. Discrete Math., vol 28(1), 2014, p. 197-205.

[25] Miškuf J., Jendroľ S., On total edge irregularity strength of the grids, Tatra Mt. Math. Publ., vol 36, 2007, p. 147-151.

[26] Nierhoff T., A tight bound on the irregularity strength of graphs, SIAM J. Discrete Math., vol 13, 2000, p. 313-323.

[27] Nurdin, Salman A.N.M., Baskoro E.T., The total edge-irregular strengths of the corona product of paths with some graphs, J. Combin. Math. Combin. Comput., vol 65, 2008, p. 163-175.

[28] Nurdin, Baskoro E.T., Salman A.N.M., Gaos N.N., On the total vertex irregularity strength of trees, Discrete Math., vol 310, 2010, p. 3043-3048.

[29] Nurdin, Baskoro E.T., Salman A.N.M., Gaos N.N., On the total vertex irregular labelings for several types of trees, Utilitas Math., vol 83, 2010, p. 277-290.

[30] Nurdin, Salman A.N.M., Gaos N.N., Baskoro E.T., On the total vertex-irregular strength of a disjoint union of copies of a path, J. Combin. Math. Combin. Comput., vol 71, 2009, p. 227-233.

[31] Przybylo J., Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J. Discrete Math., vol 23, 2009, p. 511-516.

[32] Wijaya K., Slamin, Total vertex irregular labeling of wheels, fans, suns and friendship graphs, J. Combin. Math. Combin. Comput., vol 65, 2008, p. 103-112.

[33] Wijaya K., Slamin, Surahmat, Jendroľ S., Total vertex irregular labeling of complete bipartite graphs, J. Combin. Math. Combin. Comput., vol 55, 2005, p. 129-136.

Latest Issue

ams 2 2016

Download