ALGORITHMS FOR LABELING CONSTANT WEIGHT GRAY CODES
Let \(G_{n,r}=(V_r,E_r)\) be the graph where \(V_r\) is the set of all \(r\)-subsets of \(X_n=\{1,\ldots,n\}\) and \(E_r\) consists of those pairs of vertices that correspond to subsets with intersection of cardinality \(r-1\). A Hamiltonian cycle in \(G_{n,r}\) exists always and is referred to as \((n,r)\)-Gray code. An \(r\)-set \(A\subseteq X_n\) and a weight-\(r\) partition \(\pi\) are said to be orthogonal if \(A\) is a transversal of \(\pi\), i.e. every class of \(\pi\) contains a single element of \(A\). Let \({\mathcal C}=A_1\ldots A_{{n\choose r}}\) be a list of the distinct \(r\)-sets of \(X_n\). \({\mathcal C}\) is said to be orthogonally labeled if there eixsts a list of distinct weight-\(r\) permutations \(\pi_1\ldots\pi_{{n\choose r}}\) of \(X_n\) such that the partition \(\pi_i\) is orthogonal to both \(A_i\) and \(A_{i+1}\) for \(1\leq i\leq{n\choose r}\). When \({\mathcal C}\) is a Hamiltonian cycle in \(G_{n,r}\) it is said be an orthogonally labeled Hamiltonian cycle. The main results of the paper are contained in the following theorems: Theorem 1.4. For positive integers \(n\) and \(r\) with \(1< r< n\), every Hamiltonian cycle in \(G_{n,r}\) admits an orthogonal labeling by weight \(r\) partitions. Theorem 1.5. Let \(n\) and \(r\) be positive integers with \(1<r<n\). On input \((n,r)\), we can output an orthogonally labeled Hamiltonian cycle in \(G_{n,r}\) in \(dn{n\choose r}\) time, where \(d\) is a constant independent of \(n\) and \(r\). Theorem 1.6. Let \(n\) and \(r\) be positive integers with \(1<r<n\). There exists an orthogonally labeled Hamiltonian cycle \(A\pi_1 A_2\pi_2\ldots A_{{n\choose r}}\pi_{{n\choose r}}\) in \(G_{n,r}\) such that \(\pi_1\pi_2\ldots\pi_{{n\choose r}}\) is a cycle in \(Part_{n,r}\). The paper concludes with a discussion on the connections between orthogonally labeled Hamiltonian cycles and generating sets of certain finite semigroups.
- Constructive techniques for labeling constant weight Gray codes with applications to minimal generating sets of semigroups
- Counting techniques to label constant weight Gray codes with links to minimal generating sets of semigroups
- Labelling Hamiltonian cycles of the Johnson graph
- Permutational labelling of constant weight Gray codes
- Constructing edge-labellings of K_n with constant-length Hamilton cycles
- scientific article; zbMATH DE number 706769 (Why is no real title available?)
- scientific article; zbMATH DE number 2192090 (Why is no real title available?)
This page was built for publication: ALGORITHMS FOR LABELING CONSTANT WEIGHT GRAY CODES
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5697636)
