Rainbow Hamilton cycles in random regular graphs

Svante Janson; Nicholas Wormald

doi:10.1002/rsa.20146

Rainbow Hamilton cycles in random regular graphs

Svante Janson, Nicholas Wormald

Research output: Contribution to journal › Article › Research › peer-review

16 Citations (Scopus)

Abstract

A rainbow subgraph of an edge-colored graph has all edges of distinct colors. A random d-regular graph with d even, and having edges colored randomly with d/2 of each of n colors, has a rainbow Hamilton cycle with probability tending to 1 as n → ∞, for fixed d ≥ 8.

Original language	English
Pages (from-to)	35-49
Number of pages	15
Journal	Random Structures and Algorithms
Volume	30
Issue number	1-2
DOIs	https://doi.org/10.1002/rsa.20146
Publication status	Published - Jan 2007
Externally published	Yes

Access to Document

10.1002/rsa.20146

Cite this

@article{82c6acf063e240a78671ccdf0a89f205,

title = "Rainbow Hamilton cycles in random regular graphs",

abstract = "A rainbow subgraph of an edge-colored graph has all edges of distinct colors. A random d-regular graph with d even, and having edges colored randomly with d/2 of each of n colors, has a rainbow Hamilton cycle with probability tending to 1 as n → ∞, for fixed d ≥ 8.",

author = "Svante Janson and Nicholas Wormald",

year = "2007",

month = jan,

doi = "10.1002/rsa.20146",

language = "English",

volume = "30",

pages = "35--49",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley & Sons",

number = "1-2",

}

TY - JOUR

T1 - Rainbow Hamilton cycles in random regular graphs

AU - Janson, Svante

AU - Wormald, Nicholas

PY - 2007/1

Y1 - 2007/1

N2 - A rainbow subgraph of an edge-colored graph has all edges of distinct colors. A random d-regular graph with d even, and having edges colored randomly with d/2 of each of n colors, has a rainbow Hamilton cycle with probability tending to 1 as n → ∞, for fixed d ≥ 8.

AB - A rainbow subgraph of an edge-colored graph has all edges of distinct colors. A random d-regular graph with d even, and having edges colored randomly with d/2 of each of n colors, has a rainbow Hamilton cycle with probability tending to 1 as n → ∞, for fixed d ≥ 8.

UR - http://www.scopus.com/inward/record.url?scp=33846698690&partnerID=8YFLogxK

U2 - 10.1002/rsa.20146

DO - 10.1002/rsa.20146

M3 - Article

AN - SCOPUS:33846698690

SN - 1042-9832

VL - 30

SP - 35

EP - 49

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 1-2

ER -

Rainbow Hamilton cycles in random regular graphs

Abstract

Access to Document

Other files and links

Cite this