Alja Šubic (2019) *Hypohamiltonian graphs*. MSc thesis.

| PDF Download (2005Kb) |

## Abstract

Hamiltonian graphs are a very interesting research subject in the field of graph theory, which is the subject of this master’s thesis. These are the graphs that contain a Hamiltonian cycle, that is a cycle which contains all the vertices of the given graph, each exactly once. In this master’s thesis we deal with a special type of non-hamiltonian graphs, which are almost Hamiltonian. In particular, we study the so-called hypohamiltonian graphs, which don’t contain a Hamiltonian cycle but after removing any vertex from the original graph we get an induced subgraph which is Hamiltonian. The main purpose of the master’s thesis is a detailed presentation of the concept of hypohamiltonicity and the presentation of many kinds of different examples of such graphs. A special emphasis is put on the problem of determining all natural numbers n for which there is at least one hypohamiltonian graph of order n. At the end of this master's thesis we devote some attention to cubic hypohamiltonian graphs. These are particularly interesting for this study as the degrees of vertices of such graphs are the least possible when considering hypohamiltonian graphs.

Item Type: | Thesis (MSc thesis) | ||||||
---|---|---|---|---|---|---|---|

Keywords: | Hamiltonian cycle, hypohamiltonian graph, infinite family, flip-flop | ||||||

Number of Pages: | 77 | ||||||

Language of Content: | Slovenian | ||||||

Mentor / Comentors: |
| ||||||

Link to COBISS: | https://plus.si.cobiss.net/opac7/bib/peflj/12378185 | ||||||

Institution: | University of Ljubljana | ||||||

Department: | Faculty of Education | ||||||

Item ID: | 5683 | ||||||

Date Deposited: | 24 Apr 2019 08:32 | ||||||

Last Modified: | 24 Apr 2019 08:32 | ||||||

URI: | http://pefprints.pef.uni-lj.si/id/eprint/5683 |

### Actions (login required)

View Item |