Transversal designs and induced decompositions of graphs

Zsolt Tuza (Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary; and Department of Computer Science and Systems Technology, University of Pannonia, Veszprém, Hungary)

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.

Full Text (PDF format)

Published 23 February 2016