[feed] pefprints@pef.uni-lj.si | [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0 |
  Logo Login | Create Account

Hypohamiltonian graphs

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

Download (2005Kb)


    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:
    Mentor / ComentorsIDFunction
    dr. Primož ŠparlMentor
    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