Hamiltonovskost hyperkrychlí bez k-hadů a k-cívek

Pěgřímek, David

A snake (coil) is an induced path (cycle) in a hypercube. They are well known from the snake-in-the-box (coil-in-the-box) problem which asks for the longest snake (coil) in a hypercube. They have been generalized to k-snakes (k-coils) which preserve distances between their every two vertices at distance at most k − 1 in hypercube. We study them as a variant of Locke's hypothesis. It states that a balanced set F ⊆ V (Qn) of cardinality 2m can be avoided by a Hamiltonian cycle if n ≥ m + 2 and m ≥ 1. We show that if S is a k-snake (k-coil) in Qn for n ≥ k ≥ 6 (n ≥ k ≥ 7), then Qn − V (S) is Hamiltonian laceable. For a fixed k the number of vertices of a k-coil may even be exponential with n. We introduce a dragon, which is an induced tree in a hypercube, and its generalization a k-dragon which preserves distances between its every two vertices at distance at most k−1 in hypercube. By proving a specific lemma from my Bachelor thesis that was previously verified by a computer, we finish the proof of the theorem regarding Hamiltonian laceability of hypercubes without n-dragons.

guest :: login Digital Repository
		Search		Submit		Help		About