## Abstract

The snake-in-the-box problem is concerned with finding a longest induced path in a hypercube $$Q_n$$Qn. Similarly, the coil-in-the-box problem is concerned with finding a longest induced cycle in $$Q_n$$Qn. We consider a generalization of these problems that considers paths and cycles where each pair of vertices at distance at least $$k$$k in the path or cycle are also at distance at least $$k$$k in $$Q_n$$Qn. We call these paths $$k$$k-snakes and the cycles $$k$$k-coils. The $$k$$k-coils have also been called circuit codes. By optimizing an exhaustive search algorithm, we find 13 new longest $$k$$k-coils, 21 new longest $$k$$k-snakes and verify that some of them are optimal. By optimizing an algorithm by Paterson and Tuliani to find single-track circuit codes, we additionally find another 8 new longest $$k$$k-coils. Using these $$k$$k-coils with some basic backtracking, we find 18 new longest $$k$$k-snakes.

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

Pages (from-to) | 42-62 |

Number of pages | 21 |

Journal | Journal of Combinatorial Optimization |

Volume | 30 |

Issue number | 1 |

DOIs | |

Publication status | Published - 28 Jul 2015 |

Externally published | Yes |

## Keywords

- Circuit code
- Coil
- Longest path
- Single-track
- Snake
- Snake-in-the-box