0
$\begingroup$

I'm planning on making a fiber art $K_{37}$ (like the one I laser etched with help: K37: The complete graph on 37 nodes, svg). To accomplish this, the plan is to construct 37 pegs equally spaced in a annulus made from wood and then to string yarn between them. Since $K_{37}$ is a complete graph, it has a Hamiltonian path. My knowledge of computational graph theory is nil, and I am aware that this is not exactly an easy problem (see wikipedia: Hamiltonian Path Problem, for instance)

$\endgroup$
  • 4
    $\begingroup$ Every permutation of nodes induces a Hamiltonian path in a complete graph. I'm confused; what's the problem? $\endgroup$ – Raphael Feb 26 '15 at 11:11
  • $\begingroup$ To make a "regular" Hamiltonian path (in the string-like fashion you propose) take any peg/node and connect it to a peg/node a certain number of pegs/nodes from the starting position. Repeat with the same distance. This should work for any distance, as 37 is prime. (Otherwise, I support the comment by @Raphael.) $\endgroup$ – Hendrik Jan Feb 26 '15 at 12:44
  • $\begingroup$ @Raphael: some are more optimal for laying string than others. $\endgroup$ – graveolensa Feb 26 '15 at 13:14
  • $\begingroup$ so I need a permutation that's a derangement? $\endgroup$ – graveolensa Feb 26 '15 at 13:36
  • 2
    $\begingroup$ @deoxygerbe Then your query should be, "how do I find an X-path so that..." -- we can't possibly know which criteria you have in mind. $\endgroup$ – Raphael Feb 26 '15 at 13:49
4
$\begingroup$

It seems that you're trying to construct the graph $K_{37}$ from string and nails without cutting the string. For this, you don't want a Hamiltonian path (a path that visits every vertex exactly once) but an Euler trail (a walk that visits every edge exactly once).

In the case of a complete graph, finding an Euler trail is trivial: start at any vertex and move from vertex to vertex without repeating an edge. As long as the last thing you do is returning to the initial vertex, you've created an Euler trail. (This is essentially Fleury's algorithm except that checking you've not disconnected the graph is trivial for a complete graph.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

$K_n$ has $(n-1)!/2$ Hamiltonian circles and it has $\lfloor(n-1)/2 \rfloor$ distinct Hamiltonian circles (I mean no edge in common), every Hamiltonian circle in a graph with $|V| = n$ has $n$ edges. By removing any of the edges in a Hamiltonian circle the result path is a Hamiltonian path so $k_n$ has $n \times (n-1)!/2 = n!/2 $ Hamiltonian paths and it is the permutation of nodes. What exactly do you want? You can select any of these paths.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.