Hipohamiltonovi grafi

Šubic, Alja (author), Šparl, Primož (mentor)

V teoriji grafov, področju na katero sodi to magistrsko delo, so zelo zanimiv predmet raziskovanja Hamiltonovi grafi. To so grafi, ki premorejo Hamiltonov cikel oziroma cikel, ki vsebuje vsa vozlišča danega grafa, vsako natanko enkrat. V magistrskem delu se ukvarjamo s posebno vrsto nehamiltonovih grafov, ki pa so skoraj Hamiltonovi. Gre za tako imenovane hipohamiltonove grafe, ki sicer ne premorejo Hamiltonovega cikla, ob odstranitvi poljubnega vozlišča iz prvotnega grafa pa dobljeni inducirani podgraf postane Hamiltonov. Glavni namen magistrskega dela je podrobna predstavitev koncepta hipohamiltonskosti, predstavitev več vrst različnih primerov takšnih grafov, predvsem pa se posvetimo vprašanju, za katera naravna števila n obstaja vsaj en hipohamiltonov graf reda n. Ob koncu magistrskega dela nekaj pozornosti namenimo še kubičnim hipohamiltonovim grafom. Le-ti so za študij še posebej zanimivi, saj gre za grafe, katerih stopnje vozlišč so, ko govorimo o hipohamiltonovih grafih, najmanjše možne. Magistrskemu delu je dodana priloga, kjer sta podana programa za preverjanje hamiltonskosti in hipohamiltonskosti grafov nižjih redov, napisana v programskem jeziku Python. Z njima podkrepimo nekatere rezultate magistrskega dela, saj lahko na ta način preverimo, ali so grafi, ki so podani kot konkretni primeri majhnih hipohamiltonovih grafov, zares hipohamiltonovi.

• Language: Slovenian
• Keywords: Hamiltonov cikel
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: PEF - Faculty of Education
• Year: 2019
• PID: 20.500.12556/RUL-107533
• COBISS.SI-ID: 12378185
• Publication date in RUL: 16.05.2019

Secondary language

• Language: English
• Title: Hypohamiltonian graphs

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.

• Keywords: Hamiltonian cycle