Opuscula Math. 37, no. 4 (2017), 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.
- A. Benhocine, H.J. Veldman, A.P. Wojda, Packing of digraphs, Ars Combin. 22 (1986), 43-49.
- E. Györi, A. Kostochka, A. McConvey, D. Yager, Toward Żak's conjecture on graph packing, J. Combin. 7 (2016) 2, 307-340.
- A.P. Wojda, Research problems (Problem 69), Discrete Math. 57 (1985), 209-210.
- A.P. Wojda, M. Woźniak, Packing and extremal digraphs, Ars Combin. 20 B (1985), 71-73.
- 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
- Communicated by Gyula O.H. Katona.
- Received: 2016-07-22.
- Revised: 2016-11-14.
- Accepted: 2016-11-15.
- Published online: 2017-04-28.
