5
$\begingroup$

A Hamiltonian decomposition of a finite simple graph is a partition of its edge set so that each partition class forms a Hamiltonian cycle. This is only possible if the graph is $2k$-regular.

Interestingly, if a 4-regular graph has a Hamiltonian decomposition then it has at least four of them (stated here). In my experience however, a "generic" 4-regular graph with a Hamiltonian decomposition has many more than four such decompositions.

Question 1: How to generate or construct many 4-regular graphs with exactly four Hamiltonian decompositions? For a start, a few examples would help as well.

Question 2: Are there any related results that provide (better) lower bounds on the number of Hamiltonian decompositions of 4-regular graphs?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ If I understand it correctly, here for each integer $n\geq3$ multigraphs of order $n$ with exactly four hamiltonian pairs are constructed. Moreover, in section 6 the following conjecture is formulated. 16 is the smallest value among nonzero numbers of hamiltonian pairs in 4-regular simple graphs of any order. $\endgroup$
    – kabenyuk
    Commented Apr 6, 2022 at 9:16
  • 2
    $\begingroup$ @kabenyuk, your comment is missing $\ge 15$ at the end. $\endgroup$
    – Peter Taylor
    Commented Apr 6, 2022 at 10:06
  • $\begingroup$ @PeterTaylor Yes, you are correct. The conjecture reads as follows: 16 is the smallest value among nonzero numbers of hamiltonian pairs in 4-regular simple graphs of any order $\geq15$. Thank you. $\endgroup$
    – kabenyuk
    Commented Apr 6, 2022 at 14:40

0

Reset to default

You must log in to answer this question.