## Abstract

Let P_{k + 1} denote a path of length k and let S_{k + 1} denote a star with k edges. As usual K_{n} denotes the complete graph on n vertices. In this paper we investigate the decomposition of K_{n} into paths and stars, and prove the following results. Theorem A. Let p and q be nonnegative integers and let n be a positive integer. There exists a decomposition of K_{n} into p copies of P_{4} and q copies of S_{4} if and only if n ≥ 6 and 3 (p + q) = fenced(frac(n, 2)). Theorem B. Let p and q be nonnegative integers, let n and k be positive integers such that n ≥ 4 k and k (p + q) = fenced(frac(n, 2)), and let one of the following conditions hold: (1)k is even and p ≥ frac(k, 2),(2)k is odd and p ≥ k. Then there exists a decomposition of K_{n} into p copies of P_{k + 1} and q copies of S_{k + 1}.

Original language | English |
---|---|

Pages (from-to) | 2164-2169 |

Number of pages | 6 |

Journal | Discrete Mathematics |

Volume | 310 |

Issue number | 15-16 |

DOIs | |

Publication status | Published - 2010 Aug 28 |

Externally published | Yes |

## Keywords

- Complete graph
- Decomposition
- Path
- Star

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics