Transversal designs and induced decompositions of graphs (Q286751)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Transversal designs and induced decompositions of graphs
scientific article

    Statements

    Transversal designs and induced decompositions of graphs (English)
    0 references
    0 references
    0 references
    25 May 2016
    0 references
    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. The 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)\). In 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.
    0 references
    induced subgraph
    0 references
    decomposition
    0 references
    extremal graph theory
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references