Minimal decompositions of graphs into mutually isomorphic subgraphs
type: Item
instance of: scholarly article
title: Minimal decompositions of graphs into mutually isomorphic subgraphs
zbMATH Open document ID: 0491.05049
DOI: 10.1007/BF02579173
author: Fan Chung
author: Ron Graham
author: P. Erdős
published in: Combinatorica
publication date: 1981-01-01T00:00:00Z
review text: Let \(G=\{G_1,\dots,G_k\}\) be a collection of \(n\)-vertex graphs each with the same (unspecified) number of edges. Let \(U(G)\) be the least \(r\) for which there exists a set of partitions of the edge sets \(E(G_i)\) of the graph into \(r\) parts, say \(E(G_i)=\cup_{j=1}^{r} E_{ij}\), such that for each j, all the \(E_{ij}\) are isomorphic as graphs, \(1\leq i\leq k\). Let \(U_k(n)\) denote the largest value \(U(G)\) can take with G as above. The authors and other earlier showed [Congr. Numerantium 23, 3-18 (1979; Zbl 0434.05046)] that \(U_2(n)=2n/3+o()\) as \(n\to\infty\). Here they show \(U_k(n)=3n/4+o(n)\) for any fixed \(k\geq 3\), as \(n\to\infty\). The difficult part of the proof is the establishment of the upper bound. Broadly speaking, it is done by successively removing subgraphs which are shown to be common to all the \(G_i\), where the subgraph removed at any state depends on the number of edges in the \(G_i\).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3771650
zbMATH Keywords: factorization
zbMATH Keywords: partition of edge set
reviewed by: Nicholas Wormald
MaRDI profile type: Publication
cites work: Q3097395
cites work: Q3872501
cites work: Graph 2-isomorphism is NP-complete
full work available at URL: https://doi.org/10.1007/bf02579173
OpenAlex ID: W2150278998
description: scientific article; zbMATH DE number 3771650