Decompositions of Complete Bipartite Graphs and Complete Graphs Into Paths, Stars, and Cycles with Four Edges Each

Abstract

Let G be either a complete graph of odd order or a complete bipartite graph in which each vertex partition has an even number of vertices. In this paper, we determine the set of triples (p, q, r), with p, q, r > 0, for which there exists a decomposition of G into p paths, q stars, and r cycles, each of which has 4 edges.

Keywords

• complete graph
• complete bipartite graph
• path
• star
• cycle
• decomposition
• 05c38
• 05c51