×

Algorithmic generation of molecular graphs with large Merrifield-Simmons index. (English) Zbl 1141.05077

The Merrifield-Simmons index of a graph \(G\) is equal to the number of independent-vertex sets of \(G\). An algorithm for constructing trees with large Merrifield-Simmons index is developed. The algorithm works for so-called ‘acyclic molecular graphs’, that is trees in which the maximal vertex degree does not exceed 4. The structure of such trees having maximal Merrifield-Simmons index is conjectured.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C90 Applications of graph theory
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
PDFBibTeX XMLCite