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

Research output: Contribution to journalArticlepeer-review

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

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Decomposition of Complete Bipartite Digraphs and Complete Digraphs into Directed Paths and Directed Cycles of Fixed Even Length'. Together they form a unique fingerprint.

Cite this