Acta Mechanica Slovaca 2015, 19(1):60-65 | DOI: 10.21496/ams.2015.008

On the Total Edge Irregularity Strength of Disjoint Union of Graphs

Martin Bača1, Joe Ryan2, Andrea Semaničová-Feňovčíková*
1 Technical University of Košice, Faculty of Mechanical Engineering, Department of Applied Mathematics and Informatics, Košice, Slovakia
2 University of Newcastle, School of Electrical Engineering and Computer Science, Callaghan NSW, Australia

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.

Keywords: Edge irregular total labeling, vertex irregular total labeling, totally irregular total labeling, total edge irregularity strength, total vertex irregularity strength

Published: March 31, 2015  Show citation

ACS AIP APA ASA Harvard Chicago Chicago Notes IEEE ISO690 MLA NLM Turabian Vancouver
Bača, M., Ryan, J., & Semaničová-Feňovčíková, A. (2015). On the Total Edge Irregularity Strength of Disjoint Union of Graphs. Acta Mechanica Slovaca, 19(1), 60-65. doi: 10.21496/ams.2015.008
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    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. Go to original source...
    5. Amar D., Togni O., Irregularity strength of trees, Discrete Math., vol 190, 1998, p. 15-38. Go to original source...
    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. Go to original source...
    7. Anholcer M., Palmer C., Irregular labellings of Circulant graphs, Discrete Math. vol 312, 2012, p. 3461-3466. Go to original source...
    8. Bača M., Jendroľ S., Miller M., Ryan J., On irregular total labellings, Discrete Math., vol 307, 2007, p. 1378-1388. Go to original source...
    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. Go to original source...
    10. Bača M., Siddiqui M.K., Total edge irregularity strength of generalized prism, Applied Math. Comput., vol 235, 2014, p. 168-173. Go to original source...
    11. Bloom G.S., Golomb S.W., Applications of numbered undirected graphs, Proc. IEEE, vol 65, 1977, p. 562-570. Go to original source...
    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. Go to original source...
    13. Bohman T., Kravitz D., On the irregularity strength of trees, J. Graph Theory, vol 45, 2004, p. 241-254. Go to original source...
    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. Go to original source...
    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. Go to original source...
    17. Frieze A., Gould R.J., Karonski M., Pfender F., On graph irregularity strength, J. Graph Theory, vol 41, 2002, p. 120-137. Go to original source...
    18. Haque M.K.M., Irregular total labellings of generalized Petersen graphs, Theory Comput. Syst., vol 50, 2012, p. 537-544. Go to original source...
    19. Ivančo J., Jendroľ S., Total edge irregularity strength of trees, Discussiones Math. Graph Theory, vol 26, 2006, p. 449-456. Go to original source...
    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. Go to original source...
    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. Go to original source...
    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. Go to original source...
    23. Majerski P., Przybylo J., Total vertex irregularity strength of dense graphs, J. Graph Theory, vol 76(1), 2014, p. 34-41. Go to original source...
    24. Majerski P., Przybylo J., On the irregularity strength of dense graphs, SIAM J. Discrete Math., vol 28(1), 2014, p. 197-205. Go to original source...
    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. Go to original source...
    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. Go to original source...
    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 t 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. Go to original source...
    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.

    This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content