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$

closed as unclear what you're asking by D.W., Luke Mathieson, Juho, Guildenstern, Wandering Logic Mar 1 '15 at 14:14

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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.

$\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.

$\endgroup$

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