Decomposition of Complete Bipartite Digraphs and Complete Digraphs into Directed Paths and Directed Cycles of Fixed Even Length

Research output: Contribution to journalArticle

Abstract

In this paper, we give some necessary and sufficient conditions for decomposing the complete bipartite digraphs DKm,n and complete digraphs DKn 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 DKm,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 languageEnglish
Pages (from-to)1715-1725
Number of pages11
JournalGraphs and Combinatorics
Volume31
Issue number5
DOIs
Publication statusPublished - 2015 Sep 24
Externally publishedYes

    Fingerprint

Keywords

  • Complete bipartite digraph
  • Complete digraph
  • Decomposition
  • Directed cycle
  • Directed path

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Cite this