Opuscula Math. 37, no. 4 (), 589-595
http://dx.doi.org/10.7494/OpMath.2017.37.4.589
Opuscula Mathematica

# Toward Wojda's conjecture on digraph packing

Abstract. Given a positive integer $$m\leq n/2$$, Wojda conjectured in 1985 that if $$D_1$$ and $$D_2$$ are digraphs of order $$n$$ such that $$|A(D_1)|\leq n-m$$ and $$|A(D_2)|\leq 2n-\lfloor n/m\rfloor-1$$ then $$D_1$$ and $$D_2$$ pack. The cases when $$m=1$$ or $$m = n/2$$ follow from known results. Here we prove the conjecture for $$m\geq\sqrt{8n}+418275$$.
Keywords: packing, digraph, size.
Mathematics Subject Classification: 05C35.