##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 565.05040

**Autor: ** Chung, F.R.K.; Erdös, Paul; Graham, Ronald L.

**Title: ** Minimal decomposition of all graphs with equinumerous vertices and edges into mutually isomorphic subgraphs. (In English)

**Source: ** Finite and infinite sets, 6th Hung. Combin. Colloq., Eger/Hung. 1981, Vol. I, Colloq. Math. Soc. János Bolyai 37, 171-179 (1984).

**Review: ** [For the entire collection see Zbl 559.00001.]

Let *G* = **{**G_{1},G_{2},...,G_{k}**}** be a set of graphs, all of the same size. A U-decomposition of *G* is a set of partitions of the edge sets E_{i} of the G_{i}'s, E_{i} = \cup^{r}_{j = 1}E_{ij} such that for each fixed j = 1,...,r, all the E_{ij}(1 \leq i \leq k) induce isomorphic graphs. Denote by U(*G*) the least value of r any U-decomposition of *G* can have, and by U_{k}(n) the largest value of U(*G*) over all sets *G* of k graphs of order n (and the same size).

It was shown by the authors, *S.M.Ulam*, and *F.F.Yao* [Congr. Numerantium 23, 3-18 (1979; Zbl 434.05046)] that U_{2}(n) = 2/3n+o(n), and by the authors [Combinatorica 1, 13-24 (1981; Zbl 491.05049)] that U_{k}(n) = 3/4n+o(n) for any fixed k \geq 3.

In the present paper, the family *G* = *G*(n,e) of all graphs of order n and size e is investigated. Let U(n) be the maximum value of U(*G*(n,e)) over all values of e; clearly U_{k}(n) \leq U(n). The main result states that U(n) = 3/4n+o(1); in particular, U(*G*(n,e)) = o(n) if n/e = o(1).

**Reviewer: ** J.Sirán

**Classif.: ** * 05C35 Extremal problems (graph theory)

**Keywords: ** decomposition of edge sets of a collection of graphs; decomposition of graphs into mutually isomorphic subgraphs

**Citations: ** Zbl 559.00001; Zbl 434.05046; Zbl 491.05049

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag