𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Paolo Detti; Carlo Meloni

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
464 KB
Volume
136
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

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 is a cactus is proposed.

πŸ“œ SIMILAR VOLUMES

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