Orthogonal Labellings of Caterpillars of Small Diameter

Abstract

An orthogonal double cover ( ODC) <;; of the complete graph K,. is a collection of n spanning subgraphs G 1 , G2 , . .. , G,. of K,. such that - every edge of K,. belongs to exactly two of the G,' s and - every pair of G,' s intersect in exactly one edge. If G, ~ G for all i E {l, 2, . .. , n}, then <;; is an ODC of K,. by C. An ODC of K,. is cyclic if the cyclic group of order n is a subgroup of its automorphism group. In this paper, we obtain cyclic ODCs of K,. by caterpillars of small diameter.