magistrsko delo
Dejan Krejić (Author), Primož Šparl (Mentor)

Abstract

Tema magistrskega dela sodi na področje algebraične teorije grafov, kjer se med drugim ukvarjamo s proučevanjem simetrij grafov in raziskovanjem možnosti njihove uporabe pri reševanju problemov, ki so povezani z grafi. Prav simetrija (ali avtomorfizem) grafa je pojem, preko katerega so definirane nekatere grafovske lastnosti, kot je na primer vozliščna tranzitivnost. V takšnih grafih zahtevamo, da za poljuben par vozlišč obstaja avtomorfizem, ki prvo vozlišče preslika v drugo. Dotična družina grafov je zanimiva tudi zato, ker zanjo ostaja odprtih več vprašanj, ki vzbujajo zanimanje številnih raziskovalcev. Eno izmed njih je zagotovo vprašanje o obstoju hamiltonskih ciklov in poti v vozliščno tranzitivnih grafih, ki ima že precej dolgo zgodovino in predstavlja glavno temo tega magistrskega dela. Cikel danega grafa Γ imenujemo hamiltonski cikel, če vsebuje vsa vozlišča grafa Γ (hamiltonsko pot definiramo podobno). Še vedno ne poznamo niti enega primera končnega povezanega vozliščno tranzitivnega grafa brez hamiltonske poti, poznamo pa natanko pet tovrstnih grafov, ki nimajo hamiltonskega cikla (Petersenov graf, Coxeterjev graf, njuna prisekana grafa in pot na dveh vozliščih). Osrednji namen magistrskega dela je prikazati širši vpogled v problem obstoja hamiltonskih ciklov in poti v vozliščno tranzitivnih grafih. Osredotočamo se predvsem na obravnavo različnih pristopov k reševanju danega problema, predstavimo pa tudi zanimivo lastno idejo, ki bi lahko imela uporabno vrednost na tem področju. V prvem delu magistrskega dela podrobno predstavimo družino vozliščno tranzitivnih grafov. Sledi poglavje, v katerem raziščemo možnosti uporabe koncepta blokov neprimitivnosti pri problemu obstoja hamiltonskih ciklov in poti v vozliščno tranzitivnih grafih. Tukaj naredimo analizo obstoja sistemov blokov neprimitivnosti v majhnih kubičnih vozliščno tranzitivnih grafih, proučimo strukturne lastnosti podgrafov, ki so inducirani na posamezne bloke neprimitivnosti in razmislimo o načinih dviga hamiltonskih ciklov in poti iz pripadajočih kvocientnih grafov glede na ustrezen sistem blokov neprimitivnosti. V nadaljevanju magistrskega dela se ukvarjamo z vlogo semiregularnih avtomorfizmov pri obravnavi problema obstoja hamiltonskih ciklov in poti v grafih. Zanima nas, kako je z obstojem semiregularnih avtomorfizmov v vozliščno tranzitivnih grafih, kakšne so njihove lastnosti, največ pozornosti pa posvetimo obravnavi dviga hamiltonskih ciklov iz kvocientnih grafov glede na množico orbit semiregularne grupe avtomorfizmov. Zadnji del magistrskega dela namenimo proučevanju pomembnega Babajevega rezultata o dolžini najdaljših ciklov v vozliščno tranzitivnih grafih. Predstavimo tudi zanimivo idejo, ki na področju problema hamiltonskosti vozliščno traznitivnih grafov do sedaj po našem vedenju še ni bila raziskana.

Keywords

hamiltonski cikel;hamiltonska pot;sistem blokov neprimitivnosti, semiregularnost, Babajev izrek;

Data

Language: Slovenian
Year of publishing:
Typology: 2.09 - Master's Thesis
Organization: UL PEF - Faculty of Education
Publisher: [D. Krejić]
UDC: 51(043.2)
COBISS: 12090441 Link will open in a new window
Views: 458
Downloads: 96
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Hamiltonicity of vertex transitive graphs
Secondary abstract: The topic of the master's thesis comes from algebraic graph theory, where, among other things, we study graph symmetries and explore the possibilities to use them for solving problems related to graphs. Symmetry (or graph automorphism) is a concept we use to define some graph properties, for example vertex-transitivity. In such graphs we require that for every pair of vertices there is automorphism, which maps the first vertex into the second one. One of the reasons why this family of graphs is so interesting is because we can find various open questions about these graphs that attracts interest of numerous researchers. One of these questions is definitely the question of the existence of Hamiltonian cycles and paths in vertex-transitive graphs which has a long history and represents the main topic of this master's thesis. The cycle of a given graph Γ is called a Hamiltonian cycle if it includes all vertices of the graph Γ (the Hamiltonian path is defined analogously). We still do not know of a single example of a finite connected vertex-transitive graph without a Hamiltonian path and we know of exactly five such graphs that do not have a Hamiltonian cycle (the Petersen graph, the Coxeter graph, their truncated graphs, and the path on two vertices). The main purpose of this master’s thesis is to give a broader insight into the problem of existence of Hamiltonian cycles and paths in vertex-transitive graphs. We primarily focus on different approaches to solving the given problem, and we also present an interesting idea of our own, which could prove useful in this field. In the first part of the master’s thesis we present the family of vertex-transitive graphs in more detail. We then explore the possibilities of applying the concept of blocks of imprimitivity to the problem of existence of Hamiltonian cycles and paths in vertex-transitive graphs. Here we make an analysis of the existence of systems of blocks of imprimitivity for small cubic vertex-transitive graphs and then examine structural properties of subgraphs, induced on individual blocks of imprimitivity. We also consider the possibilities of lifting Hamiltonian cycles and paths from the quotient graphs corresponding to a suitable system of blocks of imprimitivity. In the next part of the master's thesis we investigate the role of semiregular automorphisms in the problem of existence of Hamiltonian cycles and paths in graphs. We are interested in the existence of semiregular automorphisms in vertex-transitive graphs and their properties, but we mainly focus on lifting Hamiltonian cycles from quotient graphs with respect to the set of orbits of the semiregular automorphism group. The last part of the master's thesis is dedicated to the study of Lazslo Babai's important result about the length of the longest cycles in vertex-transitive graphs. We also present an interesting idea, which has not yet been explored in the context of the hamiltonicity problem for vertex-transitive graphs.
Secondary keywords: mathematics;matematika;
File type: application/pdf
Type (COBISS): Master's thesis/paper
Thesis comment: Univ. v Ljubljani, Pedagoška fak., Poučevanje
Pages: 77 str.
ID: 10954344