1
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Doesn't an $n$-clique satisfy your condition? $\endgroup$
    – Ariel
    Commented Dec 13, 2020 at 15:31
  • 1
    $\begingroup$ @Ariel But it would have the maximum number of maximal cliquies: one $\endgroup$
    – Inuyasha Yagami
    Commented Dec 13, 2020 at 15:57
  • $\begingroup$ @Ariel the utility graph doesn't satify my condition and it's a 1-clique if I'm not wrong. $\endgroup$
    – ABu
    Commented Dec 13, 2020 at 15:57
  • $\begingroup$ @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. $\endgroup$
    – Inuyasha Yagami
    Commented Dec 13, 2020 at 16:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – John L.
    Commented Dec 15, 2020 at 10:13

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ So for example if $n$ is $9$, would its vertex set be the cartesian product between $\{1, 2, 3\}$ with itself right? $\endgroup$
    – ABu
    Commented Dec 13, 2020 at 16:04
  • $\begingroup$ Right, $\sqrt{9} = 3$ and $[3] = \{1,2,3\}$. $\endgroup$
    – Yuval Filmus
    Commented Dec 13, 2020 at 16:10
  • $\begingroup$ 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$. $\endgroup$
    – ABu
    Commented Dec 13, 2020 at 16:54
  • 1
    $\begingroup$ They’re just the first thing that came to mind. No reason to believe that this construction is optimal, though who knows... $\endgroup$
    – Yuval Filmus
    Commented Dec 13, 2020 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.