Counting Hamiltonian cycles in the matroid basis graph (Q1741593)

Given a matroid $M$ and its collection of bases $\mathcal{B}$, its basis graph $BG(M)$ is defined to be the graph with vertex set $\mathcal{B}$, where two bases $B_1$ and $B_2$ are connected if $|B_1 \Delta B_2| = 2$. The authors' general strategy is using good 4-cycles in $BG(M)$ to construct a Hamiltonian cycle in $BG(M)$ containing a given edge $e$ from a Hamiltonian cycle of $BG(M\setminus e)$ and $BG(M/e)$. For the graphic matroid $M_G$ of a 2-edge connected graph of order $n \geq 3$ it is shown, using the general strategy and induction on $n$ that every edge of $BG(M_G)$ is in $2^{n-3}$ Hamiltonian cycles. Corresponding bonds are obtained also for the cycle matroid of $k$-edge-connected graphs and for generalized Catalan matroids. The authors point out that the bounds can be improved to superfactorial ones and refer to [the authors, ``Matroid basis graph: counting Hamiltonian cycles'', Preprint, \url{arXiv:1608.02635}].