Labelling Hamiltonian cycles of the Johnson graph (Q2875905)

Let \(X_n=\{1,2,\dots,n\}\) and \(r<n\). The Johnson graph \(J(n,r)\) is the graph whose vertices are the \(r\)-subsets of \(X_n\) with two sets being adjacent if they intersect in \(r-1\) elements. For a non-negative integer \(g<n\), a partition of an \((n-g)\)-subset of \(X_n\) is called a partition of \(X_n\) with gap \(g\). A subset \(A\) of \(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 \(\pi\) of \(X_n\) with gap \(g\) has type \(\tau=d_1^{\mu_1}d_2^{\mu_2}\dots d_k^{\mu_k}\) if \(\pi\) has \(\mu_i\) classes of size \(d_i\), where \(d_1>d_2>\dots>d_k\) and \(\sum_{i=1}^kd_i\mu_i=n-g\). The number \(r=\sum_{i=1}^k\mu_i\) of classes of \(\tau\) is its weight. A partition \(\gamma\) 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 both orthogonal to \(\gamma\). A cycle \(\mathcal{H}\) in \(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 of \(\mathcal{H}\) are distinct. A partition type \(\tau\) of weight \(r\) defined on \(X_n\) is said to be flexible if every Hamiltonian cycle of \(J(n,r)\) can be \(\tau\)-labeled.NEWLINENEWLINENEWLINE The paper under review characterizes all the partition types \(\tau\) of weight \(r\) defined on \(X_n\) which are flexible.NEWLINENEWLINEA partition type is non-trivial if it has at least one non-singleton class. Let \(n\geqslant3\) and let \(\tau\) be a non-trivial partition type defined on \(X_n\) with a non-zero gap \(g\) and weight \(r\geqslant1\). It is shown in the paper that if \(\tau\) has at least one class of size greater than two, then \(\tau\) is flexible unless \(g=1\) and \(\tau\) is one of the forms \(3 2^2\) or \(3^2 1^t\;(t\geqslant0)\). Moreover, if the classes of \(\tau\) are of sizes at most two, then \(\tau\) is flexible unless it is one of the forms \(2^2 1^t\;(t\geqslant0, g\geqslant1)\) or \(2^3 1^t\;(t\geqslant0, g\geqslant1)\) or \(2^4\;(g=1,2,3,4)\) or \(2^4 1\;(g=1,2)\) or \(2^4 1^2\;(g=1)\) or \(2^5\;(g=1,2,3)\) or \(2^6\;(g=1)\).NEWLINENEWLINEFurthermore, the paper deals with the flexibility of a partition in the zero gap case: Let \(r\geqslant4\) and \(t\geqslant1\). The partition type \(2^r 1^t\) with zero gap is flexible unless it is one of the forms \(2^4 1^t\;(t=1,2,3,4)\) or \(2^5 1^t\;(t=1,2)\) or \(2^6 1\). Moreover, the partition type \(2^r 1^t\) with zero gap is flexible when \(r\geqslant4\), \(t\geqslant1\) and \(2r+t\geqslant14\). Furthermore, the partition type \(3^2 2 1^t\) with zero gap is flexible if \(t\geqslant2\).