1
$\begingroup$

I am interested in the graph theory/combinatorics problem:

if you have a cycle, how many ways can you rearrange the edges and nodes such that you still only have one cycle?

any discussion is welcome

To state it another way

If the graph itself was simply one large cycle, how many ways could I rearrange the edges while maintaining a single cycle? Only one incoming and outgoing edge per node and therefore the length of the cycle must be the same with each permutation.

nodes are marked edges are not.

Does that may things clearer?

$\endgroup$
4
  • 1
    $\begingroup$ Are you asking about rearranging a graph without touching that specific cycle? (Otherwise the fact it had a cycle originally means nothing more than a min length requirement) $\endgroup$
    – Guest 86
    Jan 21 '13 at 23:59
  • $\begingroup$ If the graph itself was simply one large cycle, how many ways could I rearrange the edges while maintaining a single cycle? Only one incoming and outgoing edge per node and therefore the length of the cycle must be the same with each permutation. Does that may things clearer? $\endgroup$ Jan 22 '13 at 0:08
  • $\begingroup$ Yes, are both the edges and nodes marked? $\endgroup$
    – Guest 86
    Jan 22 '13 at 0:14
  • $\begingroup$ nodes are marked edges are not $\endgroup$ Jan 22 '13 at 0:14
1
$\begingroup$

If you have a cycle graph with $N$ nodes and edges, you can permute the nodes among themselves in $N!$ ways, without altering the shape (Is the word here topology?).

But as this results in similar graphs up to rotation, you should either treat it as holding a node constant and performing the permutation on the remaining $N-1$ nodes for a $(N-1)!$ result or simply divide the previous result by $N$ for there are this many equivalence classes.

$\endgroup$
3
  • $\begingroup$ This overcounts the possibilities because a cycle can be rotated without giving a different graph. Hanging our hats on the OP's commment (not entirely consistent with how the question is asked) that "nodes are marked[;] edges are not", one wants a count of permuting "the nodes among themselves" that gives distinct cycles. $\endgroup$
    – hardmath
    Jan 22 '13 at 0:20
  • $\begingroup$ hardmath, that is exact what I want. How many distinct cycles can I obtain. $\endgroup$ Jan 22 '13 at 0:22
  • 1
    $\begingroup$ Ah my bad, should've held one node as a constant permuting the remaining $N-1$ or simply divide the result by $N$ as there are N equivalent classes. I'll fix it, sorry. $\endgroup$
    – Guest 86
    Jan 22 '13 at 0:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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