Sparse hamiltonian 2-decompositions together with exact count of numerous Hamilton cycles

作者：Skupien Zdzislaw^*

来源：Discrete Mathematics, 2009, 309(22): 6382-6390.

DOI：10.1016/j.disc.2008.11.003

• Multigraph
• Hamiltonian pair
• Squared cycle
• Construction
• Counting Hamilton cycles
• Traceable pair

We construct multigraphs of any large order with as few as only four 2-decompositions into Hamilton cycles or only two 2-decompositions into Hamilton paths. Nevertheless, some of those multigraphs are proved to have exponentially many Hamilton cycles (Hamilton paths). Two families of large simple graphs are constructed. Members in one class have exactly 16 hamiltonian pairs and in another class exactly four traceable pairs. These graphs also have exponentially many Hamilton cycles and Hamilton paths, respectively. The exact numbers of (Hamilton) cycles and paths are expressed in terms of Lucas- or Fibonacci-like numbers which count 2-independent vertex (or edge) subsets on the n-path or n-cycle. A closed formula which counts Hamilton cycles in the square of the n-cycle is found for n >= 5. The presented results complement, improve on, or extend the corresponding well-known Thomason's results.

• 出版日期2009-11-28