Does there exist any other graph class that has as many maximal cliques as Moon–Moser graphs?

85 Views Asked by At

According to wikipedia:

The Turán graph $T(n,\lceil n/3\rceil )$ has $3^a2^b$ maximal cliques [...]. This is the largest number of maximal cliques possible among all n-vertex graphs regardless of the number of edges in the graph (Moon and Moser 1965); these graphs are sometimes called Moon–Moser graphs.

But, is there any other graph class that, for the same amount of vertices, can provide the same amount of maximal cliques as Moon-Moser graphs does? Because that quote says it contains the maximum amount of maximal cliques possible, but not that Moon-Moser graphs are the only ones wich such property.

1

There are 1 best solutions below

0
On BEST ANSWER

Theorem 2 in the Moon and Moser paper says that for $n\ge 2$, these are the only examples.

A summary of the argument is that we can modify a graph $G$ by the following operation: if $x$ and $y$ are two non-adjacent vertices, then $G(x;y)$ is the graph obtained by removing all edges incident to $x$, and then joining $x$ to every neighbor of $y$.

The graph $G(x;y)$ will have more cliques than $G$ in the following two cases:

  1. If $G$ has more cliques containing $y$ than $x$;
  2. If $G$ has the same number of cliques containing $x$ and $y$, but one of the cliques $K$ containing $x$ remains maximal when you delete $x$ (in the sense that $K-x$ is a maximal clique of $G-x$).

In particular, if $G$ is a graph with the maximum number of maximal cliques, then case 1 is not true for any graph, any two non-adjacent vertices are in the same number of cliques, and we can apply the operation however we like to obtain another graph with the maximum number of maximal cliques.

By applying the operation enough times, we can always get from $G$ to a Turán graph, and it's easy to check that the only Turán graphs with this property are the Moon–Moser graphs. Finally, we check that if $G(x;y)$ is a Moon–Moser graph, then $G$ must either also be a Moon–Moser graph, or else must have fewer maximal cliques than $G(x;y)$.