Terminal-pairability in complete bipartite graphs with non-bipartite demands Edge-disjoint paths in complete bipartite graphs

We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is a (not necessarily bipartite) multigraph on the same vertex set. In computer science, this problem is known as the edge-disjoint paths problem. We improve the lower bound on the maximum value of Delta (D) which still guarantees that the demand graph D has a realization in K-n,K-n. We also solve the extremal problem on the number of edges, i.e., we determine the maximum number of edges which guarantees that a demand graph is realizable in K-n,K-n. (C) 2018 Elsevier B.V. All rights reserved.