✦ LIBER ✦

A Hamiltonian game on Kn,n

✍ Scribed by Xiaoyun Lu

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 426 KB
Volume: 142
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)e0218-s

No coin nor oath required. For personal study only.

✦ Synopsis

Let K,,, be the complete bipartite graph of order 2n. Two players, maker and breaker, alternately take previously untaken edges of K,.,, one edge per move, with the breaker going first. The game ends when all edges of K,,, have been taken. Then the edges taken by the maker induce a graph G. The maker wants G to have as many edge disjoint Hamilton cycles as possible, and the breaker wants G to have as few such cycles as possible. We prove that the maker can achieve & n edge-disjoint Hamilton cycles for large n.

📜 SIMILAR VOLUMES

A fast infiltration game on n arcs

✍ V. J. Baston; A. Y. Garnaev 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 532 KB

Starting from a safe base, an Infiltrator tries to reach a sensitive zone within a given time limit without being detected by a Guard. The Infiltrator can move with speed at most u , while the Guard can only perform a restricted number of searches. A discrete variant of this zero-sum game played on

The game of “N questions” on a tree

✍ Ronald L. Rivest 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 330 KB

On the number of spanning trees of Kn an

On the number of spanning trees of Kn and Km, n

✍ Moh'd Z. Abu-Sbeih 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 170 KB

The object of this paper is to introduce a new technique for showing that the number of labelled spanning trees of the complete bipartite graph K,,,, is IT(m, n)l = m"-'n"-'. As an application, we use this technique to give a new proof of Cayley's formula IT(n)1 = nnm2, for the number of labelled s

A new method of generating Hamiltonian c

A new method of generating Hamiltonian cycles on the n-cube

✍ Mark Ramras 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 196 KB

A Remark on Hamiltonian Cycles

✍ Vu-Dinh-Hoa 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 309 KB

## Abstract Let __G__ be an undirected and simple graph on __n__ vertices. Let ω, α and χ denote the number of components, the independence number and the connectivity number of __G. G__ is called a 1‐tough graph if ω(__G__ – __S__) ⩽ |__S__| for any subset __S__ of __V__(__G__) such that ω(__G__ −

A note on Hamiltonian circuits

✍ V. Chvátal; P. Erdös 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 229 KB