0
$\begingroup$

Is there any way to know that a digraph has odd nubmer of hampaths if hamiltonian paths exist?

Just curious.

1 Answers 1

1

In some cases, deducing the number of Hamilton paths modulo $2$ is easy, such as when the graph has an order $2$ automorphism.

Observation: If a digraph has an automorphism $\alpha$ of order $2$, then the number of Hamilton paths is even.

Proof: We act on the set of Hamilton paths using $\langle \alpha \rangle$, thereby partitioning the set into orbits of size either $2$ or $1$. By the Orbit-Stabiliser Theorem, orbits of size $1$ contain Hamilton paths that are stabilised by $\alpha$, but this cannot happen (as it would imply the directed path has an automorphism, which it doesn't). $\square$

(By the same argument, we can deduce that $|\mathrm{Aut}(G)|$ divides the number of Hamilton paths of $G$.)


In general, though, I suspect it would require enumeration. Working modulo $2$, it would be possible to reduce the search space using some tricks. E.g. if during the enumeration we encounter the two partial Hamilton paths (a,b,c,d) and (c,a,b,d), then any completion of (a,b,c,d) also results in a completion of (c,a,b,d), and vice versa, together contributing $0 \pmod 2$ to the overall total, and thus we needn't continue extending these paths.