Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

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?

share|improve this question
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) – Guest 86 Jan 21 at 23:59
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? – user1340048 Jan 22 at 0:08
Yes, are both the edges and nodes marked? – Guest 86 Jan 22 at 0:14
nodes are marked edges are not – user1340048 Jan 22 at 0:14

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
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. – hardmath Jan 22 at 0:20
hardmath, that is exact what I want. How many distinct cycles can I obtain. – user1340048 Jan 22 at 0:22
1  
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. – Guest 86 Jan 22 at 0:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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