✦ LIBER ✦

Bounds on the number of Hamiltonian circuits in the n-cube

✍ Scribed by Robert James Douglas

Publisher: Elsevier Science
Year: 1977
Tongue: English
Weight: 224 KB
Volume: 17
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(77)90143-1

No coin nor oath required. For personal study only.

✦ Synopsis

New upper anti lower ~,ounds arc found for the number of HamilI(,nian circuits in the graph of Ihe r -cube.

(2) -1 i,, ,,'

We show that h(n)~ [n(n -I)/212 .... '~'"""',"' = U~(e,)

(3)

📜 SIMILAR VOLUMES

Bounds for the crossing number of the N-

Bounds for the crossing number of the N-cube

✍ Tom Madej 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 658 KB

## Abstract Let __Q__~__n__~ denote the n‐dimensional hypercube. In this paper we derive upper and lower bounds for the crossing number __v__(__Q__~__n__~), i.e., the minimum number of edge‐crossings in any planar drawing of __Q__~__n__~. The upper bound is close to a result conjectured by Eggleton

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

On the number of Hamiltonian cycles in t

On the number of Hamiltonian cycles in triangulations

✍ Jan Kratochvil; Dainis Zeps 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB 👁 2 views

It is proved that if a planar triangulation different from K3 and K4 contains a Hamiltonian cycle, then it contains at least four of them. Together with the result of Hakimi, Schmeichel, and Thomassen [21, this yields that, for n 2 12, the minimum number of Hamiltonian cycles in a Hamiltonian planar

On the number of Hamiltonian cycles in t

On the number of Hamiltonian cycles in tournaments

✍ Carsten Thomassen 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 949 KB

The main results assert that the minimum number of Hamiltonian bypasses in a strong tournament of order n and the minimum number of Hamiltonian cycles in a 2-connected tournament of order n increase exponentially with n. Furthermore, the number of Hamiltonian cycles in a tournament increases at leas

On the chromatic number of cube-like gra

On the chromatic number of cube-like graphs

✍ Charles Payan 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 343 KB

A cube-like graph is a graph whose vertices are all 2" subsets of a set E of cardinality n, in which two vertices are adjacent if their symmetric difference is a member of a given specified collection of subsets of E. Many authors were interested in the chromatic number of such graphs and thought it

Bounds on the number of complete subgrap

Bounds on the number of complete subgraphs

✍ David C. Fisher; Jennifer Ryan 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 385 KB

Fisher, D.C. and J. Ryan, Bounds on the number of complete subgraphs, Discrete Mathematics 103 (1992) 313-320. Let G be a graph with a clique number w. For 1 s s w, let k, be the number of complete j subgraphs on j nodes. We show that k,,, c (j~l)(kj/(~))u""'. This is exact for complete balanced w-