{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T18:41:44Z","timestamp":1761676904595,"version":"build-2065373602"},"reference-count":24,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Cycle rank is an important notion that is widely used to classify, understand, and discover new chemical compounds. We propose a method to enumerate all non-isomorphic tree-like graphs of a given cycle rank with self-loops and no multiple edges. To achieve this, we develop an algorithm to enumerate all non-isomorphic rooted graphs with the required constraints. The idea of our method is to define a canonical representation of rooted graphs and enumerate all non-isomorphic graphs by generating the canonical representation of rooted graphs. An important feature of our method is that for an integer n\u22651, it generates all required graphs with n vertices in O(n) time per graph and O(n) space in total, without generating invalid intermediate structures. We performed some experiments to enumerate graphs with a given cycle rank from which it is evident that our method is efficient. As an application of our method, we can generate tree-like polymer topologies of a given cycle rank with self-loops and no multiple edges.<\/jats:p>","DOI":"10.3390\/e22111295","type":"journal-article","created":{"date-parts":[[2020,11,16]],"date-time":"2020-11-16T11:04:20Z","timestamp":1605524660000},"page":"1295","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Enumerating Tree-Like Graphs and Polymer Topologies with a Given Cycle Rank"],"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-850, 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-850, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"Nagamochi","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics and Physics, Kyoto University, Kyoto 606-850, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Azam, N.A., Shurbevski, A., and Nagamochi, H. (2020). A method for enumerating pairwise compatibility graphs with a given number of vertices. Discrete Applied Mathematics, Elsevier.","DOI":"10.1016\/j.dam.2020.08.016"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Azam, N.A., Shurbevski, A., and Nagamochi, H. (2020, January 29\u201331). On the Enumeration of Minimal Non-pairwise Compatibility Graphs. Proceedings of the International Computing and Combinatorics Conference, Atlanta, GA, USA.","DOI":"10.1007\/978-3-030-58150-3_30"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Gugisch, R., Kerber, A., Kohnert, A., Laue, R., Meringer, M., R\u00fccker, C., and Wassermann, A. (2015). MOLGEN 5.0, a molecular structure generator. Advances in Mathematical Chemistry and Applications, Elsevier.","DOI":"10.2174\/9781608059287114010010"},{"key":"ref_4","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_5","doi-asserted-by":"crossref","first-page":"1345","DOI":"10.1021\/ci700385a","article-title":"Enumerating treelike chemical graphs with given path frequency","volume":"48","author":"Fujiwara","year":"2008","journal-title":"J. Chem. Inf. Model."},{"key":"ref_6","first-page":"53","article-title":"Improved algorithms for enumerating tree-like chemical graphs with given path frequency","volume":"21","author":"Ishida","year":"2008","journal-title":"Genome Inf."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1186\/1758-2946-6-31","article-title":"Efficient enumeration of monocyclic chemical graphs with given path frequencies","volume":"6","author":"Suzuki","year":"2014","journal-title":"J. Cheminf."},{"key":"ref_8","first-page":"1","article-title":"A 2-phase algorithm for enumerating tree-like chemical graphs satisfying given upper and lower bounds","volume":"28","author":"Suzuki","year":"2012","journal-title":"IPSJ SIG Tech. Rep."},{"key":"ref_9","unstructured":"Jin, W., Barzilay, R., and Jaakkola, T. (2018). Junction tree variational autoencoder for molecular graph generation. arXiv."},{"key":"ref_10","unstructured":"Nakano, S.I., and Uno, T. (2003). A Simple Constant Time Enumeration Algorithm for Free Trees, PSJ. PSJ SIGNotes ALgorithms."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1526","DOI":"10.1515\/math-2019-0129","article-title":"A novel method to construct NSSD molecular graphs","volume":"17","author":"Hayat","year":"2019","journal-title":"Open Math."},{"key":"ref_12","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_13","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\/0008876801010108"},{"key":"ref_14","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 Nature.","DOI":"10.1007\/978-3-030-71051-4_51"},{"key":"ref_15","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_16","first-page":"1","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_17","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_18","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_19","unstructured":"Haruna, T., Horiyama, T., and Shimokawa, K. (2017). On the Enumeration of Polymer Topologies, Information Processing Society of Japan. IPSJ SIG Technical Report."},{"key":"ref_20","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_21","doi-asserted-by":"crossref","unstructured":"Azam, N.A., Shurbevski, A., and Nagamochi, H. (2020). An Efficient Algorithm to Count Tree-Like Graphs with a Given Number of Vertices and Self-Loops. Entropy, 22.","DOI":"10.3390\/e22090923"},{"key":"ref_22","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press."},{"key":"ref_23","unstructured":"Masui, R., Shurbevski, A., and Nagamochi, H. (2009). Enumeration of Unlabeled Tree by Dynamic Programming, Department of Applied Mathematics and Physics, Kyoto University. Available online: http:\/\/www.amp.i.kyoto-u.ac.jp\/tecrep\/ps-file\/2019\/2019-003.pdf."},{"key":"ref_24","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\/11\/1295\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:33:15Z","timestamp":1760178795000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/11\/1295"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":24,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2020,11]]}},"alternative-id":["e22111295"],"URL":"https:\/\/doi.org\/10.3390\/e22111295","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2020,11,13]]}}}