Terminal-Pairability in Complete Graphs

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 multigraph $D$ is at most $2\lfloor\frac{n}{6}\rfloor-4$. We also verify the terminal-pairability property when the number of edges in $D$ does not exceed $2n-5$ and $\Delta\leq n-1$ holds.

Publication
Journal of Combinatorial Mathematics and Combinatorial Computing

Dedicated to the memory of our friend, professor Ralph Faudree.

Submitted in October, 2016. Appeared in the November 2018 issue of JCMCC (see the Table of Contents.)