1
$\begingroup$

Question:
how many pairs $\lbrace H_i, H_j\rbrace$ of edge-disjoint Hamilton cycles are in the complete graph $K_n$ with $n$ vertices?

while I could find information to the maximal number of edge-disjoint Hamilton cycles in $K_n$ I was not able to find anything about the number of combinations $\lbrace H_1,\,\dots,\,H_h\rbrace$, i.e. the number of ways to select $h$ edge-disjoint Hamilton cycles from $K_n$, specifically for $h=2$

Improve this question
$\endgroup$
3
  • $\begingroup$ It should be relatively straightforward to write an inclusion-exclusion expression for this number. $\endgroup$
    – Sam Hopkins
    Commented Jul 11, 2021 at 5:26
  • 2
    $\begingroup$ Related to A002816, isn't it? Number of Hamiltonian cycles in the complement of the cycle graph $C_n$? $\endgroup$
    – bof
    Commented Jul 11, 2021 at 5:43
  • $\begingroup$ Let $\ n>2\ $ be a prime number. Let the vertices form a regular n-gon. There are $\ a:=\frac{n-1}2\ $ Hamiltonian cycles, one for each length of the edges. Then there are $\ \binom a2\ $ (unordered) pairs of these cycles where the members of the same pair are edge-disjoint. $\endgroup$
    – Wlod AA
    Commented Jul 11, 2021 at 7:01

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .