3
$\begingroup$

Given a set of $n$ states $V = \{ s_1, s_2, \ldots, s_n \}$, and a complete digraph $G = (V, A)$ where $A = \{ (a,b) \mid (a,b) \in V^2\; \text{and}\; a \neq b \}$, I'm interested in finding cyclic trails through $G$ which traverse every element of $A$ exactly once.

I've found a number of different ways to construct such trails, including one based on A097285 (the sequence that contains exactly once every pair $(i,j)$ of distinct positive integers): $t = (a_1, a_2, \ldots, a_{n*(n+1)})$ where $a_i = (s_{A097285(i)}, s_{A097285(i+1)})$.

Given that there's more than one way to construct such trails, I'd like to better understand how to construct such trails, how many there are for a given $n$, and how the properties of different trails compare (e.g. in my practical application of this, it's desirable to construct trails which visit each vertex at least once as early as possible along the trail).

Also, what other problems are related to or isomorphic to this? I'm kinda getting vibes of Gray codes and modular arithmetic, but I've not been able to figure out an exact connection on my own just yet.

$\endgroup$
5
  • $\begingroup$ Are you asking for the number of Hamilton cycles of the complete graph? $n!$? $\endgroup$
    – Mathieu Rundström
    Commented Feb 18 at 4:36
  • $\begingroup$ @MathieuRundström No, I don't think so. I'm interested in visiting each arc exactly once (and therefore each vertex $n-1$ times). I think my graph $G$ could be transformed into a different graph where each $A$ is a vertex, in which I believe finding Hamiltonian cycles would be equivalent to my problem, but doing so just seems like it's making the problem harder (NP-complete), whereas my example solution has a complexity of $n^2$. Also, the number of these cycles is merely a part of my question. $\endgroup$
    – Florian Ragwitz
    Commented Feb 18 at 7:12
  • $\begingroup$ I'm a little confused by your mention of a starting vertex. In the case $n=3$, if the vertices are $x,y,z$ and $x$ is the starting vertex, do you count $xyzyxzx$ and $xzxyzyx$ as two different trails? Is the answer $3$ or $6$ when $n=3$? $\endgroup$
    – user14111
    Commented Feb 24 at 22:39
  • $\begingroup$ The number of Eulerian circuits in a digraph can be computed using the BEST theorem and Kirchoff's matrix-tree theorem; in the case of a complete digraph the latter reduces to Cayley's formula. For one interpretation of your question (which you could disambiguate by giving the number of trails for small values of $n$) the answer is $$((n-2)!)^n\cdot n^{n-2}.$$ $\endgroup$
    – user14111
    Commented Feb 24 at 22:55
  • $\begingroup$ That's for a given starting arc. If you really meant a given starting vertex then multiply by $n-1$ to account for which of the outbound arcs from your starting vertex is traversed first. $\endgroup$
    – user14111
    Commented Feb 25 at 2:54

1 Answer 1

Reset to default
1
+100
$\begingroup$

If you count oriented cycles, the number of such cycles for $n=2,3,4,\ldots$ is

$1, 6, 768, 3888000, \ldots$

If you count non-oriented cycles, ie edge-injective embeddings of the cyclic graph on $n(n-1)$ vertices onto $K_n$, the number of such cycles is

$1, 4, 384, 1944264, \ldots$

Neither sequence is in the OEIS, even omitting the first term, so it seems that such paths are likely not well studied (since no one seems to have even studied the enumeration problem before).

On the question of paths that visit each vertex as early as possible, the number of paths that start with $s_1\to s_2\ldots\to s_n$ is $1, 2, 36, 18432, \ldots$ for $n=2,3,4,5,\ldots$. For all such cycles, add a factor of $(n-1)!$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .