Szczegóły publikacji
Opis bibliograficzny
Decompositions of pseudographs into closed trails of even sizes / Sylwia CICHACZ, Jakub PRZYBYŁO, Mariusz WOŹNIAK // Discrete Mathematics ; ISSN 0012-365X . — 2009 — vol. 309 iss. 15, s. 4903–4908. — Bibliogr. s. 4908, Abstr.
Autorzy (3)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 48413 |
|---|---|
| Data dodania do BaDAP | 2009-11-13 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2008.04.024 |
| Rok publikacji | 2009 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Mathematics |
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 ⌈ sqrt(2 n) ⌉ if all components of G have even orders. © 2008 Elsevier B.V. All rights reserved.
