I would like to make and visualize graph library of $n$ vertices that each vertex can only have maximum of four edges. The reason behind this is that the results will be used for designing chemical libraries where each vertex is a carbon and a carbon can only form from one to four lines (edges) to carbon(s), neglecting any other atom (for example, hydrogen) connecting to the carbon. In short, this library will consist of pure carbon network.
I appreciate any result that chemically unfeasible because considering this aspect is irrelevant in this forum. What softwares that can be used to exhaustively enumerate the graphs? It would also be good if there is any resource which has realized this idea.
Thank you.
Best Answer
Wikipedia: Chemical graph generator
Wikipedia: List of straight-chain alkanes
Computer algebra systems like MAPLE and MATHEMATICA can generate random graphs with given properties like connectedness, absence of cycles and vertex degree.
Chemistry Development Kit
Peironcely, J. E.; Rojas-Chertó, M.; Fichera, D.; Reijmers, Th.; Coulier, L.; Faulon, J.-L.; Hankemeier, Th.: OMG: Open Molecule Generator. J. Cheminform. 4 (2012) 21
Fiehn Lab: Molecular Isomer Generators. 2016
Yirik, M. A.; Steinbeck, Ch.: Chemical graph generators. PLOS Computational Biology 17 (2021) (1) e1008504
Yirik, M. A.: Development of an Open Source Molecular Structure Generator
https://github.com/MehmetAzizYirik
https://github.com/MehmetAzizYirik/AlgorithmicGroupTheory
You could use the method of systematic generation of the graphs of given height used by Cayley, Pólya and Read:
Pólya, G.: Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Mathematica 68 (1937) 145-254
Pólya, G; Read, R. C.: Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds. Springer, 1987
Read, R.C.: The Enumeration of Acyclic Chemical Compounds. in: Balaban, A.T. (Ed.): Chemical Applications of Graph Theory. Academic Press, 1976
OEIS: A000055 Number of trees with n unlabeled nodes