{"ID":2850034,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.22662","arxiv_id":"2510.22662","title":"Generating pivot Gray codes for spanning trees of complete graphs in constant amortized time","abstract":"We present the first known pivot Gray code for spanning trees of complete graphs, listing all spanning trees such that consecutive trees differ by pivoting a single edge around a vertex. This pivot Gray code thus addresses an open problem posed by Knuth in The Art of Computer Programming, Volume 4 (Exercise 101, Section 7.2.1.6, [Knuth, 2011]), rated at a difficulty level of 46 out of 50, and imposes stricter conditions than existing revolving-door or edge-exchange Gray codes for spanning trees of complete graphs. Our recursive algorithm generates each spanning tree in constant amortized time using $O(n^2)$ space. In addition, we provide a novel proof of Cayley's formula, $n^{n-2}$, for the number of spanning trees in a complete graph, derived from our recursive approach. We extend the algorithm to generate edge-exchange Gray codes for general graphs with $n$ vertices, achieving $O(n^2)$ time per tree using $O(n^2)$ space. For specific graph classes, the algorithm can be optimized to generate edge-exchange Gray codes for spanning trees in constant amortized time per tree for complete bipartite graphs, $O(n)$-amortized time per tree for fan graphs, and $O(n)$-amortized time per tree for wheel graphs, all using $O(n^2)$ space.","short_abstract":"We present the first known pivot Gray code for spanning trees of complete graphs, listing all spanning trees such that consecutive trees differ by pivoting a single edge around a vertex. This pivot Gray code thus addresses an open problem posed by Knuth in The Art of Computer Programming, Volume 4 (Exercise 101, Sectio...","url_abs":"https://arxiv.org/abs/2510.22662","url_pdf":"https://arxiv.org/pdf/2510.22662v1","authors":"[\"Bowie Liu\",\"Dennis Wong\",\"Chan-Tong Lam\",\"Sio-Kei Im\"]","published":"2025-10-26T12:56:34Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}