The minimum number of Hamilton cycles in a Hamiltonian threshold graph of a prescribed order

Pu Qiao; Xingzhi Zhan

doi:10.1002/jgt.22483

The minimum number of Hamilton cycles in a Hamiltonian threshold graph of a prescribed order

Pu Qiao
, Xingzhi Zhan^*

^*Corresponding author for this work

School of Mathematical Sciences

East China University of Science and Technology

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

2 Scopus citations

Abstract

We prove that the minimum number of Hamilton cycles in a Hamiltonian threshold graph of order (Formula presented.) is (Formula presented.) and this minimum number is attained uniquely by the graph with degree sequence (Formula presented.) of (Formula presented.) distinct degrees. This graph is also the unique graph of minimum size among all Hamiltonian threshold graphs of order (Formula presented.).

Original language	English
Pages (from-to)	222-229
Number of pages	8
Journal	Journal of Graph Theory
Volume	93
Issue number	2
DOIs	https://doi.org/10.1002/jgt.22483
State	Published - 1 Feb 2020

Keywords

Hamiltonian graph
minimum size
number of Hamilton cycles
threshold graph

Access to Document

10.1002/jgt.22483

Cite this

@article{ddf3f6c025be4f83aad24c5b86356a01,

title = "The minimum number of Hamilton cycles in a Hamiltonian threshold graph of a prescribed order",

abstract = "We prove that the minimum number of Hamilton cycles in a Hamiltonian threshold graph of order (Formula presented.) is (Formula presented.) and this minimum number is attained uniquely by the graph with degree sequence (Formula presented.) of (Formula presented.) distinct degrees. This graph is also the unique graph of minimum size among all Hamiltonian threshold graphs of order (Formula presented.).",

keywords = "Hamiltonian graph, minimum size, number of Hamilton cycles, threshold graph",

author = "Pu Qiao and Xingzhi Zhan",

note = "Publisher Copyright: {\textcopyright} 2019 Wiley Periodicals, Inc.",

year = "2020",

month = feb,

day = "1",

doi = "10.1002/jgt.22483",

language = "英语",

volume = "93",

pages = "222--229",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "2",

}

TY - JOUR

T1 - The minimum number of Hamilton cycles in a Hamiltonian threshold graph of a prescribed order

AU - Qiao, Pu

AU - Zhan, Xingzhi

PY - 2020/2/1

Y1 - 2020/2/1

N2 - We prove that the minimum number of Hamilton cycles in a Hamiltonian threshold graph of order (Formula presented.) is (Formula presented.) and this minimum number is attained uniquely by the graph with degree sequence (Formula presented.) of (Formula presented.) distinct degrees. This graph is also the unique graph of minimum size among all Hamiltonian threshold graphs of order (Formula presented.).

AB - We prove that the minimum number of Hamilton cycles in a Hamiltonian threshold graph of order (Formula presented.) is (Formula presented.) and this minimum number is attained uniquely by the graph with degree sequence (Formula presented.) of (Formula presented.) distinct degrees. This graph is also the unique graph of minimum size among all Hamiltonian threshold graphs of order (Formula presented.).

KW - Hamiltonian graph

KW - minimum size

KW - number of Hamilton cycles

KW - threshold graph

UR - https://www.scopus.com/pages/publications/85070830339

U2 - 10.1002/jgt.22483

DO - 10.1002/jgt.22483

M3 - 文章

AN - SCOPUS:85070830339

SN - 0364-9024

VL - 93

SP - 222

EP - 229

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 2

ER -

The minimum number of Hamilton cycles in a Hamiltonian threshold graph of a prescribed order

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this