4
$\begingroup$

Let $N$ be a positive integer,$G$ be a simple graph and $H_1,H_2,\ldots,H_k$ be a family of subgraphs of $G$ which satisfy:

  1. every $H_i$ is a $N$-order complete graph;
  2. the union of $H_i$ is $G$;
  3. the maximal clique size of $G$ is $N$;
  4. $H_i$ is not equal to $H_j$ and the intersection of $H_i$ and $H_j$ is not empty for any different $i$ and $j$;
  5. the intersection of $H_i$ is empty.

I want to ask what is the minimum possible value of the order of G.

(Here for any two simple graph $G_1$=($V_1$,$E_1$) and $G_2$=($V_2$,$E_2$),define the union of $G_1$ and $G_2$ be (the union of $V_1$ and $V_2$ , the union of $E_1$ and $E_2$), the intersection of $G_1$ and $G_2$ be (the intersection of $V_1$ and $V_2$ , the intersection of $E_1$ and $E_2$).)

$\endgroup$
2
  • $\begingroup$ What do you mean by: "5 the intersection of Hi is empty;"? $\endgroup$ Commented Sep 23, 2013 at 16:35
  • $\begingroup$ I assume user40096 means that $\bigcap_{i=1}^k V(H_i)=\emptyset$. $\endgroup$
    – Tony Huynh
    Commented Sep 23, 2013 at 16:54

1 Answer 1

1
$\begingroup$

In a beautiful paper A. Hajnal obtained the following Lemma.

Lemma. Let $G$ be a graph on $n$ vertices containing no $(k+1)$-clique. Then all $k$-cliques in $G$ have at least $2k-n$ common vertices.

This yields that $G$ should contain at least $2N$ vertices, otherwise the $H_i$ have a common vertex.

On the other hand, a complete graph on $2N$ vertices with a perfect matching removed contains no $(N+1)$-clique, but it contains $2^{N-1}$ pairwise intersecting cliques of size $N$. So, if $3\leq k\leq 2^{N-1}$, then the answer is $2N$.

$\endgroup$
1
  • $\begingroup$ Daniel's answer was deleted on his request. $\endgroup$
    – Todd Trimble
    Commented Mar 3, 2016 at 22:23

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.