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

Csilla Bujtás (Department of Computer Science and Systems Technology, University of Pannonia, Veszprém, Hungary)

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