Transversal designs and induced decompositions of graphs

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

Authors: Csilla Bujtás, Zsolt Tuza 

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

Recommendations

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

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 (9)

• Designs with mutually orthogonal resolutions and decompositions of edge‐colored graphs
• Title not available (Why is that?)
• Induced decompositions of highly dense graphs
• Set-codes with small intersections and small discrepancies
• Nearly complete graphs decomposable into large induced matchings and their applications
• Truncated transversal designs: A new lower bound on the number of idempotent MOLS of side \(n\)
• Title not available (Why is that?)
• 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)