Home > Search Results: keywords:"Hamiltonovskost"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 1 records found  Search took 0.01 seconds. 
Hamiltonicity of hypercubes without k-snakes and k-coils
 Pěgřímek, David ; Gregor, Petr (advisor) ; Fink, Jiří (referee)
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.
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English