Path-Pairable Graphs

Abstract

A graph of even order is called path-pairable if, for any pairing of its vertices, there exist edge-disjoint paths connecting the paired vertices. Extremal problems for path-pairable graphs with restrictions on the maximum degree will be considered. In particular, let $f(n,k)$ denote the minimum number of edges in a path-pairable graph of order $n$ and maximum degree $k$. Exact values of $f(n,k)$ are determined for $k=n-1,n-2,$ and $n-3$.