Discussiones Mathematicae Graph Theory (Feb 2022)
Minimum Coverings of Crowns with Cycles and Stars
Abstract
Let F, G and H be graphs. A (G, H)-decomposition of F is a partition of the edge set of F into copies of G and copies of H with at least one copy of G and at least one copy of H. For R ⊆ F, a (G, H)-covering of F with padding R is a (G, H)-decomposition of F + E(R). A (G, H)-covering of F with the smallest cardinality is a minimum (G, H)-covering. This paper gives the solution of finding the minimum (Ck, Sk)-covering of the crown Cn,n−1.
Keywords