ON SUM EDGE-COLORINGS OF SOME REGULAR GRAPHS
DOI:
https://doi.org/10.46991/PYSUA.2026.60.1.014Keywords:
edge-coloring, sum edge-coloringAbstract
A sum edge-coloring of a graph is an assignment of positive integers to the edges of the graph, so that adjacent edges correspond to different numbers (colors) and the sum of the numbers on all the edges is minimum possible. This minimum possible sum is called the edge-chromatic sum of the graph, and the minimal number of colors needed for a sum edge-coloring is called the edge-strength of the graph. In this paper, we give the exact values of the edge-chromatic sums and edge-strengths for cycle powers and generalized cycles.
References
West D.B. Introduction to Graph Theory. Prentice-Hall, New Jersey (2001). https://dwest.web.illinois.edu/igt/
Bar-Noy A., Bellare M., et al. On Chromatic Sums and Distributed Resource Allocation. Inform. and Comput. 140 (1998), 183-202. https://doi.org/10.1006/inco.1997.2677
Salavatipour M.R. On Sum Coloring of Graphs. Discrete Appl. Math. 127 (2003), 477-488. https://doi.org/10.1016/S0166-218X(02)00249-4
Giaro K., Kubale M. Edge-Chromatic Sum of Trees and Bounded Cyclicity Graphs. Inform. Process. Lett. 75 (2000), 65-69. https://doi.org/10.1016/S0020-0190(00)00072-7
Petrosyan P.A., Kamalian R.R. On Sum Edge-Coloring of Regular, Bipartite and Split Graphs. Discrete Appl. Math. 165 (2014), 263-269. https://doi.org/10.1016/j.dam.2013.09.025
Hajiabolhassan H., Mehrabadi M.L., Tusserkani R. Minimal Coloring and Strength of Graphs. Discrete Math. 215 (2000), 265-270. https://doi.org/10.1016/S0012-365X(99)00319-2
Parker E.T. Edge Coloring Numbers of Some Regular Graphs. Proc. of the American Math. Society 37 (1973), 623-624. https://doi.org/10.1090/S0002-9939-1973-0313103-0
Meidanis J. Edge Coloring of Cycle Powers is Easy. Unpublished Manuscript (1998). Available at www.ic.unicamp.br/~meidanis/research/edge/cpowers.pdf
Mikaelyan H.V. On Sum Edge-colorings of Complete Tripartite Graphs. Proc. of the YSU A. Phys. and Math. Sci. 59 (2025), 69-83. https://doi.org/10.46991/PYSUA.2025.59.3.069
Bermond J.-C., Favaron O., Maheo M. Hamiltonian Decomposition of Cayley Graphs of Degree 4. J. Combin. Theory Ser. B 46 (1989), 142-153. https://doi.org/10.1016/0095-8956(89)90040-3
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Proceedings of the YSU
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
