Graph Algorithms for Constructing and Enumerating Cycles and Related Structures

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
School of Electrical Engineering | Doctoral thesis (article-based) | Defence date: 2015-10-02
Checking the digitized thesis and permission for publishing
Instructions for the author
Date
2015
Major/Subject
Mcode
Degree programme
Language
en
Pages
56 + app. 87
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 127/2015
Abstract
A graph is a mathematical object that consists of a set of vertices and a set of edges between some pairs of vertices. Despite the simple definition graphs are very versatile; in addition to being of theoretical interest, they have a large number of applications in several areas of science and technology, including physics, biology, and telecommunications. This thesis focuses on algorithms for constructing and enumerating cycles and some related structures in graphs. Cycles are central objects in graph theory, and they appear in a multitude of applications. For many applications it is essential to construct or enumerate cycles with certain properties in a graph. The algorithms created here are based on canonical augmentation, dynamic programming, and recursive search, and they make heavy use of the symmetries of the graphs. The contribution of this thesis is as follows. We present a new method for enumerating Hamiltonian cycles in general graphs, planar graphs and grid graphs. We enumerate perfect matchings in the n-cube for n ≤ 7. We discover new chordless cycles and chordless paths in the 8-cube and establish that they are of maximal length. We discover new small planar hypohamiltonian graphs of order 40; the smallest previously known examples were of order 42. Furthermore, enumeration of certain cycles in the grid graph is used for studying Toeplitz' conjecture.

Graafi on matemaattinen objekti joka koostuu solmuista ja solmujen välillä olevista kaarista. Yksinkertaisesta määritelmästä huolimatta graafit ovat hyvin monipuolisia; sen lisäksi että graafit ovat kiinnostavia teoreettisesta näkökulmasta, niillä on suuri määrä sovelluksia monella tieteen ja teknologian alalla, kuten fysiikassa, biologiassa ja tietoliikennetekniikassa. Tässä väitöskirjassa tutkitaan algoritmeja, joita voidaan käyttää syklien ja eräiden sykleihin liittyvien rakenteiden konstruoimiseen ja lukumäärän laskemiseen graafeissa. Syklit ovat keskeisiä objekteja graafiteoriassa, ja niitä esiintyy lukuisissa sovelluksissa. Monien sovellusten kannalta on tärkeää konstruoida tai laskea sellaisia graafeissa olevia syklejä joilla on joitain tiettyjä ominaisuuksia. Väitöskirjatyössä luodut algoritmit perustuvat kanoniseen augmentointiin, dynaamiseen ohjelmointiin ja rekursiiviseen hakuun, ja ne käyttävät hyväkseen tutkittavien graafien symmetriaa. Väitöskirjan kontribuutio on seuraavanlainen. Esitämme uuden menetelmän Hamiltonin syklien lukumäärän laskemiseen yleisissä graafeissa, tasograafeissa ja hilagraafeissa. Laskemme täydellisten paritusten lukumäärän n-kuutiossa arvoon n = 7 asti. Löydämme uusia indusoituja syklejä ja polkuja 8-kuutiossa ja todistamme että näiden pituus on suurin mahdollinen. Löydämme uusia pieniä hypohamiltonisia tasograafeja, joissa on vain 40 solmua; pienin aiemmin tunnettu esimerkki sisälsi 42 solmua. Lopuksi tutkimme Toeplitzin konjektuuria laskemalla tietynlaisten syklien lukumäärän hilagraafissa.
Description
Supervising professor
Östergård, Patric, Prof., Aalto University, Department of Communications and Networking, Finland
Thesis advisor
Östergård, Patric, Prof., Aalto University, Department of Communications and Networking, Finland
Keywords
graphs, algorithms, construction, enumeration, cycles, graafit, algoritmit, syklit, konstruointi, enumerointi
Other note
Parts
  • [Publication 1]: M. Jooyandeh, B. D. McKay, P. R. J. Östergård, V. H. Pettersson, C. T. Zamfirescu. Planar Hypohamiltonian Graphs on 40 Vertices. Submitted to Journal of Graph Theory, 2014.
  • [Publication 2]: P. R. J. Östergård, V. H. Pettersson. Enumerating Perfect Matchings in n-Cubes. Order, 30, 821–835, 2013. DOI 10.1007/s11083-012-9279-8
  • [Publication 3]: P. R. J. Östergård, V. H. Pettersson. Exhaustive Search for Snake-in-the-Box Codes. Accepted for publication in Graphs and Combinatorics, 2014. DOI 10.1007/s00373-014-1423-3
  • [Publication 4]: P. R. J. Östergård, V. H. Pettersson. On the Maximum Length of Coil-in-the-Box Codes in Dimension 8. Discrete Applied Mathematics, 179, 193–200, 2014. DOI 10.1016/j.dam.2014.07.010
  • [Publication 5]: V. H. Pettersson. Enumerating Hamiltonian Cycles. The Electronic Journal of Combinatorics, 21(4), #P4.7, 2014.
  • [Publication 6]: V. H. Pettersson, H. A. Tverberg, P. R. J. Östergård. A note on Toeplitz’ conjecture. Discrete and Computational Geometry, 51, 722–728, 2014. DOI 10.1007/s00454-014-9578-5
Citation