Labeling Hamiltonian Cycles of the Johnson Graph

Abstract

A non-empty \( r \)-element subset \( A \) of an \( n \)-element set \( X_n \), and a partition \( \pi \) of \( X_n \), are said to be orthogonal if every class of \( \pi \) meets \( A \) in exactly one element. A partition type is determined by the number of classes of each distinct size of the partition. The Johnson graph \( J(n,r) \) is the graph whose vertices are the \( r \)-element subsets of \( X_n \), with two sets being adjacent if they intersect in \( r-1 \) elements. A partition of a given type \( \tau \) is said to be a \( \tau \)-label for an edge \( AB \) in \( J(n,r) \) if the sets \( A \) and \( B \) are orthogonal to the partition. A cycle \( \mathcal{H} \) in the graph \( J(n,r) \) is said to be \( \tau \)-labeled if for every edge of \( \mathcal{H} \), there exists a \( \tau \)-label, and the \( \tau \)-labels associated with distinct edges are distinct. Labeled Hamiltonian cycles are used to produce minimal generating sets for transformation semigroups. We identify a large class of partition types \( \tau \) with a non-zero gap for which every Hamiltonian cycle in the graph \( J(n,r) \) can be \( \tau \)-labeled, showing, for example, that this class includes all the partition types with at least one class of size larger than 3 or at least three classes of size 3.