Transversal designs and induced decompositions of graphs

DOI10.4310/JOC.2016.V7.N2.A3zbMATH Open1347.05153arXiv1501.03518WikidataQ59072428 ScholiaQ59072428MaRDI QIDQ286751FDOQ286751

Zsolt Tuza, Csilla Bujtás

Publication date: 25 May 2016

Published in: Journal of Combinatorics (Search for Journal in Brave)

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 $nchoose2-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.

Full work available at URL: https://arxiv.org/abs/1501.03518

zbMATH Keywords

decompositionextremal graph theoryinduced subgraph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (5)

• Designs with mutually orthogonal resolutions and decompositions of edge‐colored graphs
• Title not available (Why is that?)
• Truncated transversal designs: A new lower bound on the number of idempotent MOLS of side \(n\)
• Title not available (Why is that?)
• Set-Codes with Small Intersections and Small Discrepancies

This page was built for publication: Transversal designs and induced decompositions of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q286751)