Rainbow Hamilton cycles in random regular graphs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

A rainbow subgraph of an edge-coloured graph has all edges of distinct colours. A random d-regular graph with d even, and having edges coloured randomly with d/2 of each of n colours, has a rainbow Hamilton cycle with probability tending to 1 as n tends to infinity, provided d is at least 8.
16 pages

Keywords

Combinatorics, Probability, 05C80 (Primary); 05C15, 05C45, 60C05 (Secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/75992

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0508145
 http://arxiv.org/abs/math/0508145

Collections

arXiv