We extend results concerning orthogonal edge labeling of constant weight Gray codes. For positive integers \(n\) and \(r\) with \(n > r\), let \(G_{n,r}\) be the graph whose vertices are the \(r\)-sets of \(\{1, \ldots, n\}\), with \(r\)-sets adjacent if they intersect in \(r-1\) elements. The graph \(G_{n,r}\) is Hamiltonian; Hamiltonian cycles of \(G_{n,r}\) are early examples of error-correcting codes, where they came to be known as constant weight Gray codes.
An \(r\)-set \(A\) and a partition \(\pi\) of weight \(r\) are said to be orthogonal if every block of \(\pi\) meets \(A\) in exactly one element. Given a class \(P\) of weight \(r\) partitions of \(X_n\), one would like to know if there exists a \(G_{n,r}\) Hamiltonian cycle \(A_1 A_2 \ldots A_{\binom{n}{r}}\) whose edges admit a labeling \(A_1\pi_1 A_2 \ldots A_{\binom{n}{r}}\pi_{\binom{n}{r}}\) by distinct partitions from \(\mathcal{P}\), such that a partition label of an edge is orthogonal to the vertices that comprise the edge. The answer provides non-trivial information about Hamiltonian cycles in \(G_{n,r}\) and has application to questions pertaining to the efficient generation of finite semigroups.
Let \(r\) be a partition of \(m\) as a sum of \(r\) positive integers. We let \(r\) also refer to the set of all partitions of \(X_n\) whose block sizes comprise the partition \(r\). J. Lehel and the first author have conjectured that for \(n \geq 6\) and partition type \(\pi\) of \(\{1, \ldots, n\}\) of weight \(r\) partitions, there exists a \(r\)-labeled Hamiltonian cycle in \(G_{n,r}\).
In the present paper, for \(n = s + r\), we prove that there exist Hamiltonian cycles in \(G_{n,r}\) which admit orthogonal labelings by the partition types which have \(s\) blocks of size two and \(r – s\) blocks of size one, thereby extending a result of J. Lehel and the first author and completing the work on the conjecture for all partition types with blocks of size at most two.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.