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 = {G1,G2,...,Gk} be a set of graphs, all of the same size. A U-decomposition of G is a set of partitions of the edge sets Ei of the Gi's, Ei = \cuprj = 1Eij such that for each fixed j = 1,...,r, all the Eij(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 Uk(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 U2(n) = 2/3n+o(n), and by the authors [Combinatorica 1, 13-24 (1981; Zbl 491.05049)] that Uk(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 Uk(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