The unilateral 2-linkage problem

arXiv:2610.36895 · math.CO · Submitted 2026-10-27 · Read on arXiv

math.CO

Submitted: 2026-10-27

Updated: 2026-10-27

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

The gist: We study a new variant of the classical linkage problem for digraphs, which we call unilateral linkages.

Abstract

We study a new variant of the classical linkage problem for digraphs, which we call unilateral linkages. A digraph D is unilaterally k-linked if it satisfies that for every choice of 2k distinct vertices s 1,s 2,,s k,t 1,t 2,,t k there are vertex disjoint directed paths P 1,,P k in D such that P i is either an (s i,t i) -path or a (t i,s i) -path for each i in [k]. This is a relaxation of the property of D being k-linked, where we insist that each P i must go from s i to t i. Clearly every k-linked digraph is also unilaterally k-linked. It is easy to see that the unilateral linkage problem is NP-complete for general digraphs and that it is trivial for semicomplete digraphs (digraphs with no pair of non-adjacent vertices). We show how Thomassen's construction of highly connected digraphs which are not 2-linked can be modified to show that there is no connectivity which guarantees that a digraph is unilaterally 2-linked. We show that every 4-strong split digraph and every 5-strong semicomplete multipartite digraph is unilaterally 2-linked. Both bounds are best possible. A digraph is co-bipartite if its vertex set can be covered by two induced semicomplete digraphs. We prove that every 6-strong co-bipartite digraph is unilaterally 2-linked. Here we do not know whether the correct answer is 5. We also prove that every 16-strong digraph with independence number at most 2 is unilaterally 2-linked.

Related papers