Transversal designs and induced decompositions of graphs
type: Item
instance of: scholarly article
title: Transversal designs and induced decompositions of graphs
zbMATH Open document ID: 1347.05153
author: Csilla Bujtás
author: Zsolt Tuza
published in: Journal of Combinatorics
publication date: 2016-05-25T00:00:00Z
full work available at URL: https://arxiv.org/abs/1501.03518
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 6585220
zbMATH Keywords: induced subgraph
zbMATH Keywords: decomposition
zbMATH Keywords: extremal graph theory
Wikidata QID: Q59072428
reviewed by: Sebastian Cioaba
MaRDI profile type: MaRDI publication profile
DOI: 10.4310/JOC.2016.V7.N2.A3
review text: Given two graphs \(G\) and \(H\), an induced \(H\)-decomposition of \(G\) is a collection \(\{H_1,\dots,H_k\}\) of pairwise edge-disjoint induced subgraphs of \(G\) such that each \(H_i\) is isomorphic to \(H\) for \(1\leq i\leq k\) and the edge set of \(G\) is a union of the edge sets of \(H_1,\dots,H_k\). Except when \(H\) is the complete graph on \(2\) vertices, not every graph \(G\) has an \(H\)-decomposition.NEWLINENEWLINEThe following interesting problem was proposed by \textit{J. A. Bondy} and \textit{J. L. Szwarcfiter} [J. Graph Theory 72, No. 3--4, 462--477 (2013; Zbl 1261.05082)]: given a non-complete graph \(H\) with \(v\) vertices and \(n\geq v\), what is the largest number of edges \(ex^{\ast}(n,H)\) of a graph on \(n\) vertices that has an induced \(H\)-decomposition ? \textit{N. Cohen} and \textit{Z. Tuza} [ibid. 78, No. 2, 97--107 (2015; Zbl 1305.05119)] proved that for every graph \(H\), \({n\choose 2}-\mathrm{ex}^{\ast}(n,H)=o(n^2)\).NEWLINENEWLINEIn this paper, using design theoretic and combinatorial tools, the authors proved that when \(H\) is a complete multipartite graph, then \({n\choose 2}-\mathrm{ex}^{\ast}(n,H)=O(n)\). The paper concludes with several interesting directions (5 conjectures and 1 problem) for future research.
Recommended article: Induced decompositions of highly dense graphs
Recommended article: Induced decompositions of graphs
Recommended article: Orthogonal \(H\)-decompositions.
Recommended article: Graphs having the local decomposition property
Recommended article: On colored designs. I
description: scientific article; zbMATH DE number 6585220