Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones
<|reference_start|>Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones: We prove that computing a single pair of vertices that are mapped onto each other by an isomorphism $\phi$ between two isomorphic graphs is as hard as computing $\phi$ itself. This result optimally improves upon a result of G\'{a}l et al. We establish a similar, albeit slightly weaker, result about computing complete Hamiltonian cycles of a graph from partial Hamiltonian cycles.<|reference_end|>
@article{grosse2001computing,
    title={Computing Complete Graph Isomorphisms and Hamiltonian Cycles from
  Partial Ones},
    author={Andr'e Grosse, Joerg Rothe, and Gerd Wechsung},
    journal={arXiv preprint arXiv:cs/0106041},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0106041},
    primaryClass={cs.CC}
}