Toward Wojda's conjecture on digraph packing
Author(s) -
Jerzy Konarski,
Andrzej Żak
Publication year - 2017
Publication title -
opuscula mathematica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.481
H-Index - 16
eISSN - 2300-6919
pISSN - 1232-9274
DOI - 10.7494/opmath.2017.37.4.589
Subject(s) - digraph , mathematics , conjecture , combinatorics
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\)
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom