✦ LIBER ✦

Properly colored hamilton cycles in edge-colored complete graphs

✍ Scribed by N. Alon; G. Gutin

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 156 KB
Volume: 11
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199709)11:2<179::aid-rsa5>3.0.co;2-p

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that, for ⑀ ) 0 and n ) n ⑀ , any complete graph K on n vertices 0 ' Ž . whose edges are colored so that no vertex is incident with more than 1 y 1r 2 y ⑀ n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and n any such K contains a cycle of length k in which adjacent edges have distinct colors.

📜 SIMILAR VOLUMES

Edge disjoint Hamilton cycles in graphs

✍ Guojun Li 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 1 views

Special monochromatic trees in two-color

Special monochromatic trees in two-colored complete graphs

✍ Chen, Guantao; Schelp, Richard H.; ?olt�s, ?ubom�r 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB 👁 1 views

For a positive integer k, a set of k + 1 vertices in a graph is a k-cluster if the difference between degrees of any two of its vertices is at most k -1. Given any tree T with at least k 3 edges, we show that for each graph G of sufficiently large order, either G or its complement contains a copy of

Edge disjoint Hamilton cycles in sparse

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk

✍ Bollob�s, B.; Cooper, C.; Fenner, T. I.; Frieze, A. M. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 2 views

Let G n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A k , if G contains (k -1)/2 edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size n/2 . We prove that, for