Three-regular path pairable graphs (Q1187948)

A graph \(G\) is \(k\)-path pairable if for any two disjoint sets of vertices \(\{x_ 1,x_ 2,\dots,x_ k\}\) and \(\{y_ 1,y_ 2,\dots,y_ k\}\) of \(G\) there are edge-disjoint paths \(P_ i\), \(1\leq i\leq k\), where \(P_ i\) is a path from \(x_ i\) to \(y_ i\). It is shown that for any positive integer \(k\) and for \(n\) sufficiently large, there is a 3-regular graph on \(n\) vertices that is \(k\)-path pairable. Such a graph can be constructed from a complete binary tree which has a root of degree three. The authors give upper and lower bounds for the minimum number of edges in a \(k\)-path pairable graph of order \(n\) with maximum degree at most 3, in terms of \(n\) and \(k\), for \(n\) sufficiently large.