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

被引：0
作者：
Colucci, Lucas [2 ]
Erdos, Peter L. [1 ]
Gyori, Ervin [1 ,2 ]
Mezei, Tamas Robert [1 ,2 ]
机构：
[1] Hungarian Acad Sci, Alfred Renyi Inst Math, Realtanoda U 13-15, H-1053 Budapest, Hungary
[2] Cent European Univ, Dept Math & Its Applicat, Nador U 9, H-1051 Budapest, Hungary
来源：
THEORETICAL COMPUTER SCIENCE | 2019年 / 775卷
关键词：
Edge-disjoint paths; Terminal-pairability; Complete bipartite graph;
D O I：
10.1016/j.tcs.2018.12.007
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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.
引用
收藏
页码：16 / 25
页数：10
相关论文
共 34 条
  • [11] A MINIMUM DEGREE CONDITION FORCING COMPLETE GRAPH IMMERSION
    DeVos, Matt
    Dvorak, Zdenek
    Fox, Jacob
    McDonald, Jessica
    Mohar, Bojan
    Scheide, Diego
    [J]. COMBINATORICA, 2014, 34 (03) : 279 - 298
  • [12] Diestel R., 2010, Graduate Text in Mathematics, V4th
  • [13] Even S., 1976, SIAM Journal on Computing, V5, P691, DOI 10.1137/0205048
  • [14] FAUDREE R., 1992, Congressus Numerantium, V88, P111
  • [15] FAUDREE R.J., 1999, Journal of Combinatorial Mathematics and Combinatorial Computing, V20, P145
  • [16] 3-REGULAR PATH PAIRABLE GRAPHS
    FAUDREE, RJ
    GYARFAS, A
    LEHEL, J
    [J]. GRAPHS AND COMBINATORICS, 1992, 8 (01) : 45 - 52
  • [17] ON WELL-PARTIAL-ORDER THEORY AND ITS APPLICATION TO COMBINATORIAL PROBLEMS OF VLSI DESIGN
    FELLOWS, MR
    LANGSTON, MA
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (01) : 117 - 126
  • [18] ON SEARCH, DECISION, AND THE EFFICIENCY OF POLYNOMIAL-TIME ALGORITHMS
    FELLOWS, MR
    LANGSTON, MA
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 49 (03) : 769 - 779
  • [19] An improved upper bound on the maximum degree of terminal-pairable complete graphs
    Girao, Antonio
    Meszaros, Gabor
    [J]. DISCRETE MATHEMATICS, 2018, 341 (09) : 2606 - 2607
  • [20] A communication problem and directed triple systems
    Gyarfas, A
    Schelp, RH
    [J]. DISCRETE APPLIED MATHEMATICS, 1998, 85 (02) : 139 - 147
1234