Exact embedding of two G-designs into a (G plus e)-design

Let G be a connected simple graph and let S-G be the spectrum of integers v for which there exists a G-design of order v. Put e = {x, y}, with x epsilon V(G) and y is not an element of V(G). Denote by G + e the graph having vertex set V(G) U [y] and edge set E(G) U {e}. Let (X. D) be a (G + e)-design. We say that two G-designs (V-f, B-i), i = 1, 2, are exactly embedded into (X, D) if X = V-1 boolean OR V-2. [V-1 boolean AND V-2] = 0 and there is a bijective mapping f : B-1 U B-2 -> D such that B is a subgraph of f(B), for every B epsilon B-1 U B-2. We give necessary and sufficient conditions so that two G-designs can be exactly embedded into a (G + e)-design. We also consider the following two problems: (1) determine the pairs {v(1), v(2)) subset of S-G for which any two nontrivial G-designs (V-i, B-i), [V-i] = vi, i = 1, 2, can be exactly embedded into a (G + e)-design; (2) determine the pairs {v(1), v(2)) subset of S-G for which there exists a (G + e)-design of order v(1) + v(2) exactly embedding two nontrivial G-designs (V-i, B-i), [V-i] = v(i), i = 1, 2. We study these problems for BIBDs, cycle systems, cube systems, path designs and star designs. (C) 2011 Elsevier B.V. All rights reserved.