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$ Commented Mar 3, 2016 at 22:23

You must log in to answer this question.

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