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

Area of Science:

• Graph Theory
• Computational Chemistry
• Bioinformatics

Background:

• Graph enumeration is a fundamental problem in graph theory.
• Applications span natural sciences and engineering, including bioinformatics and computational chemistry.
• Counting non-isomorphic trees with constraints is crucial for modeling complex systems.

Purpose of the Study:

• To propose a dynamic programming method for counting non-isomorphic trees.
• To enumerate trees with a specified number of vertices (n) and self-loops (Δ).
• To establish bounds for tree-like polymer topologies in chemical compounds.

Main Methods:

• Developed a dynamic programming algorithm to count non-isomorphic rooted trees.
• Algorithm complexity: O(n^2(n+Δ(n+Δ·min{n,Δ}))) time and O(n^2(Δ^2+1)) space.
• Utilized the unique rooted tree representation (unicentroid or virtual vertex for bicentroid) for enumeration.

Main Results:

• Successfully counted non-isomorphic trees with n vertices and Δ self-loops.
• Provided a method to count non-isomorphic rooted trees efficiently.
• Derived lower and upper bounds for tree-like polymer topologies based on cycle rank.

Conclusions:

• The proposed dynamic programming method offers an efficient approach to graph enumeration.
• The results contribute to understanding and quantifying complex molecular structures.
• This work provides foundational insights for applications in chemistry and bioinformatics.