Back to Search
Start Over
Rainbow subgraphs in Hamiltonian cycle decompositions of complete graphs.
- Source :
-
Discrete Mathematics . Aug2023, Vol. 346 Issue 8, pN.PAG-N.PAG. 1p. - Publication Year :
- 2023
-
Abstract
- A Hamiltonian cycle decomposition of a complete graph K 2 n + 1 is an n -edge-coloring of K 2 n + 1 such that each color class is a Hamiltonian cycle. For a given Hamiltonian cycle decomposition, a subgraph of K 2 n + 1 is called rainbow if all its edges are colored differently. Let H be any subgraph of K 2 n + 1 consisting of n edges. In 1999, Wu conjectured that K 2 n + 1 has a Hamiltonian cycle decomposition such that H is rainbow. In this paper, we show that the conjecture is true in the cases that | H | ≤ n + 1 , or H is a linear forest, or n ≤ 5. Using this result, we partially confirm a conjecture on restricted size Ramsey numbers due to Miralaei and Shahsiah in 2020. [ABSTRACT FROM AUTHOR]
- Subjects :
- *RAMSEY numbers
*SUBGRAPHS
*COMPLETE graphs
*HAMILTONIAN graph theory
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 346
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 163931678
- Full Text :
- https://doi.org/10.1016/j.disc.2023.113479