Terminal-pairability in complete bipartite graphs

DOI10.1016/J.DAM.2017.10.026MaRDI QIDQ1693175zbMATH OpenOpenAlexFDO

Authors Lucas Colucci, Tamás Róbert Mezei, Péter L. Erdős, Ervin Győri

Publication date 11 January 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.04313, http://real.mtak.hu/71043/1/1702.04313v2.pdf

zbMATH Keywords

complete bipartite graphsterminal-pairability

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Graph theory (05C99)

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.

Recommendations

• The terminal-pairability problem in complete bipartite graphs
• Terminal-pairability in complete graphs
• Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs
• An improved upper bound on the maximum degree of terminal-pairable complete graphs
• Note on terminal-pairability in complete grid graphs

Cites work

• scientific article; zbMATH DE number 1523257 (Why is no real title available?)
• scientific article; zbMATH DE number 3266380 (Why is no real title available?)
• A communication problem and directed triple systems
• A sufficient condition for graphs to be weakly \(k\)-linked
• Graph theory
• Networks communicating for each pairing of terminals
• Note on terminal-pairability in complete grid graphs

Cited in

(6)

• Terminal-pairability in complete graphs
• On the termination of some biclique operators on multipartite graphs
• Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs
• The terminal-pairability problem in complete bipartite graphs
• An improved upper bound on the maximum degree of terminal-pairable complete graphs
• Note on terminal-pairability in complete grid graphs

This page was built for publication: Terminal-pairability in complete bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1693175)