I have been reading a lot on the theory of Turan graphs, but I could not find anything on the graphs I am interested in. They are somewhat between complete $k$-partite graphs and Turan graphs.

Let $G=(V,E)$ a graph such that $V$ is partitioned into $r$ subsets $V_1, \dots, V_r$. Let $n<r$ be a positive integer such that for all $1\leq m \leq n$ and for all $(i,j)\in V_m^2$, the edge $(i,j)\in E$ exists in the graph $G$. For the remainings sets, the edges do not exist in $G$: for all $n<m\leq r$ and $(i,j)\in V_m^2$, $(i,j)\notin E.$

In others words, in contrast with the Turan graphs where $G$ would contain no $(r+1)$-clique, here I consider exactly $n$ such cliques. Note that if $n=r$, then $G$ is the complete $r$-partite graph.

My question then is: what can we say about the number of edges in $G$ ?

Does this graph has a name ?

Thanks a lot!

  • 1
    $\begingroup$ The graph $G$ can be the complete graph: take $V_{n+1},\ldots,V_r$ to be singletons. It could also be the empty graph: take $V_1,\ldots,V_n$ to be singletons. $\endgroup$ – Yuval Filmus Oct 31 '12 at 16:51
  • $\begingroup$ I was searching for a similar result of Turan theorem, which claims the maximal number of edges in the graph for a given number of vertices. Or the dual problem: the minimal number of vertices for a given number of edges. $\endgroup$ – wwjoze Oct 31 '12 at 18:01
  • 1
    $\begingroup$ Perhaps you misread my comment. It shows that under your conditions as stated, there is no non-trivial lower or upper bound on the number of edges. $\endgroup$ – Yuval Filmus Nov 1 '12 at 5:21
  • $\begingroup$ Ok, I see your point. Let say then that $G$ needs to have a given number $v=\sum V_i$ of vertices. In the same vein as Turan's theorem, how do we distribute the vertices in the $V_i$s so that the number of edges $e$ in $G$ is maximal? $\endgroup$ – wwjoze Nov 1 '12 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.