Back to Search Start Over

Terminal-Pairability in Complete Bipartite Graphs

Authors :
Colucci, Lucas
Erdős, Péter L.
Győri, Ervin
Mezei, Tamás Róbert
Source :
Discrete Applied Mathematics, Volume 236, 19 February 2018, Pages 459-463
Publication Year :
2017

Abstract

We investigate the terminal-pairibility problem in the case when the base graph is a complete bipartite graph, and the demand graph is also bipartite with the same color classes. We improve the lower bound on maximum value of $\Delta(D)$ which still guarantees that the demand graph $D$ is terminal-pairable in this setting. We also prove a sharp theorem on the maximum number of edges such a demand graph can have.<br />Comment: 8 pages, several typos corrected

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Journal :
Discrete Applied Mathematics, Volume 236, 19 February 2018, Pages 459-463
Publication Type :
Report
Accession number :
edsarx.1702.04313
Document Type :
Working Paper
Full Text :
https://doi.org/10.1016/j.dam.2017.10.026