A note on Frucht diagrams, Boolean graphs and Hamilton cycles (Q685668)

For integers \(0<i<j\) let \(V_ i\) and \(V_ j\) denote the sets of all \(i\)-element respectively \(j\)-element subsets of \(\{1,2, \dots,i+j\}\). The bipartite graph \(RG_{ij}\) has vertex set \(V_ i \cup V_ j\), and \(X \in V_ i\) and \(Y \in V_ j\) are adjacent if \(X \subseteq Y\). I. Hável conjectured that every such graph \(RG_{ij}\) is Hamiltonian. In this note the authors demonstrate the method of constructing Hamiltonian cycles in \(RG_{ij}\) by means of group actions on graphs, and apply it to the graph \(RG_{5,6}\).