1
$\begingroup$

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)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

If you take a the complete bipartite graph $K_{n,n}$ and add a vertex $v$ adjacent to every vertex of the bipartite graph, then the resulting graph has a star of size $n$ centered at $v$, but is a member of $n^2$ maximal cliques.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Perhaps $\ 2\cdot n\,$? $\endgroup$
    – Wlod AA
    Commented May 16, 2020 at 3:21
  • $\begingroup$ To ask a question when you already have an answer is against the spirit of this Q&A group. Thus, I stilled "plused-1" you here but not the question. Please, next time avoid this kind of combination. $\endgroup$
    – Wlod AA
    Commented May 16, 2020 at 3:26
  • $\begingroup$ Can be much worse. Take a complete graph on mn+1 vertices for your favourite m,n, let v be one vertex and remove the edges of a collection of m disjoint n-cliques avoiding v. The largest induced star centred at v has n leaves, but v is in n^m maximal cliques. $\endgroup$
    – user36212
    Commented May 16, 2020 at 14:33
  • $\begingroup$ @WlodAA I agree with the sentiment of what you say; however, when I asked this question, I did not yet have an answer. When I cam upon an answer, I thought I would share the results of this with others who may be interested in the answer $\endgroup$
    – Quotable
    Commented May 17, 2020 at 4:34
  • $\begingroup$ @user36212 Yes, you are right. I actually came across an even more extreme example when investigating this question: Suppose $|V(G)| = n$ is divisible by 3 (for simplicity). Then consider the Turan graph $T(n, n/3)$. Then this is a complete multipartite graph with $n$ stable sets of size 3. Attaching a vertex $v$ adjacent to all vertices in $T(n, n/3)$ then makes $v$ have a largest star of size 3, but who belongs to $3^{n/3}$ maximal cliques. This is in fact as bad as it possibly can get (see the paper Moon and Moser, "On Cliques in Graphs"). $\endgroup$
    – Quotable
    Commented May 17, 2020 at 4:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .