Rozšiřování perfektního párování na Hamiltonovskou kružnici

• Thesis title in Czech: Rozšiřování perfektního párování na Hamiltonovskou kružnici
• Thesis title in English: Perfect matching extends to Hamiltonian cycle
• Academic year of topic announcement: 2007/2008
• Thesis type: Bachelor's thesis
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: RNDr. Jiří Fink, Ph.D.

Guidelines

Každou Hamiltonovskou kružnici v grafu na sudém počtu vrcholů lze rozdělit na dvě perfektní párovaní. Přirozenou otázkou je, zda je možné každé perfektní párování rozšířit na Hamiltonovskou kružnici. Tato otázka byla kladně odpovězena pro hyperkrychle [1]. Cílem práce je popsat další třídy grafů, ve kterých lze každé perfektní párování rozšířit na Hamiltonovskou kružnici, nebo vymyslet nutné a postačující podmínky, aby graf do této třídy patřil.

References

[1] Jiří Fink. Perfect matchings extend to Hamilton cycles in hypercubes. J. Comb. Theory, Ser. B, 97(6):1074-1076, 2007. http://kam.mff.cuni.cz/~fink/publications/kreweras1.pdf

Preliminary scope of work

Charakterizace třídy grafů, ve kterých lze každé perfektní párování rozšířit na Hamiltonovskou kružnici

Preliminary scope of work in English

Characterization of the class of graphs where every perfect matching can be extended to Hamiltonian cycle.