Transversal designs and induced decompositions of graphs

DOI10.4310/JOC.2016.V7.N2.A3MaRDI QIDQ286751zbMATH OpenWikidataFDO

Authors Csilla Bujtás, Zsolt Tuza

Publication date 25 May 2016

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

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)

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.

Recommendations

• Induced decompositions of highly dense graphs
• Induced decompositions of graphs
• Orthogonal \(H\)-decompositions.
• Graphs having the local decomposition property
• On colored designs. I

Cited in

(9)

• Designs with mutually orthogonal resolutions and decompositions of edge‐colored graphs
• scientific article; zbMATH DE number 4008405 (Why is no real title available?)
• Induced decompositions of highly dense graphs
• Set-codes with small intersections and small discrepancies
• Truncated transversal designs: A new lower bound on the number of idempotent MOLS of side \(n\)
• Nearly complete graphs decomposable into large induced matchings and their applications
• scientific article; zbMATH DE number 3849246 (Why is no real title available?)
• On graphs decomposable into induced matchings of linear sizes
• Induced decompositions of graphs

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)