In this paper we prove that there are either 2k-2 or 2k-1 pairwise compatible Hamilton path decompositions of K-2k. In the case of K-4, there exactly 2 compatible Hamilton path decompositions. We also find (different) lower bounds on the number of pairwise compatible Hamilton decompositions of K4m+1 and K4m+3. (C) 1997 Academic Press.
展开▼