Premium
The minimum number of Hamilton cycles in a Hamiltonian threshold graph of a prescribed order
Author(s) -
Qiao Pu,
Zhan Xingzhi
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22483
Subject(s) - mathematics , combinatorics , hamiltonian path , quartic graph , discrete mathematics , wheel graph , graph , cubic graph , graph power , line graph , voltage graph
We prove that the minimum number of Hamilton cycles in a Hamiltonian threshold graph of order n is 2 ⌊ ( n − 3 ) ∕ 2 ⌋and this minimum number is attained uniquely by the graph with degree sequence n − 1 , n − 1 , n − 2 , … , ⌈ n ∕ 2 ⌉ , ⌈ n ∕ 2 ⌉ , … , 3,2 of n − 2 distinct degrees. This graph is also the unique graph of minimum size among all Hamiltonian threshold graphs of order n .
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom