Zentralblatt MATH

Publications of (and about) Paul Erdös
Zbl.No:  434.05046
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).
Reviewer:  R.S.Read
Classif.:  * 05C35 Extremal problems (graph theory)
Keywords:  isomorphism; edge-chromatic number; edge-dominating number; decomposition
Citations:  Zbl.418.00002

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page