### Abstract

In this paper we show that the problem to decide whether the hamiltonian index of a given graph is less than or equal to a given constant is NP-complete (although this was conjectured to be polynomial). Consequently, the corresponding problem to determine the hamiltonian index of a given graph is NP-hard. Finally, we show that some known upper and lower bounds on the hamiltonian index can be computed in polynomial time.

Original language | English |
---|---|

Pages (from-to) | 246-250 |

Journal | Discrete Applied Mathematics |

Volume | 159 |

Issue number | 4 |

DOIs | |

Publication status | Published - 2011 |

## Fingerprint Dive into the research topics of 'Hamiltonian index is NP-complete'. Together they form a unique fingerprint.

## Cite this

Ryjacek, Z., Woeginger, G. J., & Xiong, L. (2011). Hamiltonian index is NP-complete.

*Discrete Applied Mathematics*,*159*(4), 246-250. https://doi.org/10.1016/j.dam.2010.08.027