EUVIMEDEUVIMED entdecken
Crossref

Extending Matchings to Gray Codes in Hypercubes with Prescribed Endpoints

Abid Ali, Gohar Ali, Weihua Yang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →