Sums and differences along Hamiltonian cycles (Q5900544): Difference between revisions

Let \(G\) be a finite abelian group, and let \(\mathcal{C}(G)\) be the set of all hamiltonian cycles in the complete digraph on the vertex set \(G\). Given a cycle \(C\in\mathcal{C}(G)\), label each arc \((g_1,g_2)\in C\) with the sum \(g_1+g_2\in G\), and let \(S(C)\) be the set of labels of all arcs in \(C\). The author studies the value of the maximum and the minimum of the cardinalities \(|S(C)|\) with \(C\in\mathcal{C}(G)\), and the expected value \({\text{E}}(|S(C)|)\) when \(C\in \mathcal{C}(G)\) is chosen randomly. Analogous problems arise when each arc \((g_1,g_2)\) is labeled with the difference \(g_2-g_1\). The author finds the exact value or establishes tight bounds for these six quantities.