Counting Tree-like Multigraphs with a Given Number of Vertices and Multiple Edges

Muhammad Ilyas, Seemab Hayat and Naveed Ahmed Azam ()
Additional contact information
Muhammad Ilyas: Discrete Mathematics and Computational Intelligence Laboratory, Department of Mathematics, Quaid-i-Azam University, Islamabad 45320, Pakistan
Seemab Hayat: Discrete Mathematics and Computational Intelligence Laboratory, Department of Mathematics, Quaid-i-Azam University, Islamabad 45320, Pakistan
Naveed Ahmed Azam: Discrete Mathematics and Computational Intelligence Laboratory, Department of Mathematics, Quaid-i-Azam University, Islamabad 45320, Pakistan

Mathematics, 2025, vol. 13, issue 21, 1-24

Abstract: The enumeration of chemical graphs plays a crucial role in cheminformatics and bioinformatics, especially in the search for novel drug discovery. These graphs are usually tree-like multigraphs, or they consist of tree-like multigraphs attached to a central core. In both configurations, the tree-like components play a key role in determining the properties and activities of chemical compounds. In this work, we propose a dynamic programming approach to precisely count the number of tree-like multigraphs with a given number of n vertices and Δ multiple edges. Our method transforms multigraphs into rooted forms by designating their unicentroid or bicentroid as the root and then defining a canonical representation based on the maximal subgraphs rooted at the root’s children. This canonical form ensures that each multigraph is counted only once. Recursive formulas are then established based on the number of vertices and multiple edges in the largest subgraphs rooted at the root’s children. The resulting algorithm achieves a time complexity of O ( n 2 ( n + Δ ( n + Δ 2 · min { n , Δ } ) ) ) and space complexity of O ( n 2 ( Δ 3 + 1 ) ) . Extensive experiments demonstrate that the proposed method scales efficiently, being able to count multigraphs with up to 200 vertices (e.g., (200, 26)) and up to 50 multiple edges (e.g., (90, 50)) in under 15 min. In contrast, the available state-of-the-art tool Nauty runs out of memory beyond moderately sized instances, as it relies on explicit generation of all candidate multigraphs. These results highlight the practical advantage and strong potential of the proposed method as a scalable tool for chemical graph enumeration in drug discovery applications.

Keywords: trees; chemical graphs; graph isomorphism; enumeration; dynamic programming (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/21/3405/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/21/3405/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:21:p:3405-:d:1779886

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().