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

On Hamiltonicity of circulant digraphs

Iva Antončič (2011) On Hamiltonicity of circulant digraphs. Diploma thesis.

[img]
Preview
PDF
Download (3567Kb)

    Abstract

    A circulant digraph Circ(n;\, S) is a digraph with vertex set Zn and arcs from v to v+s for each v in Zn, and s in S. The bachelor thesis deals with existence of Hamilton cycle in circulant digraphs with outdegree 2 or 3. Hamilton cycle of a digraph is a closed walk, which meets every vertex exactly ones. Due to Rankin the hamiltonicity question of circulant digraphs of outdegree 2 is solved since 1946. Circulant digraphs of outdegree 3 have however turned out to be more challenging. There are some families, for which we can prove the existence of a Hamilton cycle and some families, for which we can prove nonexistence of such a cycle, but for most of circulant digraphs of outdegree 3 we know nothing jet. In the bachelor thesis we take a close look at Rankin's result for circulant digraphs of outdegree 2 and previous results that consider circulant digraphs of outdegree 3. Besides that we use computer program to examine the hamiltonicity of circulant digraphs of outdegree 3, that have 87 or less vertices.

    Item Type: Thesis (Diploma thesis)
    Keywords: Cayley digraph, circulant digraph, hamiltonicity, Hamilton cycle
    Number of Pages: 66
    Language of Content: Slovenian
    Mentor / Comentors:
    Mentor / ComentorsIDFunction
    doc. dr. Primož ŠparlMentor
    Link to COBISS: http://www.cobiss.si/scripts/cobiss?command=search&base=50126&select=(ID=8903753)
    Institution: University of Ljubljana
    Department: Faculty of Education
    Item ID: 532
    Date Deposited: 02 Dec 2011 13:25
    Last Modified: 02 Dec 2011 13:25
    URI: http://pefprints.pef.uni-lj.si/id/eprint/532

    Actions (login required)

    View Item