Generating Spanning-Tree Sequences of a Fan Graph in Lexicographic Order and Ranking/Unranking Algorithms

Cameron et al. [27th Int. Conf. Computing and Combinatorics (COCOON 2021), LNCS 13025, pp. 49-60] recently presented an algorithm for generating all spanning trees of a fan graph in O(1)amortized time. The listing of spanning trees fulfills the so-called pivot Gray code property so that successive trees differ by pivoting a single edge around a vertex. They also presented algorithms for ranking and unranking a spanning tree in the listing in O(n) time using O(n) space. In this paper, we first observe that all spanning trees of a fan graph can be naturally represented by integer sequences so that their coding tree has properties with regularity. Then, we propose a simple algorithm for generating spanning-tree sequences in lexicographic order in O(1)amortized time according to these properties. Additionally, based on the lexicographic order, we develop ranking and unranking algorithms in O(n)-time using n + O(1) space (i.e., the size of the space is just slightly larger than n).

Automated summary

This paper presents an algorithm for generating all spanning trees of a fan graph and provides methods for ranking and unranking. The time and space complexities of these algorithms are analyzed.