Hamiltonian index is NP-complete

DOI10.1016/J.DAM.2010.08.027zbMATH Open1210.05069OpenAlexW2059973876MaRDI QIDQ629366FDOQ629366

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The Planar Hamiltonian Circuit Problem is NP-Complete
• On Eulerian and Hamiltonian Graphs and Line Graphs
• The edge Hamiltonian path problem is NP-complete
• Hamiltonian iterated line graphs
• The Hamiltonian index of a graph and its branch-bonds
• On Hamiltonian Line-Graphs
• The Hamiltonian index of graphs
• On the 2-factor index of a graph
• 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
• Forbidden subgraphs for supereulerian and Hamiltonian graphs
• On traceable iterated line graph and Hamiltonian path index
• Parameterized edge Hamiltonicity
• Minimum number of components of 2-factors in iterated line graphs
• Gray codes with bounded weights
• Problems remaining NP-complette for sparse or dense graphs
• Hamiltonian index of directed multigraph
• 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
• Title not available (Why is that?)
• Even factors with a bounded number of components in iterated line graphs
• Title not available (Why is that?)
• 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

   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 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• NP-completeness of the Hamming salesman problem 👍 👎

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)