Decompositions of pseudographs into closed trails of even sizes |
| |
Authors: | Sylwia Cichacz Jakub Przyby?o Mariusz Wo?niak |
| |
Institution: | AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Kraków, Poland |
| |
Abstract: | We consider a graph Ln, with n even, which is a complete graph with an additional loop at each vertex and minus a 1-factor and we prove that it is edge-disjointly decomposable into closed trails of even lengths greater than four, whenever these lengths sum up to the size of the graph Ln. We also show that this statement remains true if we remove from Ln two loops attached to nonadjacent vertices. Consequently, we improve P. Wittmann’s result on the upper bound of the irregular coloring number c(G) of a 2-regular graph G of size n, by determining that this number is, with a discrepancy of at most one, equal to if all components of G have even orders. |
| |
Keywords: | Pseudograph decomposition Irregular edge coloring Irregular coloring number |
本文献已被 ScienceDirect 等数据库收录! |
|