Hamiltonian index is NP-complete

DOI10.1016/J.DAM.2010.08.027MaRDI QIDQ629366zbMATH OpenOpenAlexFDO

Authors Zdeněk Ryjáček, Gerhard J. Woeginger, Liming Xiong

Publication date 9 March 2011

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.08.027

zbMATH Keywords

complexityline graphNP-complete problemHamiltonian indexbranch-bond

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38)

Recommendations

• On Computing the Hamiltonian Index of Graphs
• On computing the Hamiltonian index of graphs
• The Hamiltonian index of graphs
• On the hamiltonian index of a graph
• On the Hamiltonian index
• The NPO-completeness of the longest Hamiltonian cycle problem
• scientific article; zbMATH DE number 4045182
• scientific article; zbMATH DE number 3851144
• scientific article; zbMATH DE number 617594
• NP-completeness of the Hamming salesman problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Hamiltonian iterated line graphs
• On Eulerian and Hamiltonian Graphs and Line Graphs
• On Hamiltonian Line-Graphs
• On the 2-factor index of a graph
• On the supereulerian index of a graph
• The Hamiltonian index of a graph and its branch-bonds
• The Hamiltonian index of graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The edge Hamiltonian path problem is NP-complete
• The existence of even factors in iterated line graphs

Cited in

(23)

• On the dominating (induced) cycles of iterated line graphs
• On computing the Hamiltonian index of graphs
• Edge degree conditions for Hamiltonian 2-iterated line graphs
• On s-fully cycle extendable line graphs
• Forbidden subgraphs for supereulerian and Hamiltonian graphs
• On traceable iterated line graph and Hamiltonian path index
• Minimum number of components of 2-factors in iterated line graphs
• Gray codes with bounded weights
• Hamiltonian index of directed multigraph
• Problems remaining NP-complette for sparse or dense graphs
• Characterizing forbidden pairs for the existence of even factors
• Polynomially determining spanning connectivity of locally connected line graphs
• On Computing the Hamiltonian Index of Graphs
• Being Hamiltonian is not a Tutte invariant
• NP-completeness of the Hamming salesman problem
• Degree sum conditions for Hamiltonian index
• Forbidden subgraphs on Hamiltonian index
• Characterization of forbidden subgraphs for the existence of even factors in a graph
• Even factors with a bounded number of components in iterated line graphs
• On the extended Clark-Wormold Hamiltonian-like index problem
• Branch-bonds, two-factors in iterated line graphs and circuits in weighted graphs
• Panconnected index of graphs
• Asymptotically sharpening the s-Hamiltonian index bound

This page was built for publication: Hamiltonian index is NP-complete

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