Cesty, kružnice a párování v hyperkrychli
Pokud vás zaujmou některé z následujících otázek, tak mi napište a domluvíme podrobnosti.- Je možné každé párování v hyperkrychli rozšířit Hamiltonovskou kružnici?
- Víme, že každé perfektní párování v hyperkrychli je možné rozšířit na Hamiltonovskou kružnici. Existuje i jiná třída grafů, ve které lze každé perfektní párovaní rozšířit na Hamiltonovskou kružnici?
- Fu [8] dokázal, že pro každou množinu chybných vrcholů F v Q_n velikosti nejvýše n - 2 existuje cesta délky alespoň 2^n - 2 |F| - 2 mezi předepsanými dvěma vrcholy. Dále víme, že počet chyb je možné zvýšit na 2n - 4, pokud oba předepsané vrcholy u a v mají alespoň jednoho souseda různého od F, u, v. Snadno nahlédnete, že počet chyb je v těchto větách maximální. Jaký je maximální počet chyb, pokud zvýšíme počet zdravých sousedů koncových vrcholů na dva či více?
- Další zajímavé otázky můžete najít v [9].
Pojmy
- n-dimenzionální hyperkrychle
- je graf, jehož vrcholy jsou posloupnosti čísel 0 a 1 délky n a hranou jsou spojeny právě ty vrcholy, jejichž posloupnosti se liší právě v jedné pozici. Značí se Q_n. Například čtverec je 2-dimenzionální hyperkrychle a klasická krychle je 3-dimenzionální hyperkrychle. Parita vrcholu je parita (sudost či lichost) počtu jedniček v posloupnosti. Hyperkrychle je bipartitní graf, protože hranou jsou spojeny jen vrcholy různé parity.
- Párování
- je množina hran daného grafu taková, že každý vrchol je incidentní s nejvýše jednou hranou párování. Párování je perfektní, pokud každý vrchol je incidentní právě s jednou hranou párování.
- Hamiltonovská kružnice
- je kružnice procházející všemi vrcholy daného grafu.
Reference
[1] L. Gros: Théorie du Baguenodier, Aimé Vingtrinier, Lyon, 1872.[2] N. Castaneda, V. Gochev, I. Gotchev and F. Latour: On path coverings of hypercubes with one faulty vertex. Submitted.
[3] M. Lewinter and W. Widulski: Hyper-Hamilton laceable and caterpillar-spannable product graphs, Comput. Math. Appl. 34 (1997), 99-104.
[4] J. Fink. Perfect matchings extend to Hamilton cycles in hypercubes. J. Comb. Theory, Ser. B, 97(6):1074-1076, 2007.
[5] F. Ruskey and C.D. Savage. Hamilton cycles that extend transposition matchings in cayley graphs of sn. SIAM Journal on Discrete Mathematics, 6(1):152-166, 1993.
[6] J. Fink and P. Gregor. Long paths and cycles in hypercubes with faulty vertices. Information Sciences, 179:3634-3644, 2009.
[7] J. Fink and P Gregor. Long cycles in hypercubes with optimal number of faulty vertices. Manuscript, 2009.
[8] J.-S. Fu. Longest fault-free paths in hypercubes with vertex faults. Information Sciences, 176(7):759-771, 2006.
[9] T. Mütze. Combinatorial Gray codes-an updated survey. arXiv preprint arXiv:2202.01280.Mütze, Torsten. "Combinatorial Gray codes-an updated survey." arXiv preprint arXiv:2202.01280, 2022.