Extending Matchings to Gray Codes in Hypercubes with Prescribed Endpoints
Parallel Processing Letters · 2026-06 · 36 (01n02)
DOI: 10.1142/s0129626426500040 ↗Kurz gefasst
Fachartikel in der Zeitschrift Parallel Processing Letters, online erschienen am 11.03.2026. Verfasst von Abid Ali und 2 weiteren Autor:innen. Die Arbeit nennt 39 Literaturangaben.
Abstract (Originalsprache)
A cyclic Gray code is an ordered sequence that contains all binary strings of a given length in which each consecutive string differs from the previous one in exactly one coordinate. Such a sequence directly represents a Hamiltonian cycle and path in the hypercube. Ruskey and Savage asked whether every matching in the hypercube extends to a Hamiltonian cycle, and Fink proved that every perfect matching in [Formula: see text] extends to a Hamiltonian cycle. In this study, we address a problem related to Hamiltonian paths. We prove that every matching at most in five directions where every [Formula: see text]-cycle contains at least one unsaturated vertex, can be extended to a Hamiltonian path joining two vertices in distinct partite sets of [Formula: see text], for [Formula: see text]. The only forbidden configurations are the so-called half-layers, which form certain natural obstacles.
Zitieren
APA
Ali, A., Ali, G., & Yang, W. (2026). Extending Matchings to Gray Codes in Hypercubes with Prescribed Endpoints. Parallel Processing Letters, 36(01n02). https://doi.org/10.1142/s0129626426500040
Vancouver
Ali A, Ali G, Yang W. Extending Matchings to Gray Codes in Hypercubes with Prescribed Endpoints. Parallel Processing Letters. 2026;36(01n02). doi:10.1142/s0129626426500040
BibTeX
@article{Ali2026,
author = {Ali, Abid and Ali, Gohar and Yang, Weihua},
title = {Extending Matchings to Gray Codes in Hypercubes with Prescribed Endpoints},
journal = {Parallel Processing Letters},
year = {2026},
volume = {36},
number = {01n02},
doi = {10.1142/s0129626426500040}
}
EUVIMED