✦ LIBER ✦

Polychromatic Hamilton cycles

✍ Scribed by Alan Frieze; Bruce Reed

Book ID: 103056259
Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 303 KB
Volume: 118
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90054-w

No coin nor oath required. For personal study only.

✦ Synopsis

The edges of the complete graph K, are coloured so that no colour appears more than k = k(n) times, k=rn/(A In n)l, for some sufficiently large A. We show that there is always a Hamiltonian cycle in which each edge is a different colour. The proof technique is probabilistic.

📜 SIMILAR VOLUMES

Hamilton cycles in prisms

✍ Tomáš Kaiser; Zdeněk Ryjáček; Daniel Král; Moshe Rosenfeld; Heinz-Jürgen Voss 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 300 KB

## Abstract The prism over a graph __G__ is the Cartesian product __G__ □ __K__~2~ of __G__ with the complete graph __K__~2~. If __G__ is hamiltonian, then __G__□__K__~2~ is also hamiltonian but the converse does not hold in general. Having a hamiltonian prism is shown to be an interesting relaxati

Knots in Hamilton Cycles

✍ Mansfield, Marc L. 📂 Article 📅 1994 🏛 American Chemical Society 🌐 English ⚖ 376 KB

Directed Hamilton Cycles in Digraphs and

Directed Hamilton Cycles in Digraphs and Matching Alternating Hamilton Cycles in Bipartite Graphs

✍ Zhang, Zan-Bo; Zhang, Xiaoyan; Wen, Xuelian 📂 Article 📅 2013 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 258 KB

Independence trees and Hamilton cycles

✍ Broersma, Hajo; Tuinstra, Hilde 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 268 KB

Let G be a connected graph on n vertices. A spanning tree T of G is called an independence tree, if the set of end vertices of T (vertices with degree one in T ) is an independent set in G. If G has an independence tree, then α t (G) denotes the maximum number of end vertices of an independence tree

Neighborhood unions and hamilton cycles

✍ Bill Jackson 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 392 KB

## Abstract Let __G__ be a graph on __n__ vertices and __N__~2~(__G__) denote the minimum size of __N__(__u__) ∪ __N__(__v__) taken over all pairs of independent vertices __u, v__ of __G__. We show that if __G__ is 3‐connected and __N__~2~(__G__) ⩾ ½(__n__ + 1), then __G__ has a Hamilton cycle. We

Oriented hamilton cycles in digraphs

✍ Roland Häggkvist; Andrew Thomason 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 473 KB

## Abstract We show that a directed graph of order __n__ will contain __n__‐cycles of every orientation, provided each vertex has indegree and outdegree at least (1/2 + __n__^‐1/6^)__n__ and __n__ is sufficiently large. © 1995 John Wiley & Sons, Inc.