An Efficient Algorithm to Count Tree-Like Graphs with a Given Number of Vertices and Self-Loops

Graph enumeration with given constraints is an interesting problem considered to be one of the fundamental problems in graph theory, with many applications in natural sciences and engineering such as bio-informatics and computational chemistry. For any two integers [Formula: see text] and [Formula: see text] , we propose a method to count all non-isomorphic trees with n vertices, [Formula: see text] self-loops, and no multi-edges based on dynamic programming. To achieve this goal, we count the number of non-isomorphic rooted trees with n vertices, [Formula: see text] self-loops and no multi-edges, in [Formula: see text] time and [Formula: see text] space, since every tree can be uniquely viewed as a rooted tree by either regarding its unicentroid as the root, or in the case of bicentroid, by introducing a virtual vertex on the bicentroid and assuming the virtual vertex to be the root. By this result, we get a lower bound and an upper bound on the number of tree-like polymer topologies of chemical compounds with any “cycle rank”.