𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hamiltonian circuits in random graphs

✍ Scribed by L. Pósa

Publisher
Elsevier Science
Year
1976
Tongue
English
Weight
807 KB
Volume
14
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Hamiltonian circuits in chordal bipartit
Hamiltonian circuits in chordal bipartite graphs
✍ Haiko Müller 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 359 KB

The main result of this paper is the NP-completeness of the HAMILTONIAN CIRCUIT problem for chordal bipartite graphs. This is proved by a sophisticated reduction from SATISFIABILITY. As a corollary, HAMILTONIAN CIRCUIT is NP-complete for strongly chordal split graphs. On both classes the complexity

Graphs with exactly one hamiltonian circ
Graphs with exactly one hamiltonian circuit
✍ John Sheehan 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 221 KB

## Abstract Let __h(n__) be the largest integer such that there exists a graph with __n__ vertices having exactly one Hamiltonian circuit and exactly __h(n__) edges. We prove that __h(n__) = [__n__^2^/4]+1 (__n__ ≧ 4) and discuss some related problems.

Sparse pseudo-random graphs are Hamilton
Sparse pseudo-random graphs are Hamiltonian
✍ Michael Krivelevich; Benny Sudakov 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 133 KB

## Abstract In this article we study Hamilton cycles in sparse pseudo‐random graphs. We prove that if the second largest absolute value λ of an eigenvalue of a __d__‐regular graph __G__ on __n__ vertices satisfies and __n__ is large enough, then __G__ is Hamiltonian. We also show how our main resu

Hamiltonian circuits in N2-locally conne
Hamiltonian circuits in N2-locally connected K1,3-free graphs
✍ ZdeněK Ryjáček 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 407 KB 👁 1 views

## Abstract There are many results concerned with the hamiltonicity of __K__~1,3~‐free graphs. In the paper we show that one of the sufficient conditions for the __K__~1,3~‐free graph to be Hamiltonian can be improved using the concept of second‐type vertex neighborhood. The paper is concluded with

Hamiltonian circuits and paths in subset
Hamiltonian circuits and paths in subset graphs with circular adjacency
✍ T.C. Enns 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 751 KB

Consider the subset graph G(n, k) whose vertex set C(n, k) is the set of all n-tuples of 'O's' and 'l's' with exactly k 'I's'. Let an edge exist between two vertices a and b in G(n,k) if and only if a can be transformed into b by the interchange of two adjacent coordinate values, with the first and