Thesis (Selection of subject)Thesis (Selection of subject)(version: 368)
Thesis details
   Login via CAS
Hamiltonicity of hypercubes without k-snakes and k-coils
Thesis title in Czech: Hamiltonovskost hyperkrychlí bez k-hadů a k-cívek
Thesis title in English: Hamiltonicity of hypercubes without k-snakes and k-coils
Key words: hyperkrychle, vadný vrchol, Hamiltonovskost, k-had, k-cívka
English key words: hypercube, faulty vertex, Hamiltonicity, k-snake, k-coil
Academic year of topic announcement: 2014/2015
Thesis type: diploma thesis
Thesis language: angličtina
Department: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Supervisor: doc. Mgr. Petr Gregor, Ph.D.
Author: hidden - assigned and confirmed by the Study Dept.
Date of registration: 10.04.2015
Date of assignment: 10.04.2015
Confirmed by Study dept. on: 07.07.2015
Date and time of defence: 20.06.2016 09:00
Date of electronic submission:11.05.2016
Date of submission of printed version:11.05.2016
Date of proceeded defence: 20.06.2016
Opponents: RNDr. Jiří Fink, Ph.D.
A snake (coil) is an induced path (cycle) in a hypercube. It has received attention in a well known problem called snake-in-the-box (coil-in-the-box) which asks for a longest snake (coil) in a hypercube. Both snakes and coils have been generalized to k-snakes and k-coils with parameter k which is referred to as a spread. The goal of this thesis is to familiarize with k-snakes and k-coils and to explore whether they could be avoided by a Hamiltonian path or a Hamiltonian cycle for some k. The thesis will also introduce and study a dragon which is an induced tree in a hypercube and its generalization to a k-dragon.
S. Hood, D. Recoskie, J. Sawada, D. Wong, Snakes, coils, and single-track circuit codes with spread k, Journal of Combinatorial Optimization (2013), 1-21.

R. Singleton, Generalized Snake-in-the-Box Codes, Electronic Computers, IEEE Transactions on Electronic Computers (1966), 596-602.

Chao-Ming Sun and Yue-Dar Jou, Hamiltonian laceability of hypercubes with some faulty elements, Proceedings of the 2009 IEEE International Conference on Networking, Sensing and Control, ICNSC (2009), 626-630.

F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, California (1992).

P. Gregor and R. Škrekovski, Long cycles in hypercubes with distant faulty vertices, Discrete Mathematics & Theoretical Computer Science 11 (2009), 185-198.

T. Dvořák and P. Gregor. Hamiltonian fault-tolerance of hypercubes, Electronic Notes in Discrete Mathematics 29 (2007), 471-477.
Charles University | Information system of Charles University |