Minimal decompositions of graphs into mutually isomorphic subgraphs (Q1167190): Difference between revisions
From MaRDI portal
Removed claims |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Fan R. K. Chung / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Ronald L. Graham / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Nicholas C. Wormald / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3097395 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3872501 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph 2-isomorphism is NP-complete / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf02579173 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2150278998 / rank | |||
Normal rank |
Latest revision as of 10:13, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimal decompositions of graphs into mutually isomorphic subgraphs |
scientific article |
Statements
Minimal decompositions of graphs into mutually isomorphic subgraphs (English)
0 references
1981
0 references
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\).
0 references
factorization
0 references
partition of edge set
0 references