Two Hamilton cycles in bipartite reflective Kneser graphs (Q1112063)

For integers i, j with \(0<i<j\), let \(RG_{ij}\) be the bipartite graph the vertex-classes \(V_ 1\) and \(V_ 2\) of which are the \((i+j)\)-tuples over \(\{\) 0,1\(\}\) of Hamming weight i and j, respectively, and \((a_ 1,...,a_{i+j})\in V_ 1\), \((b_ 1,...,b_{i+j})\in V_ 2\) are adjacent iff \(a_ k=1\) implies \(b_ k=1\), \(k=1,...,i+j\). According to a conjecture due to \textit{I. Havel} [Graphs and other combinatorial topics, Proc. 3rd Czech. Symp., Prague 1982, Teubner-Texte Math. 59, 101-108 (1983; Zbl 0528.05030)] concerning such graphs \(RG_{ij}\) the authors verify the graphs \(RG_{9,10}\) and \(RG_{7,9}\) to be Hamiltonian. The Hamilton cycles are constructed by considering group actions on graphs and their quotient graphs.