{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T18:41:25Z","timestamp":1761676885062,"version":"build-2065373602"},"reference-count":18,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,8,22]],"date-time":"2020-08-22T00:00:00Z","timestamp":1598054400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["18J23484"],"award-info":[{"award-number":["18J23484"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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 n\u22651 and \u0394\u22650, we propose a method to count all non-isomorphic trees with n vertices, \u0394 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, \u0394 self-loops and no multi-edges, in O(n2(n+\u0394(n+\u0394\u00b7min{n,\u0394}))) time and O(n2(\u03942+1)) 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 \u201ccycle rank\u201d.<\/jats:p>","DOI":"10.3390\/e22090923","type":"journal-article","created":{"date-parts":[[2020,8,23]],"date-time":"2020-08-23T21:28:06Z","timestamp":1598218086000},"page":"923","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["An Efficient Algorithm to Count Tree-Like Graphs with a Given Number of Vertices and Self-Loops"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7941-3419","authenticated-orcid":false,"given":"Naveed Ahmed","family":"Azam","sequence":"first","affiliation":[{"name":"Department of Applied Mathematics and Physics, Kyoto University, Kyoto 606-8502, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9224-6929","authenticated-orcid":false,"given":"Aleksandar","family":"Shurbevski","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics and Physics, Kyoto University, Kyoto 606-8502, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"Nagamochi","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics and Physics, Kyoto University, Kyoto 606-8502, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,8,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02546665","article-title":"Kombinatorische anzahlbestimmungen f\u00fcr gruppen, graphen und chemische verbindungen","volume":"68","year":"1937","journal-title":"Acta Math."},{"key":"ref_2","unstructured":"Polya, G., and Read, R.C. (2012). Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds, Springer Science & Business Media."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"8732","DOI":"10.1021\/ja902302h","article-title":"970 million druglike small molecules for virtual screening in the chemical universe database GDB-13","volume":"131","author":"Blum","year":"2009","journal-title":"J. Am. Chem. Soc."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Azam, N.A., Chiewvanichakorn, R., Zhang, F., Shurbevski, A., Nagamochi, H., and Akutsu, T. (2020, January 24\u201326). A method for the inverse QSAR\/QSPR based on artificial neural networks and mixed integer linear programming. Proceedings of the 13th International Joint Conference on Biomedical Engineering Systems and Technologies\u2014Volume 3: Bioinformatics, Valletta, Malta.","DOI":"10.5220\/0008876800002513"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Ito, R., Azam, N.A., Wang, C., Shurbevski, A., Nagamochi, H., and Akutsu, T. (2020). A novel method for the inverse QSAR\/QSPR to monocyclic chemical compounds based on artificial neural networks and integer programming. Advances in Computer Vision and Computational Biology, Springer.","DOI":"10.1007\/978-3-030-71051-4_51"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Zhu, J., Wang, C., Shurbevski, A., Nagamochi, H., and Akutsu, T. (2020). A novel method for inference of chemical compounds of cycle index two with desired properties based on artificial neural networks and integer programming. Algorithms, 13.","DOI":"10.3390\/a13050124"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1038\/s41467-019-13807-w","article-title":"De novo generation of hit-like molecules from gene expression signatures using artificial intelligence","volume":"11","author":"Baillif","year":"2020","journal-title":"Nat. Commun."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1153","DOI":"10.1039\/C9SC04503A","article-title":"Scaffold-based molecular design with a graph generative model","volume":"11","author":"Lim","year":"2020","journal-title":"Chem. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"440","DOI":"10.3390\/metabo3020440","article-title":"Small molecule identification with MOLGEN and mass spectrometry","volume":"3","author":"Meringer","year":"2013","journal-title":"Metabolites"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0003-2670(95)00291-7","article-title":"MOLGEN+, a generator of connectivity isomers and stereoisomers for molecular structure elucidation","volume":"314","author":"Benecke","year":"1995","journal-title":"Anal. Chim. Acta"},{"key":"ref_11","unstructured":"(2020, July 04). Available online: http:\/\/sunflower.kuicr.kyoto-u.ac.jp\/tools\/enumol2\/."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1186\/1758-2946-4-21","article-title":"OMG: Open molecule generator","volume":"4","author":"Peironcely","year":"2012","journal-title":"J. Cheminf."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"5317","DOI":"10.1016\/j.bmc.2012.03.030","article-title":"Chemoinformatics: A view of the field and current trends in method development","volume":"20","author":"Vogt","year":"2012","journal-title":"Bioorg. Med. Chem."},{"key":"ref_14","first-page":"1","article-title":"On the enumeration of polymer topologies","volume":"2017-Al-162","author":"Haruna","year":"2017","journal-title":"IPSJ SIG Tech. Rep."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1016\/S0079-6700(02)00009-6","article-title":"Topological polymer chemistry","volume":"27","author":"Tezuka","year":"2002","journal-title":"Prog. Polym. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0166-218X(88)90012-1","article-title":"Some applications of graph theory to the study of polymer configuration","volume":"19","author":"Galina","year":"1988","journal-title":"Discret. Appl. Math."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1301","DOI":"10.1063\/1.1747157","article-title":"The dimensions of chain molecules containing branches and rings","volume":"17","author":"Zimm","year":"1949","journal-title":"J. Chem. Phys."},{"key":"ref_18","first-page":"81","article-title":"Sur les assemblages de lignes","volume":"70","author":"Jordan","year":"1869","journal-title":"J. Reine Angew. Math."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/9\/923\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:05:16Z","timestamp":1760177116000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/9\/923"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,22]]},"references-count":18,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["e22090923"],"URL":"https:\/\/doi.org\/10.3390\/e22090923","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2020,8,22]]}}}