P(A) is a cyclic permutation graph A if each vertex is shifted by one in P : (P({1, 2, 3, ..., n - 1, n}) = {2, 3, ..., n - 1, n, 1}).
e.g : cyclic permutation of 2 - 4 - 1 - 3 is 3 - 1 - 2 - 4
Given a number n, how many graphs A with n vertices has cyclic permutation P which G and P(G) have the exact opposite set of edges (if vertex x is connected to vertex y, then P(x) is not connected to P(y), if vertex x is not connected to vertex y, then P(x) is connected to P(y))
E.g when n = 4 There are 4 different graphs with 4 vertices has P(x) which has properties like mentioned above.
What is the formula or approach for this problem, i think it has somthing to do with Burside 's lemma but after hours of thinking i can not figure out the formula. Thanks for your help!
The edges form different types of cycles under this permutation. Edges of the form $\left(k,k+\frac n2\right)$ form a cycle with period $\frac n2$, whereas all other edges form cycles with period $n$.
Thus, if $n$ is odd or $\frac n2$ is odd, there are no such graphs, since there are cycles of odd length that can't be coloured consistently.
In the remaining case, where $n$ is a multiple of $4$, we have
$$ \frac{\binom n2-\frac n2}n=\frac{n(n-1)-n}{2n}=\frac n2-1 $$
cycles of length $n$, for a total of $\frac n2$ cycles, each of which can independently be coloured in two different ways, so there are $2^{\frac n2}$ different ways to colour them, in agreement with your result for $n=4$.
You can readily relate this to your diagrams for $n=4$. The cycle of length $4$ is the outer ring, and the cycle of length $2$ is the cross in the centre. Each of your diagrams shows one of the $2\cdot2$ combinations of alternating colourings for these cycles.