TY - JOUR

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

AU - Shyu, Tay Woei

N1 - Funding Information:
This work was supported by the National Science Council of ROC (NSC 100-2115-M-003-013).
Publisher Copyright:
© 2014, Springer Japan.

PY - 2015/9/24

Y1 - 2015/9/24

N2 - 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.

AB - 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.

KW - Complete bipartite digraph

KW - Complete digraph

KW - Decomposition

KW - Directed cycle

KW - Directed path

UR - http://www.scopus.com/inward/record.url?scp=84939775281&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84939775281&partnerID=8YFLogxK

U2 - 10.1007/s00373-014-1442-0

DO - 10.1007/s00373-014-1442-0

M3 - Article

AN - SCOPUS:84939775281

VL - 31

SP - 1715

EP - 1725

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

SN - 0911-0119

IS - 5

ER -