# Number of maximal cliques in graphs without common neighbourhoods

Let's consider a graph $$G(n)$$ of $$n$$ vertices such as no two vertices in $$G$$ have the same exact neighbors (different open neighbourhoods to be more specific; I wonder if this kind of graphs have already a name). Which is the maximum number of maximal cliques of such graphs? Is that amount polynomically bounded?

Additional related question: which extra conditions must such graphs have to be planar? This is in fact a related question because planar graph does indeed have a polynomically bounded amount of maximal cliques.

• Doesn't an $n$-clique satisfy your condition? Commented Dec 13, 2020 at 15:31
• @Ariel But it would have the maximum number of maximal cliquies: one Commented Dec 13, 2020 at 15:57
• @Ariel the utility graph doesn't satify my condition and it's a 1-clique if I'm not wrong.
– ABu
Commented Dec 13, 2020 at 15:57
• @Peregring-lk Any connected graph can be converted to your graph by adding a pendant vertex on each vertex of the graph. And the number of vertices only increases twice. Therefore, you can reduce your problem to a general connected graph. Commented Dec 13, 2020 at 16:05
• Let $M$ be the Moon–Moser graph $K_{3,3,\cdots,3}$ with $3k$ vertices $v_{i,j}$ for $i=1,2,3$ and $j=1,2,\cdots,k$. Let $G$ be $M$ with additional vertices $u_1, u_2$ and additional edges $\{v_{1,j}, u_1\}$ and $\{v_{2,j}, u_2\}$ for all $j$. Check that all neighbourhoods are different. For $k\ge2$, the number of maximum cliques is $3^k = 3^{\frac{n-2}3}=\omega((\sqrt{n}!)^c)$ for any constant $c$, where $\sqrt{n}!$ is Yuval's answer. Commented Dec 15, 2020 at 10:13

Suppose that $$n$$ is a perfect square, and identify its vertex set with $$\{1,\ldots,\sqrt{n}\}^2$$. Connect $$(a,b)$$ to $$(c,d)$$ if $$a \neq c$$ and $$b \neq d$$. You can identify a vertex from the set of its neighbors, so the open neighborhoods are all distinct. The number of maximal cliques is $$\sqrt{n}!$$, which isn't polynomial.
• So for example if $n$ is $9$, would its vertex set be the cartesian product between $\{1, 2, 3\}$ with itself right?
• Right, $\sqrt{9} = 3$ and $[3] = \{1,2,3\}$. Commented Dec 13, 2020 at 16:10
• Amazing graphs. Assuming $n$ is a perfect square, are these graphs the ones having the maximum number of cliques while satisfying my conditions? They seem like Moon-Moser graphs with just the minimal modifications to satisfy my criteria, although the number of groups, instead of being $n/3$ of size $3$, are $\sqrt n$ of size $\sqrt n$.