Terminal-pairability in complete graphs

MaRDI QIDQ3119338zbMATH OpenFDO

Authors Tamás Róbert Mezei, Gábor Mészáros, Ervin Győri

Publication date 11 March 2019

Full work available at URL https://arxiv.org/abs/1605.05857

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Communication networks in operations research (90B18)

Abstract: We investigate terminal-pairability properties of complete graphs and improve the known bounds in two open problems. We prove that the complete graph $K_n$ on $n$ vertices is terminal-pairable if the maximum degree $Delta$ of the corresponding demand graph $D$ is at most $2lfloorfracn6floor-2$. We also verify the terminal-pairability property when the number of edges in $D$ does not exceed $2n-5$ and $Deltaleqn-1$ holds.

Recommendations

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

Cited in

(8)

• Terminal-pairability in complete bipartite graphs
• On path-pairability of the finite grids
• Note on the bisection width of cubic graphs
• Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs
• Minimal 2-connected graphs satisfying the even cut condition
• The terminal-pairability problem in complete bipartite graphs
• Note on terminal-pairability in complete grid graphs
• An improved upper bound on the maximum degree of terminal-pairable complete graphs

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

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