## Abstract

In this paper, we give some necessary and sufficient conditions for decomposing the complete bipartite digraphs DK_{m,n} and complete digraphs DK_{n} into directed paths P→k+1 and directed cycles C→k with k arcs each. In particular, we prove that: (1) For any nonnegative integers p and q; and any positive integers m, n, and k with m≥k and n≥k; a decomposition of DK_{m,n} into p copies of P→k+1 and q copies of (Formula presented.) exists if and only if k(p+q)=2mn, p≠1, (m,n,k,p)≠(2,2,2,3), and k is even when q>0. (2) For any nonnegative integers p and q and any positive integers n and k with k even and(Formula presented.), a decomposition of (Formula presented.) and q copies of (Formula presented.) exists if and only if k(p+q)=n(n-1) and p≠1. We also give necessary and sufficient conditions for such decompositions to exist when k=2 or 4.

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

Pages (from-to) | 1715-1725 |

Number of pages | 11 |

Journal | Graphs and Combinatorics |

Volume | 31 |

Issue number | 5 |

DOIs | |

Publication status | Published - 2015 Sep 24 |

Externally published | Yes |

## Keywords

- Complete bipartite digraph
- Complete digraph
- Decomposition
- Directed cycle
- Directed path

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics