Path Decompositions of the Kneser Graph

Abstract

Necessary and sufficient conditions are given for the existence of a graph decomposition of the Kneser Graph $KG_{n,2}$ into paths of length three and four, and of the Generalized Kneser Graph $GKG_{n,3,1}$ into paths of length three. A solution is also presented for the problem of embedding maximal $H$-designs, where $H$ is a path of length three.