Decomposition of the complete bipartite graph with a 1-factor removed into paths and stars

Jenq-Jong Lin, Hung-Chih Lee

Abstract


Let P_k denote a path on k vertices, and let S_k denote a star with k edges. For graphs F, G, and H, a decomposition of F is a set of edge-disjoint subgraphs of F whose union is F. A (G,H)-decomposition of F is a decomposition of F into copies of G and H using at least one of each. In this paper, necessary and sufficient conditions for the existence of the (P_{k+1},S_k)-decomposition of the complete bipartite graph with a 1-factor removed are given.

Keywords


Decomposition; complete bipartite graph; path; star; crown

Full Text:

PDF


DOI: https://doi.org/10.11575/cdm.v13i2.62378

DOI (PDF): https://doi.org/10.11575/cdm.v13i2.62378.g46788

Refbacks

  • There are currently no refbacks.


Contributions to Discrete Mathematics. ISSN: 1715-0868