# Unions of graphs

### From G-designs

Relevant articles: _{[1]},
_{[2]},
_{[3]},
_{[4]},
_{[5]},
_{[6]},
_{[7]},
_{[8]},
_{[9]},
_{[10]},
_{[11]},
_{[12]},
_{[13]},
_{[14]},
_{[15]},
_{[16]},
_{[17]},
_{[18]},
_{[19]}.

## Contents[hide] |

# Unions of graphs

In this section we consider the existence of -designs for cases where
is the union of pairwise vertex-disjoint graphs, or graphs intersecting
in only one vertex. Many such results can be obtained indirectly via
solutions to other related problems, and yield only a few scattered
existence results on the spectrum problem. A description and summary of
all such results would be very lengthy, full of partial results, and
not really in line with the focus of this website.

The survey article 'A Survey on the Existence of -Designs' by Adams, Bryant and Buchanan _{[6]} briefly discuss a few examples to indicate the types of results that can be obtained in this manner.

## Spectrum Results

An explanation of the sources of most of the follwoing results is given in _{[6]}, and the remainder is a correction to an error in _{[6]} as discussed below.

There is an error in the -design of order given in Example A.28 in the Appendix of _{[6]}. Instead, let consist of the orbit of under the permutation . Then is a -design of order .

**Theorem 1**

*Denote by the graph consisting of two copies of sharing a vertex. There exists a -design of order if and only if there exists a -design of order and is even.*

Combining Theorem 1 with the results given in Table 1 in the section on Complete Graphs we have a complete solution to the spectrum problem for when , see Table 1 below.

**Table 1**

Spectrum for | Possible exceptions | |

**Theorem 2**

*Denote by the graph consisting of vertex disjoint copies of . If there exists a -design of order and then there exists a design of order .*

We can use Theorem 2 and some small designs given in _{[6]} to settle the spectrum problem for when and . The cases and are also settled, see the section on matchings or the section on small graphs for and the section on even graphs for . We summarise these results in Table 2 below.

**Table 2**

Spectrum for | Exceptions | |

## Notes

- Results on the Oberwolfach problem yield -designs of in the case is a -regular graph on vertices. A table of known results on the Oberwolfach problem is given in
_{[10]}. - Various small disconnected graphs and small graphs with cut-vertices which could be mentioned in this section are covered in the section on small graphs.

## References

- ↑ Abel, R. J. R., Ge, G., and Yin, J.
*Resolvable and Near-Resolvable Designs*, CRC Press Series on Discrete Mathematics and its Applications, The CRC handbook of combinatorial designs, ed. 2, CRC Press, 124–132 (2007). - ↑ Adams, P., Ardal, H., Maňuch, Ján., Hòa, V. D., Rosenfeld, M., and Stacho, L.
*Spanning cubic graph designs*, Discrete Math.**309**, 5781–5788 (2009). - ↑ Adams, P. and Bryant, D.
*Two-factorisations of complete graphs of orders fifteen and seventeen*, Australas. J. Combin.**35**, 113–118 (2006). - ↑ Adams, P., Bryant, D. E., and Khodkar, A.
*Uniform 3-factorisations of K_10*, Proceedings of the Twenty-eighth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1997), 23–32 (1997). - ↑ Adams, P., Bryant, D., and Maenhaut, B.
*Cube factorizations of complete graphs*, J. Combin. Des.**12**, 381–388 (2004). - ↑
^{6.0}^{6.1}^{6.2}^{6.3}^{6.4}^{6.5}Adams, P., Bryant, D., and Buchanan, M.*A survey on the existence of G-designs*, J. Combin. Des.**16**, 373–410 (2008). - ↑ Alspach, B., Schellenberg, P. J., Stinson, D. R., and Wagner, D.
*The Oberwolfach problem and factors of uniform odd length cycles*, J. Combin. Theory Ser. A,**52**, 20–43 (1989). - ↑ Bermond, J. -C., Heinrich, K., and Yu, M.
*Existence of resolvable path designs*, European J. Combin.**11**, 205–211 (1990). - ↑ Bryant, D. and El-Zanati, S.
*Graph decompositions*, CRC Press Series on Discrete Mathematics and its Applications, The CRC handbook of combinatorial designs, ed. 2, CRC Press, 477–486 (2007). - ↑
^{10.0}^{10.1}Bryant, D. and Rodger, C. A.*Cycle decompositions*, CRC Press Series on Discrete Mathematics and its Applications, The CRC handbook of combinatorial designs, ed. 2, CRC Press, 373–382 (2007). - ↑ Colbourn, C. J., Stinson, D. R., and Zhu, L.
*More frames with block size four*, J. Combin. Math. Combin. Comput.**23**, 3–19 (1997). - ↑ Hajnal, A. and Szemerédi, E.
*Proof of a conjecture of P. Erdös*, Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), North-Holland, Amsterdam, 601–623 (1970). - ↑ Hanani, H., Ray-Chaudhuri, D. K., and Wilson, R. M.
*On resolvable designs*, Discrete Math.**3**, 343–357 (1972). - ↑ Horák, P. and Rosa, A.
*Decomposing Steiner triple systems into small configurations*, Ars Combin.**26**, 91–105 (1988). - ↑ Huang, C.
*Resolvable balanced bipartite designs*, Discrete Math.**14**, 319–335 (1976). - ↑ Lonc, Z.
*On resolvable tree-decompositions of complete graphs*, J. Graph Theory,**12**, 295–303 (1988). - ↑ Ray-Chaudhuri, D. K. and Wilson, R. M.
*Solution of Kirkman's schoolgirl problem*, Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968), Amer. Math. Soc. Providence, R.I. 187–203 (1971). - ↑ Yu, M.
*On tree factorizations of K_n*, J. Graph Theory,**17**, 713–725 (1993). - ↑ Yu, M.
*Almost resolvable P_k-decompositions of complete graphs*, J. Graph Theory,**15**, 523–541 (1991).