Counting the spanning trees of a labelled molecular-graph

Ogre: A Python package for molecular crystal surface generation with applications to surface energy and crystal habit prediction

We present Ogre, an open-source code for generating surface slab models from bulk molecular crystal structures. Ogre is written in Python and interfaces with the FHI-aims code to calculate surface energies at the level of density functional theory (DFT). The input of Ogre is the geometry of the bulk molecular crystal. The surface is cleaved from the bulk structure with the molecules on the surface kept intact. A slab model is constructed according to the user specifications for the number of molecular layers and the length of the vacuum region. Ogre automatically identifies all symmetrically unique surfaces for the user-specified Miller indices and detects all possible surface terminations. Ogre includes utilities to analyze the surface energy convergence and Wulff shape of the molecular crystal. We present the application of Ogre to three representative molecular crystals: the pharmaceutical aspirin, the organic semiconductor tetracene, and the energetic material HMX. The equilibrium crystal shapes predicted by Ogre are in agreement with experimentally grown crystals, demonstrating that DFT produces satisfactory predictions of the crystal habit for diverse classes of molecular crystals.

Reliable Graphs for SLAM

Estimation-over-graphs (EoG) is a class of estimation problems that admit a natural graphical representation. Several key problems in robotics and sensor networks, including sensor network localization, synchronization over a group, and simultaneous localization and mapping (SLAM) fall into this category. We pursue two main goals in this work. First, we aim to characterize the impact of the graphical structure of SLAM and related problems on estimation reliability. We draw connections between several notions of graph connectivity and various properties of the underlying estimation problem. In particular, we establish results on the impact of the weighted number of spanning trees on the D-optimality criterion in 2D SLAM. These results enable agents to evaluate estimation reliability based only on the graphical representation of the EoG problem. We then use our findings and study the problem of designing sparse SLAM problems that lead to reliable maximum likelihood estimates through the synthesis of sparse graphs with the maximum weighted tree connectivity. Characterizing graphs with the maximum number of spanning trees is an open problem in general. To tackle this problem, we establish several new theoretical results, including the monotone log-submodularity of the weighted number of spanning trees. We exploit these structures and design a complementary greedy–convex pair of efficient approximation algorithms with provable guarantees. The proposed synthesis framework is applied to various forms of the measurement selection problem in resource-constrained SLAM. Our algorithms and theoretical findings are validated using random graphs, existing and new synthetic SLAM benchmarks, and publicly available real pose-graph SLAM datasets.

Overall connectivities/topological complexities: a new powerful tool for QSPR/QSAR

Earlier attempts to assess the complexity of molecules are analyzed and summarized in a number of definitions of general and topological complexity. A concept which specifies topological complexity as overall connectivity, and generalizes the idea of molecular connectivities of Randic, Kier, and Hall, is presented. Two overall connectivity indices, TC and TC1, are defined as the connectivity (the sum of the vertex degrees) of all connected subgraphs in the molecular graph. The contributions to TC and TC1, which originate from all subgraphs having the same number of edges e, form two sets of eth-order overall connectivities, eTC and eTC1. The total number of subgraphs K is also analyzed as a complexity measure, and the vector of its eth-order components, eK, is examined as well. The TC, TC1, and K indices match very well the increase in molecular complexity with the increase in the number of atoms and, at a constant number of atoms, with the increased degree of branching and cyclicity of the molecular skeleton, as well as with the multiplicity of bonds and the presence of heteroatoms. The potential of the three sets of eth-order complexities for applications to QSPR was tested by the modeling of 10 alkane properties (boiling point, critical temperature, critical pressure, critical volume, molar volume, molecular refraction, heat of formation, heat of vaporization, heat of atomization, and surface tension), in parallel with Kier and Hall's molecular connectivity indices (k)chi. The topological complexity indices were shown to outperform molecular connectivity indices in 44 out of the 50 pairs of models compared, including all models with four and five parameters.

Complexity of molecules

Several currently used measures of the complexity of molecules, such as, for example, those by Bertz and Randic or those based on the number of spanning trees, are briefly reviewed. We also proposed as complexity measures the sum of vertex-weights and the sum of edge-weights and their variants related to partition of vertex-weights and edge-weights into classes by their numerical values. The vertex-weights considered are the squares of the vertex-degrees, and the edge-weights are products of vertex-degrees making up the edges. Comparison is made between considered complexity measures for selected molecular graphs. All considered indices increase with increasing size and cyclicity and most with increasing branching. However, they differ regarding the influence of symmetry.

Walk counts, labyrinthicity, and complexity of acyclic and cyclic graphs and molecules

It is demonstrated how the complexity of a (molecular) graph can be quantified in terms of the walk counts, extremely easily obtained graph invariants that depend on size, branching, cyclicity, and edge and vertex weights (unsaturation, heteroatoms). The influence of symmetry is easily accounted for. The term labyrinthicity is proposed for what is measured by walk counts alone, neglecting symmetry. The total walk count and recently advanced measures of labyrinthicity or complexity are compared with respect to the ordering of structures and to the computational effort required to obtain numerical values.