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

DOI10.1016/J.AMC.2013.06.020MaRDI QIDQ902504zbMATH OpenOpenAlexFDO

Authors Paolo Detti, C. Meloni, Marco Pranzo

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)

Recommendations

• A linear algorithm for the Hamiltonian completion number of the line graph of a tree
• scientific article; zbMATH DE number 1094037
• scientific article; zbMATH DE number 1439412
• Local search algorithms for finding the Hamiltonian completion number of line graphs
• scientific article; zbMATH DE number 1185618
• A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.
• A lower bound for the shortest Hamiltonean path in directed graphs
• A result on Hamiltonian line graphs involving restrictions on induced subgraphs
• scientific article; zbMATH DE number 3946175
• On hamiltonian line graphs of hypergraphs

Cites work

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

Cited in

(6)

• Local search algorithms for finding the Hamiltonian completion number of line graphs
• A bi-objective coordination setup problem in a two-stage production system
• A linear algorithm for the Hamiltonian completion number of the line graph of a tree
• A lower bound for the optimal crossing-free Hamiltonian cycle problem
• Evolutionary operators for the Hamiltonian completion problem
• A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q902504)