Graphs which are both H_1 and H_2-decomposable

Barbara Maenhaut
Open University


A graph G is said to be H-decomposable if there exists a collection of subgraphs of G, each isomorphic to H, which partition the edge set of G. If G is H-decomposable, we say that H|G. Given two graphs H_1 and H_2, for which values q does there exist a graph G having q edges such that H_1|G and H_2|G? The problem will be considered for the cases when H_1 and H_2 are both cycles and when H_1 and H_2 are both complete graphs.