𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A linear algorithm for the Hamiltonian completion number of the line graph of a cactus

✍ Scribed by C. Meloni

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
12 KB
Volume
8
Category
Article
ISSN
1571-0653

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A linear algorithm for the Hamiltonian c
A linear algorithm for the Hamiltonian completion number of the line graph of a cactus
✍ Paolo Detti; Carlo Meloni πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 464 KB

Given a graph G = (V; E); HCN (L(G)) is the minimum number of edges to be added to its line graph L(G) to make L(G) Hamiltonian. This problem is known to be NP-hard for general graphs, whereas a O(|V |) algorithm exists when G is a tree. In this paper a linear algorithm for ΓΏnding HCN (L(G)) when G

A 1-factorization of the line graphs of
A 1-factorization of the line graphs of complete graphs
✍ Brian Alspach πŸ“‚ Article πŸ“… 1982 πŸ› John Wiley and Sons 🌐 English βš– 254 KB πŸ‘ 1 views

## Abstract A 1‐factorization is constructed for the line graph of the complete graph __K~n~__ when __n__ is congruent to 0 or 1 modulo 4.

On the number of hamiltonian cycles in a
On the number of hamiltonian cycles in a maximal planar graph
✍ S. L. Hakimi; E. F. Schmeichel; C. Thomassen πŸ“‚ Article πŸ“… 1979 πŸ› John Wiley and Sons 🌐 English βš– 243 KB πŸ‘ 2 views

## Abstract We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on __p__ vertices. In particular, we construct a __p__‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every __p__ β‰₯ 12. We also pro