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. |