Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles

    Research output: Contribution to journalArticlepeer-review

    2 Citations (Scopus)

    Abstract

    A constructive method is provided that outputs a directed graph which is named a broken crown graph, containing 5n - 9 vertices and k Hamiltonian cycles for any choice of integers n ≥ k ≥ 4. The construction is not designed to be minimal in any sense, but rather to ensure that the graphs produced remain non-trivial instances of the Hamiltonian cycle problem even when k is chosen to be much smaller than n.

    Original languageEnglish
    Pages (from-to)18-25
    Number of pages8
    JournalElectronic Journal of Graph Theory and Applications
    Volume4
    Issue number1
    DOIs
    Publication statusPublished - 2016

    Fingerprint Dive into the research topics of 'Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles'. Together they form a unique fingerprint.

    Cite this