Towards a problem of Ruskey and Savage on matching extendability
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10364722" target="_blank" >RIV/00216208:11320/17:10364722 - isvavai.cz</a>
Výsledek na webu
<a href="http://www.sciencedirect.com/science/article/pii/S1571065317301567" target="_blank" >http://www.sciencedirect.com/science/article/pii/S1571065317301567</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.endm.2017.06.071" target="_blank" >10.1016/j.endm.2017.06.071</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Towards a problem of Ruskey and Savage on matching extendability
Popis výsledku v původním jazyce
Does every matching in the n-dimensional hypercube extend to a Hamiltonian cycle? This question was raised by Ruskey and Savage in 1993 and even though a positive answer in known in some special cases, the problem still remains open in general. In this paper we present recent results on extendability of matchings in hypercubes to Hamiltonian cycles and paths as well as on the computational complexity of these problems, motivated by the Ruskey-Savage question. Moreover, we verify the conjecture of Vandenbussche and West saying that every matching in the hypercube of dimension at least two extends to a 2-factor.
Název v anglickém jazyce
Towards a problem of Ruskey and Savage on matching extendability
Popis výsledku anglicky
Does every matching in the n-dimensional hypercube extend to a Hamiltonian cycle? This question was raised by Ruskey and Savage in 1993 and even though a positive answer in known in some special cases, the problem still remains open in general. In this paper we present recent results on extendability of matchings in hypercubes to Hamiltonian cycles and paths as well as on the computational complexity of these problems, motivated by the Ruskey-Savage question. Moreover, we verify the conjecture of Vandenbussche and West saying that every matching in the hypercube of dimension at least two extends to a 2-factor.
Klasifikace
Druh
J<sub>SC</sub> - Článek v periodiku v databázi SCOPUS
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA14-10799S" target="_blank" >GA14-10799S: Hyperkrychlové, grafové a hypergrafové struktury</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2017
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Electronic Notes in Discrete Mathematics
ISSN
1571-0653
e-ISSN
—
Svazek periodika
2017
Číslo periodika v rámci svazku
61
Stát vydavatele periodika
NL - Nizozemsko
Počet stran výsledku
7
Strana od-do
437-443
Kód UT WoS článku
—
EID výsledku v databázi Scopus
2-s2.0-85026759380