A Pivot Gray Code Listing for the Spanning Trees of the Fan Graph

2021/08/20 by Ben Cameron, Cameron, Ben, Aaron Grubb +3
Computer Science · Engineering · #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2108.09363

openalex publication_date 2021/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We use a greedy strategy to list the spanning trees of the fan graph, F_n, such that successive trees differ by pivoting a single edge around a vertex. It is the first greedy algorithm for exhaustively generating spanning trees using such a minimal change operation. The resulting listing is then studied to find a recursive algorithm that produces the same listing in O(1)-amortized time using O(n) space. Additionally, we present O(n)-time algorithms for ranking and unranking the spanning trees for our listing; an improvement over the generic O(n³)-time algorithm for ranking and unranking spanning trees of an arbitrary graph.

Related

• Pivot Gray Codes for the Spanning Trees of a Graph ft. the Fan
• Generating pivot Gray codes for spanning trees of complete graphs in constant amortized time
• Approximate Spanning Tree Counting from Uncorrelated Edge Sets
• A combinatorial algorithm to generate all spanning trees of a weighted\n graph in order of increasing cost
• Listing spanning trees of outerplanar graphs by pivot-exchanges