Paired Many-to-Many 2-Disjoint Path Cover of Johnson Graphs

Given two disjoint vertex-sets [Formula: see text] and [Formula: see text], a paired many-to-many 2-disjoint path cover joining [Formula: see text] and [Formula: see text] is a set of two vertex-disjoint paths with endpoints [Formula: see text] and [Formula: see text], respectively, that cover every vertex of the graph. If a graph has such a cover for any two disjoint vertex-sets [Formula: see text] and [Formula: see text], then it is called paired 2-coverable. It is straightforward that every paired 2-coverable graph is Hamilton-connected, whereas the converse does not hold in general. Alspach [Johnson graphs are Hamilton-connected, Ars Math. Contemp. 6 (2013) 21–23] proved that Johnson graphs [Formula: see text], where [Formula: see text], are Hamilton-connected. In this paper, we prove that Johnson graphs are paired 2-coverable. Moreover, we show that another family of graphs [Formula: see text], constructed from Johnson graphs by Alspach, is also paired 2-coverable.