𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A lower bound on the Hamiltonian path completion number of a line graph

✍ Scribed by Detti, Paolo; Meloni, Carlo; Pranzo, Marco

Book ID
123377141
Publisher
Elsevier Science
Year
2013
Tongue
English
Weight
599 KB
Volume
220
Category
Article
ISSN
0096-3003

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

On the hamiltonian path graph of a graph
On the hamiltonian path graph of a graph
✍ George R. T. Hendry πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 491 KB πŸ‘ 1 views

The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and u are adjacent if and only if F contains a hamiltonian u -u path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian grap

A lower bound on the independence number
A lower bound on the independence number of a graph
✍ Jochen Harant πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 210 KB

A new lower bound on the independence number of a graph is established and an accompanying efficient algorithm constructing an independent vertex set the cardinality of which is at least this lower bound is given. (~