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

DOI10.1016/j.amc.2013.06.020zbMath1329.05251OpenAlexW2013110476MaRDI QIDQ902504

Marco Pranzo, Paolo Detti, Carlo Meloni

Publication date: 18 January 2016

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2013.06.020

zbMATH Keywords

lower boundline graphsdominating trailHamiltonian path completion number

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph operations (line graphs, products, etc.) (05C76)

Related Items (2)

Evolutionary operators for the Hamiltonian completion problem ⋮ A bi-objective coordination setup problem in a two-stage production system

Cites Work

• Unnamed Item
• Unnamed Item
• The total interval number of a tree and the Hamiltonian completion number of its line graph
• The edge Hamiltonian path problem is NP-complete
• Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
• A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.
• Process selection and sequencing in a two-agents production system
• Set-up coordination between two stages of a supply chain
• A linear algorithm for the Hamiltonian completion number of the line graph of a tree
• Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
• Local search algorithms for finding the Hamiltonian completion number of line graphs
• A bi-objective coordination setup problem in a two-stage production system
• Limit distribution for the existence of Hamiltonian cycles in a random graph. (Reprint)
• The approximability of the weighted Hamiltonian path completion problem on a tree
• Hamiltonian completions of sparse random graphs
• A result on Hamiltonian line graphs involving restrictions on induced subgraphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Algorithms for Page Retrieval and Hamiltonian Paths on Forward-Convex Line Graphs
• Halin graphs and the travelling salesman problem
• On Eulerian and Hamiltonian Graphs and Line Graphs
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: A lower bound on the Hamiltonian path completion number of a line graph