Authors:
Z.-C. Chen, H.-C. Lee
Title:
Decomposing the complete graph into Hamiltonian paths (cycles) and 3-stars
Source:
Discussiones Mathematicae Graph Theory
Received 12.01.2018, Revised 14.05.2018, Accepted 14.05.2018, doi: 10.7151/dmgt.2153

Abstract:
Let H be a graph. A decomposition of H is a set of edge-disjoint subgraphs of H whose union is H. A Hamiltonian path (respectively, cycle) of H is a path (respectively, cycle) {that} contains every vertex of H exactly once. A k-star, denoted by Sk, is a star with k edges. In this paper, we give necessary and sufficient conditions for decomposing the complete graph into α copies of Hamiltonian path (cycle) and β copies of S3.
Keywords:
decomposition, complete graph, Hamiltonian path, Hamiltonian cycle, star

Links:
PDF