Contents Online

# Journal of Combinatorics

## Volume 7 (2016)

### Number 2–3

Guest editors: Rong Luo and Cun-Quan Zhang

### Transversal designs and induced decompositions of graphs

Pages: 257 – 269

DOI: http://dx.doi.org/10.4310/JOC.2016.v7.n2.a3

#### Authors

#### Abstract

We prove that for every complete multipartite graph $F$ there exist very dense graphs $G_n$ on $n$ vertices, namely with as many as ${^n_2} - cn$ edges for all $n$, for some constant $c = c(F)$, such that $G_n$ can be decomposed into edge-disjoint induced subgraphs isomorphic to $F$. This result identifies and structurally explains a gap between the growth rates $O(n)$ and $\Omega (n^{3/2})$ on the minimum number of non-edges in graphs admitting an induced $F$-decomposition.

#### Keywords

induced subgraph, edge decomposition, complete multipartite graph, extremal graph theory

#### 2010 Mathematics Subject Classification

Primary 05C35, 05C70. Secondary 05C75.

Published 23 February 2016