𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graphs with exactly one hamiltonian circuit

✍ Scribed by John Sheehan

Publisher
John Wiley and Sons
Year
1977
Tongue
English
Weight
221 KB
Volume
1
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ 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

On graphs with hamiltonian squares
On graphs with hamiltonian squares
✍ P. Underground πŸ“‚ Article πŸ“… 1978 πŸ› Elsevier Science 🌐 English βš– 111 KB

The problem of recognizing hamiltonian graphs is not Jriously difficult; in fack, Karp, Lawler and Tarjan [3] proved that it is NP-colnplete. Combined with Cook's theorem [l], this result suggests that the existence'= of a good characterization of nonhamiltcnian graphs is extremely unlikely. On the

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

One sufficient condition for hamiltonian
One sufficient condition for hamiltonian graphs
✍ Guantao Chen πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 220 KB πŸ‘ 1 views

## Abstract Let __G__ be a 2‐connected graph of order __n.__ We show that if for each pair of nonadjacent vertices __x__,__y__ ∈ __V(G)__, then __G__ is Hamiltonian.