Uniform {<i>C</i>_h,<i>S</i>(<i>C</i>_h)}-Factorizations of <i>K</i>_n−<i>I</i> for Even <i>h</i>

Abstract

Let H be a connected subgraph of a graph G. An H-factor of G is a spanning subgraph of G whose components are isomorphic to H. Given a set H of mutually non-isomorphic graphs, a uniform H-factorization of G is a partition of the edges of G into H-factors for some H∈H. In this article, we give a complete solution to the existence problem of uniform H-factorizations of Kn−I (the graph obtained by removing a 1-factor from the complete graph Kn) for H={Ch,S(Ch)}, where Ch is a cycle of length an even integer h≥4 and S(Ch) is the graph consisting of the cycle Ch with a pendant edge attached to each vertex.

Keywords

• graph decompostion
• factor
• uniform factorization