Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles

Michael Haythorpe

doi:10.5614/ejgta.2016.4.1.3

Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles

Michael Haythorpe

Research output: Contribution to journal › Article › peer-review

3 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 language	English
Pages (from-to)	18-25
Number of pages	8
Journal	Electronic Journal of Graph Theory and Applications
Volume	4
Issue number	1
DOIs	https://doi.org/10.5614/ejgta.2016.4.1.3
Publication status	Published - 2016

Keywords

Broken crown
Graph construction
Hamiltonian cycles

Access to Document

10.5614/ejgta.2016.4.1.3

Cite this

@article{761868a4aa89410394460109f12b56bf,

title = "Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles",

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.",

keywords = "Broken crown, Graph construction, Hamiltonian cycles",

author = "Michael Haythorpe",

year = "2016",

doi = "10.5614/ejgta.2016.4.1.3",

language = "English",

volume = "4",

pages = "18--25",

journal = "Electronic Journal of Graph Theory and Applications",

issn = "2338-2287",

publisher = "Indonesian Combinatorics Society",

number = "1",

}

TY - JOUR

T1 - Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles

AU - Haythorpe, Michael

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - Broken crown

KW - Graph construction

KW - Hamiltonian cycles

UR - http://www.ejgta.org/index.php/ejgta/article/view/97/pdf_13

UR - http://www.scopus.com/inward/record.url?scp=85007334212&partnerID=8YFLogxK

U2 - 10.5614/ejgta.2016.4.1.3

DO - 10.5614/ejgta.2016.4.1.3

M3 - Article

SN - 2338-2287

VL - 4

SP - 18

EP - 25

JO - Electronic Journal of Graph Theory and Applications

JF - Electronic Journal of Graph Theory and Applications

IS - 1

ER -

Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this