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.
Seznam odborné literatury
[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
Předběžná náplň práce
Charakterizace třídy grafů, ve kterých lze každé perfektní párování rozšířit na Hamiltonovskou kružnici
Předběžná náplň práce v anglickém jazyce
Characterization of the class of graphs where every perfect matching can be extended to Hamiltonian cycle.
