Matchings of quadratic size extend to long cycles in hypercubes

Kód výsledku v IS VaVaI

RIV/00216208:11320/16:10325181 - isvavai.cz

Výsledek na webu

https://dmtcs.episciences.org/2012/pdf

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Matchings of quadratic size extend to long cycles in hypercubes

Popis výsledku v původním jazyce

Ruskey and Savage in 1993 asked whether every matching in a hypercube can be extended to a Hamiltonian cycle. A positive answer is known for perfect matchings, but the general case has been resolved only for matchings of linear size. In this paper we show that there is a quadratic function q(n) such that every matching in the n-dimensional hypercube of size at most q(n) may be extended to a cycle which covers at least 3/4 of the vertices.

Název v anglickém jazyce

Matchings of quadratic size extend to long cycles in hypercubes

Popis výsledku anglicky

Ruskey and Savage in 1993 asked whether every matching in a hypercube can be extended to a Hamiltonian cycle. A positive answer is known for perfect matchings, but the general case has been resolved only for matchings of linear size. In this paper we show that there is a quadratic function q(n) such that every matching in the n-dimensional hypercube of size at most q(n) may be extended to a cycle which covers at least 3/4 of the vertices.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

GA14-10799S: Hyperkrychlové, grafové a hypergrafové struktury

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

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ů

Název periodika

Discrete Mathematics and Theoretical Computer Science

ISSN

1462-7264

e-ISSN

—

Svazek periodika

18

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

8

Strana od-do

1-8

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—