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.