Publications of (and about) Paul Erdös
Autor: Chung, F.R.K.; Erdös, Paul; Graham, Ronald L.; Ulam, S.M.; Yao, F.F.
Title: Minimal decompositions of two graphs into pairwise isomorphic subgraphs. (In English)
Source: Proc. 10th southeast. Conf. Combinatorics, graph theory and computing, Boca Raton 1979, Vol. I, Congr. Numerantium 23, 3-18 (1979).
Review: [For the entire collection see Zbl 418.00002.]
The basic concept of this paper is that of a U-decomposition. Suppose the edge sets of two graphs G and G' can be partitioned into sets E1+...+Er and E'1+...+E'r in such a way that the subgraphs defined by Ei and E'i are isomorphic for i = 1,2,...,r. Then this pair of partitions is a U-decomposition of the pair of graphs. U(G,G') is defined to be the minimum value of r for which a U-decomposition exists. The paper considers many properties of U(G,G') and of U(n') defined as max U(G,G') where ''max'' ranges over all pairs (G,G') of graphs with n vertices. The main result of the paper is that U(n) = 2n/3+0(n).
Classif.: * 05C35 Extremal problems (graph theory)
Keywords: isomorphism; edge-chromatic number; edge-dominating number; decomposition
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag