Opuscula Mathematica
Opuscula Math. 37, no. 4 (2017), 589-595

Toward Wojda's conjecture on digraph packing

Jerzy Konarski
Andrzej Żak
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.
Full text (pdf)
References ▼
  1. [1] A. Benhocine, H.J. Veldman, A.P. Wojda, Packing of digraphs, Ars Combin. 22 (1986), 43-49.
  2. [2] E. Györi, A. Kostochka, A. McConvey, D. Yager, Toward Żak's conjecture on graph packing, J. Combin. 7 (2016) 2, 307-340.
  3. [3] A.P. Wojda, Research problems (Problem 69), Discrete Math. 57 (1985), 209-210.
  4. [4] A.P. Wojda, M. Woźniak, Packing and extremal digraphs, Ars Combin. 20 B (1985), 71-73.
About the authors ▼
Jerzy Konarski
AGH University of Science and Technology, Faculty of Applied Mathematics, al. A. Mickiewicza 30, 30-059 Krakow, Poland
Andrzej Żak
AGH University of Science and Technology, Faculty of Applied Mathematics, al. A. Mickiewicza 30, 30-059 Krakow, Poland
About the article ▼
Communicated by Gyula O.H. Katona.
Received: 2016-07-22.
Revised: 2016-11-14.
Accepted: 2016-11-15.
Published online: 2017-04-28.
Cite this article as ▼
Jerzy Konarski, Andrzej Żak, Toward Wojda's conjecture on digraph packing, Opuscula Math. 37, no. 4 (2017), 589-595, http://dx.doi.org/10.7494/OpMath.2017.37.4.589.
Download this article's citation as: