<p>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. </p>

<p>Let $G=(V,E)$ a graph such that $V$ is partitioned into $r$ subsets $V_1, \dots, V_r$. Let $n&lt;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&lt;m\leq r$ and $(i,j)\in V_m^2$, $(i,j)\notin E.$</p>

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

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

<p>Does this graph has a name ?</p>

<p>Thanks a lot!</p>

CC BY-SA 3.0
2012-10-31T16:51:52.287Z
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.
Yuval Filmus
CC BY-SA 3.0
2012-10-31T18:01:26.697Z
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.
wwjoze
CC BY-SA 3.0
2012-11-01T05:21:16.863Z
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.
Yuval Filmus
CC BY-SA 3.0
2012-11-01T09:45:53.213Z
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?
wwjoze
<graph-theory><co.combinatorics>
Generalized Turan Graphs
wwjoze
# Generalized Turan Graphs

(Asked by: username_0 on 2012-10-31)

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

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!

**Tags:** graph-theory, co.combinatorics
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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?  

---

## 0 answers

