Maximal cliques on graphs on the vertices of regular $2n$-gons Consider the vertices of a regular $2n$-gon in the plane, and label the points clockwise $1,\dots,2n$. For any vertex $v$ let $-v$ denote its opposite vertex on the polygon.
Define a graph $G$ which says that for any vertex $v$, we connect $v$ to all other vertices except $-v,(-v-1),$ and $(-v+1)$. That is, connect $v$ to all other vertices except its opposite vertex, and one on each side of it.
I would like to know how to calculate the number of maximal cliques of this family of graphs as $n\to \infty$.
I know how to do it when we disconnect only opposite vertices, because then we obtain a complete $n$-partite graph which has $2^n$ maximal cliques, formed by choosing one vertex from each of $n$ sets of two vertices.
The same argument does not seem to immediately apply when we disconnect the neighbors of $-v$ from $v$ as well, but is there a combinatorial method that would give the number of maximal cliques of this graph?
 A: I think it's a very interesting question.
Here are some thoughts on it.
Let $G_n$ be a graph on $2n$ vertices defined in the question. Consider its complement graph denoted by $H_n$.
The graph $H_n$ is a cubic graph which can be defined as follows. The vertices of the graph $H_n$ are elements of the additive group $\mathbb{Z}_{2n}$. Two vertices $x,y$ are connected by an edge if and only if $x-y\in\{n-1,n,n+1\}\pmod{2n}$.

Our problem is now to compute the number of maximal independent sets
of vertices of graph $H_n$. It is easy to see that the number of
independence is $\alpha(H_n)=n-1$.


*

*Consider first the case when $n$ is even. In this case the numbers $2n$ and $n-1$  are coprime. Hence $n-1$ is a generating one in the group $\mathbb{Z}_{2n}$.
It follows that we have a Hamiltonian cycle in $H_n$:
$$
0,n-1,2(n-1),\ldots,(2n-1)(n-1). 
$$
Moreover, since $n(n-1)\equiv n\pmod{2n}$  ($n$ is even) we see that the opposite vertices of this cycle are adjacent:
$$
x+n(n-1)\equiv x+n\pmod{2n}.
$$
It follows that the graph $H_n$ is isomorphic to the graph called Möbius ladder
and denoted by  $M_{2n}$.
The number of independent sets of vertices of the graph $H_n=M_{2n}$ is the sequence A182143


*Now consider the case when $n$ is odd.
In this case we get the next two cycles of length $n$:
\begin{align*}
     & 0,n-1,2(n-1),\ldots,(n-1)(n-1); \\     
     & n,n+(n-1),n+2(n-1),\ldots,n+(n-1)(n-1).
  \end{align*}
Since $n+k(n-1)-k(n-1)=n$ we have the corresponding vertices of these two cycles are adjacent.
Hence in this case our graph $H_n$ is isomorphic to the prism graph $Y_n$.
The number of independent sets of vertices in the prism graph $H_n=Y_n$ is the sequence A051927
