If a vertex belongs to many maximal cliques, does it belong to a large star?

76 Views Asked by At

I am curious about the following question:

Suppose I have a connected graph $G = (V,E)$, and let $v \in V$. Let $K_v$ denote the set of maximal cliques in $G$ that contain $v$. Now, suppose $v$ is the center of some maximal induced star $K_{1,n}$, for some fixed $n \in \mathbb{N}$. I would like to show that there exists a constant $C$ such that $|K_v| \le Cn$, but I am unsure how to proceed with this claim (and in fact am starting to suspect this claim may be false).

I would like for this claim to be true, but I've been able to construct progressively worse examples e.g. I was able to construct an example of a graph that contains a vertex $v$ that belongs to 12 maximal cliques (all of which are isomorphic to $K_4$), but the largest star centered at $v$ is a $K_{1,2}$. The example is given in the image below, where $v$ is the central vertex.

enter image description here

As a result, I am starting to suspect that if pairs of maximal cliques are allowed to have large intersection, then the claim will not be true (for example in the image above, some maximal cliques intersect on all but a pair of vertices). If it does not hold in general, then does it start to hold when I limit the size of the intersection between two maximal cliques (say no two maximal cliques intersect on more than $m$ vertices)?

1

There are 1 best solutions below

0
On BEST ANSWER

Consider a complete bipartite graph $K_{n,n}$ and take a cone over it, that is a new vertex $v$ adjacent to all of that graph. Then the maximal induced star containing $v$ has size $n$ but $|K_v|=n^2$.