Maximal cliques on graphs on the vertices of regular $2n$-gons

Question

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?

Answer 1

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$.

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

2. 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