Graph Algorithms for Constructing and Enumerating Cycles and Related Structures

Ville Pettersson

    Research output: ThesisDoctoral ThesisCollection of Articles

    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.
    Translated title of the contributionGraafialgoritmeja syklien ja niihin liittyvien rakenteiden konstruointiin ja enumerointiin
    Original languageEnglish
    QualificationDoctor's degree
    Awarding Institution
    • Aalto University
    Supervisors/Advisors
    • Östergård, Patric, Supervising Professor
    • Östergård, Patric, Thesis Advisor
    Publisher
    Print ISBNs978-952-60-6364-5
    Electronic ISBNs978-952-60-6365-2
    Publication statusPublished - 2015
    MoE publication typeG5 Doctoral dissertation (article)

    Keywords

    • graphs
    • algorithms
    • construction
    • enumeration
    • cycles

    Fingerprint

    Dive into the research topics of 'Graph Algorithms for Constructing and Enumerating Cycles and Related Structures'. Together they form a unique fingerprint.

    Cite this