 | On Thursday, September 4, 2025, from 8:00 PM to 10:00 PM, there will be an outage of WhoIs system. This will limit work in IS studium. For example, you will not be able to submit thesis. Subscription to courses should remain unaffected by the outage. We apologize for any inconveniece and we thank you for understanding. |
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. |
| Guidelines |
| 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. |
| References |
| 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. |