Files

TFG_Drapkin_Junyent_Sara.pdf (801.84 KB)

Document type

Bachelor thesis

Publication date

2025-06-10

Publication license

cc-by-nc-nd (c) Sara Drapkin Junyent, 2025
Please use this identifier to cite or link to this item: https://hdl.handle.net/2445/227314

Extending matchings to Hamilton cycles in Hypercubes

Journal Title

Authors

Director/Tutor

Journal ISSN

Volume Title

Related resource

Abstract

The main goal of this work is to study the problem of extending matchings to Hamilton cycles in hypercubes, a fundamental question in graph theory. We focus on the Ruskey--Savage conjecture, which states that every matching in the hypercube $Q_n$ can be extended to a Hamilton cycle. In particular, we formulate and prove some partial results of this conjecture, such as the validity of the conjecture for perfect matchings, known as Kreweras conjecture, and for small matchings, a result by Dvo\v{r}\'ak and Fink. In conclusion, we overview in depth and evaluate the existing progress on the Ruskey--Savage conjecture.

Description

Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2025, Director: Kolja Knauer

Subject

Teoria de grafs, Teoria de l'aparellament, Sara Drapkin Junyent, Treballs de fi de grau

Subject (English)

Graph theory, Matching theory, Bachelor's theses

Citation

Collections

Treballs Finals de Grau (TFG) - Matemàtiques

Citation

DRAPKIN JUNYENT, Sara. Extending matchings to Hamilton cycles in Hypercubes. [consulted: 6 of June of 2026]. Available at: https://hdl.handle.net/2445/227314

Export metadata

JSON - METS

Share record