Most efficient way to output a cycle starting from an unordered list of graph vertices

Question

I have some graph $G$ and a list of vertices $(v_1, ..., v_N) \in V$. Using graph structures in Mathematica version 9.0, what is the most efficient way to determine whether or not $(v_1, ..., v_N)$ represents a cycle, and then, if so, to output a permutation cycle starting from some desired $v_i$?

---

Let me provide a specific example:

Say I have a ring of eight vertices where:

$v_1 \to v_2$

$v_2 \to v_3$

$v_3 \to v_4$

$v_4 \to v_5$

$v_5 \to v_6$

$v_6 \to v_7$

$v_7 \to v_8$

$v_8 \to v_1$

And also:

$v_2 \to v_4$

$v_4 \to v_6$

$v_6 \to v_8$

$v_8 \to v_2$

Say the above list is scrambled (i.e. we randomly assign the vertex labels). Without scrambling things here, and specifying that I want a permutation to start from $v_2$, how would I output a permutation:

$(v_2,v_3,v_4,v_5,v_6,v_7,v_8,v_1)$

Scrambling, we could maybe map the labels: $(v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8)$ to something like: $(v_{1111111111}, v_{11011}, v_{111110011}, v_{100101}, v_{11}, v_{1010111}, v_{111}, v_{101010101})$ where the labels convey no ordering information.

Answer 1

If I am reading your question correctly, you are looking for

HamiltonianGraphQ@Subgraph[g, {v1, v2, ...}]

You can use FindHamiltonianCycle to actually find a cycle (an ordering of vertices).

Answer 2

If you just want to verify a given list of vertices is a cycle, you could define the following function to check it's cycle:

cycleQ[g_, vs_] :=
      Block[{edge},
          edge = If[DirectedGraphQ[g], DirectedEdge, UndirectedEdge];
          VectorQ[Partition[vs, 2, 1, 1], EdgeQ[g, edge @@ #] &]
      ]

For example,

g = CycleGraph[10];

In[96]:= cycleQ[g, Range[5]]
Out[96]= False

In[97]:= cycleQ[g, Range[10]]
Out[97]= True

To permute the list, you could use RotateLeft or RotateRight with Position:

In[91]:= RotateLeft[{a, b, c, d, e}, 
             Position[{a, b, c, d, e}, d][[1, 1]] - 1]
Out[91]= {d, e, a, b, c}