Graph theoretical classification and coding of chemical reactions with a linear mechanism

Linear mechanisms of catalytic and noncatalytic chemical reactions which are theoretically feasible have been classified and coded using a detailed procedure for the unique numbering of cycles, edges, and vertices in the kinetic graphs. The following classification criteria are used in a hierarchical order: number of cycles and vertices, mutual connectivity of the cycles, manner of linking any pair of cycles, number of elements linking two cycles, mutual position of two cycles joined to a third one, orientation of edges, and presence of pendant vertices. All the types and classes of mechanisms are presented for reactions having up to five and four routes, respectively.     

Chemical applications of topology and group theory

Earlier approaches to the analysis of chemical dynamic systems using kinetic logic are refined to deal more effectively with systems having the two or more feedback circuits required for chaos. The essential kinetic features of such a system can be represented by a directed graph (called aninfluence diagram) in which the vertices represent the internal species and the directed edges represent kinetic relationships between the internal species. Influence diagrams characteristic of chaotic chemical systems have the following additional features: (1) They are connected; (2) Each vertex has at least one edge directed towards it and one edge directed away from it; (3) There is at least one vertex, called a turbulent vertex, with at least two edges directed towards it. From such an influence diagram a state transition diagram representing the qualitative dynamics of the system can be obtained using the following 4-step procedure: (1) A logical relationship is assigned at each turbulent vertex; (2) A local truth table is generated for each circuit in the influence diagram; (3) The local truth tables are combined to give a global truth table using the logical relationships at the turbulent vertices; (4) The global truth table is used to determine the corresponding state transition diagram using previously described methods. This refined procedure leads to a more restricted set of influence diagrams having the interlocking cycle flow topology required for chaos than the procedure described earlier. Systems with 3 internal species are examined in detail using the refined procedure. All systems with 3 dynamic variables shown in the simulation studies of Rössler to give chaotic dynamics correspond to influence diagrams which give inter-locking cycle (chaotic) flow topologies by the refined procedure. In addition, two models for the Belousov-Zhabotinskii reaction are examined using the refined procedure. The results are potentially informative concerning possible mechanisms for the limitation of the accumulation of autocatalytically produced HBrO₂ (one of the internal species) during the course of this reaction.     

The spectrum of the vertex quadrangulation of a 4-regular toroidal graph and beyond

Journal of Mathematical Chemistry - Let G be a simple plane graph with all vertices of valency 4. The vertex quadrangulation QG of G visually looks like a graph whose vertices are depicted as empty...     

Unique description of chemical structures based on hierarchically ordered extended connectivities (HOC procedures). I. Algorithms for finding graph orbits and canonical numbering of atoms

An iterative algorithm is described for finding topological equivalence, ordering, and canonical numbering of vertexes (atoms) in molecular graphs. Like the Morgan algorithm, it is based on extended connectivities but: (i) the latter are used hierarchically, i. e., the discrimination in the next iteration is carried out only for the vertices having the same extended connectivities (ranks) at the previous iteration; (ii) at equal extended connectivities, additional discrimination is introduced by the ranks of adjacent vertices; (iii) there is no “best name” search; (iv) three levels of complexity of chemical structures are distinguished and handled by different procedures. Two schemes of application of HOC procedures are presented: one directed towards a fast canonical numbering for coding systems, and another one yielding levels of topological equivalence allowing a unique topological representation of the molecule with possible applications to similarity search, structure-activity correlations, etc.     

On the centrality of vertices of molecular graphs

For acyclic systems the center of a graph has been known to be either a single vertex of two adjacent vertices, that is, an edge. It has not been quite clear how to extend the concept of graph center to polycyclic systems. Several approaches to the graph center of molecular graphs of polycyclic graphs have been proposed in the literature. In most cases alternative approaches, however, while being apparently equally plausible, gave the same results for many molecules, but occasionally they differ in their characterization of molecular center. In order to reduce the number of vertices that would qualify as forming the center of the graph, a hierarchy of rules have been considered in the search for graph centers. We reconsidered the problem of “the center of a graph” by using a novel concept of graph theory, the vertex “weights,” defined by counting the number of pairs of vertices at the same distance from the vertex considered. This approach gives often the same results for graph centers of acyclic graphs as the standard definition of graph center based on vertex eccentricities. However, in some cases when two nonequivalent vertices have been found as graph center, the novel approach can discriminate between the two. The same approach applies to cyclic graphs without additional rules to locate the vertex or vertices forming the center of polycyclic graphs, vertices referred to as central vertices of a graph. In addition, the novel vertex “weights,” in the case of acyclic, cyclic, and polycyclic graphs can be interpreted as vertex centralities, a measure for how close or distant vertices are from the center or central vertices of the graph. Besides illustrating the centralities of a number of smaller polycyclic graphs, we also report on several acyclic graphs showing the same centrality values of their vertices. © 2013 Wiley Periodicals, Inc.     

A DNA algorithm for the graph coloring problem

A DNA algorithm based on surfaces for the graph coloring problem is presented. First the whole combinatorial color assignments to the vertices of a graph are synthesized and immobilized on a surface; then a vertex is legally colored while those adjacent to it with illegal colors are deleted; and the cycle is repeated until finally the correct color assignments to the graph are reached. Compared with the other DNA algorithms, our algorithm is easy to implement and error-resistant.     

Nonbonding orbitals in fullerenes: nuts and cores in singular polyhedral graphs

A zero eigenvalue in the spectrum of the adjacency matrix of the graph representing an unsaturated carbon framework indicates the presence of a nonbonding pi orbital (NBO). A graph with at least one zero in the spectrum is singular; nonzero entries in the corresponding zero-eigenvalue eigenvector(s) (kernel eigenvectors) identify the core vertices. A nut graph has a single zero in its adjacency spectrum with a corresponding eigenvector for which all vertices lie in the core. Balanced and uniform trivalent (cubic) nut graphs are defined in terms of (-2, +1, +1) patterns of eigenvector entries around all vertices. In balanced nut graphs all vertices have such a pattern up to a scale factor; uniform nut graphs are balanced with scale factor one for every vertex. Nut graphs are rare among small fullerenes (41 of the 10 190 782 fullerene isomers on up to 120 vertices) but common among the small trivalent polyhedra (62 043 of the 398 383 nonbipartite polyhedra on up to 24 vertices). Two constructions are described, one that is conjectured to yield an infinite series of uniform nut fullerenes, and another that is conjectured to yield an infinite series of cubic polyhedral nut graphs. All hypothetical nut fullerenes found so far have some pentagon adjacencies: it is proved that all uniform nut fullerenes must have such adjacencies and that the NBO is totally symmetric in all balanced nut fullerenes. A single electron placed in the NBO of a uniform nut fullerene gives a spin density distribution with the smallest possible (4:1) ratio between most and least populated sites for an NBO. It is observed that, in all nut-fullerene graphs found so far, occupation of the NBO would require the fullerene to carry at least 3 negative charges, whereas in most carbon cages based on small nut cubic polyhedra, the NBO would be the highest occupied molecular orbital (HOMO) for the uncharged system.     

NFκB pathway analysis: An approach to analyze gene co-expression networks employing feedback cycles

The genes of the NFκB pathway are involved in the control of a plethora of biological processes ranking from inhibition of apoptosis to metastasis in cancer. It has been described that Gliobastoma multiforme (GBM) patients carry aberrant NFκB activation, but the molecular mechanisms are not completely understood. Here, we present a NFκB pathway analysis in tumor specimens of GBM compared to non-neoplasic brain tissues, based on the different kind of cycles found among genes of a gene co-expression network constructed using quantized data obtained from the microarrays. A cycle is a closed walk with all vertices distinct (except the first and last). Thanks to this way of finding relations among genes, a more robust interpretation of gene correlations is possible, because the cycles are associated with feedback mechanisms that are very common in biological networks. In GBM samples, we could conclude that the stoichiometric relationship between genes involved in NFκB pathway regulation is unbalanced. This can be measured and explained by the identification of a cycle. This conclusion helps to understand more about the biology of this type of tumor.     

Characterization of molecular complexity

We put forward a novel index of molecular complexity, ξ, taking into account the symmetry of a molecular graph and the specificity of structural components considered. The ξ index is defined as the sum of augmented valences of all mutually nonequivalent vertices in a molecular graph. The augmented valence of a vertex in a graph is the sum of its valence and valences of all neighboring vertices with the weight 1/2^d depending on their distance, d, from the vertex. The ξ index is examined on the set of octane isomers and some special classes of graphs. It is also compared with a certain number of alternative complexity measures considered in the literature. © 2002 Wiley Periodicals, Inc. Int J Quantum Chem, 2003     

Version of zones and zigzag structure in icosahedral fullerenes and icosadeltahedra

A circuit of faces in a polyhedron is called a zone if each face is attached to its two neighbors by opposite edges. (For odd-sized faces, each edge has a left and a right opposite partner.) Zones are called alternating if, when odd faces (if any) are encountered, left and right opposite edges are chosen alternately. Zigzag (Petrie) circuits in cubic (= trivalent) polyhedra correspond to alternating zones in their deltahedral duals. With these definitions, a full analysis of the zone and zigzag structure is made for icosahedral centrosymmetric fullerenes and their duals. The zone structure provides hypercube embeddings of these classes of polyhedra which preserve all graph distances (subject to a scale factor of 2) up to a limit that depends on the vertex count. These embeddings may have applications in nomenclature, atom/vertex numbering schemes, and in calculation of distance invariants for this subclass of highly symmetric fullerenes and their deltahedral duals.     

Computer generation of the characteristic polynomials of chemical graphs

A computer program based on the Frame method for the characteristic polynomials of graphs is developed. This program makes use of an efficient polynomial algorithm of Frame for generating the coefficients in the characteristic polynomials of graphs. This program requires as input only the set of vertices that are neighbors of a given vertex and with labels smaller than the label of that vertex. The program generates and stores only the lower triangle of the adjacency matrix in canonical ordering in a one-dimensional array. The program is written in integer arithmetic, and it can be easily modified to real arithmetic. The coefficients in the characteristic polynomials of several graphs were generated in less than a few seconds, thus solving the difficult problem of generating characteristic polynomials of graphs. The characteristic polynomials of a number of very complicated graphs are obtained including for the first time the characteristic polynomial of an honeycomb lattice graph containing 54 vertices.     

Improved strategy in analytic surface calculation for molecular systems: Handling of singularities and computational efficiency

Computer methods for analytic surface calculations of molecular systems suffer from numerical instabilities and are CPU time consuming. In this article, we present proposals toward the solution of both problems. Singularities arise when nearly collinear triples of neighboring atoms or multiple vertices are encountered during the calculation. Topological decisions in analytic surface calculation algorithms (accessibility of vertices and arcs) are based upon the comparison of distances or angles. If two such numbers are nearly equal, then currently used computer programs may not resolve this ambiguity correctly and can subsequently fail. In this article, modifications in the analytic surface calculation algorithm are described that recognize singularities automatically and treat them appropriately without restarting parts of the computation. The computing time required to execute these alterations is minimal. The basic modification consists in defining an accuracy limit within which two values may be assumed as equal. The search algorithm has been reformulated to reduce the computational effort. A new set of formulas makes it possible to avoid mostly the extraction of square roots. Tests for small-and medium-sized intersection circles and for pairs of vertices with small vertex height help recognize fully buried circles and vertex pairs at an early stage. The new program can compute the complete topology of the surface and accessible surface area of the protein crambin in 1.50–4.29 s (on a single R3000 processor of an SGI 4D/480) depending on the compactness of the conformation where the limits correspond to the fully extended or fully folded chain, respectively. The algorithm, implemented in a computer program, will be made available on request. © John Wiley & Sons, Inc.     

A High-Performance Asymmetric Supercapacitor Based on Tungsten Oxide Nanoplates and Highly Reduced Graphene Oxide Electrodes

Tungsten oxide/graphene hybrid materials are attractive semiconductors for energy-related applications. Herein, we report an asymmetric supercapacitor (ASC, HRG//m-WO₃ ASC), fabricated from monoclinic tungsten oxide (m-WO₃) nanoplates as a negative electrode and highly reduced graphene oxide (HRG) as a positive electrode material. The supercapacitor performance of the prepared electrodes was evaluated in an aqueous electrolyte (1 m H₂SO₄) using three- and two-electrode systems. The HRG//m-WO₃ ASC exhibits a maximum specific capacitance of 389 F g⁻¹ at a current density of 0.5 A g⁻¹, with an associated high energy density of 93 Wh kg⁻¹ at a power density of 500 W kg⁻¹ in a wide 1.6 V operating potential window. In addition, the HRG//m-WO₃ ASC displays long-term cycling stability, maintaining 92 % of the original specific capacitance after 5000 galvanostatic charge–discharge cycles. The m-WO₃ nanoplates were prepared hydrothermally while HRG was synthesized by a modified Hummers method.     

(C4N3H15)[(BO2)2(GeO2)4]: the first organically templated 3D borogermanate showing 1D 12-rings, large channels, and a novel zeolite-type framework topology constructed from Ge8O24 and B2O7 cluster units

The first organically templated 3D borogermanate with a novel zeolite-type topology, (C4N3H15)[(BO2)2(GeO2)4] FJ-17, has been solvothermally synthesized and characterized by IR spectroscopy, powder X-ray diffraction (PXRD), TGA, and single-crystal X-ray diffraction. The compound crystallized in the monoclinic space group P2(1)/c with a = 6.967(1) A, b = 10.500(1) A, c = 20.501(1) A, beta = 90.500(3) degrees , V = 1499.68(8) A3, and Z = 4. The framework topology of this compound is the previously unknown topology with the vertex symbols 3.4.3.9.3.8(2) (vertex 1), 3.8.3.4.6(2).9(2) (vertex 2), 3.8(2).4.6(2).6(2).8 (vertex 3), 4.8.4.8.8(3).12 (vertex 4), 4.8.4.8.8(2).12 (vertex 5), and 3.8.4.6(2).6.8(2) (vertex 6). The structure is constructed from Ge8O24 and B2O7 clusters. The Ge8O24 cluster contains eight GeO4 tetrahedra that share vertices; the B2O7 unit is composed of two BO4 tetrahedra sharing a vertex. The cyclic Ge8O24 clusters connect to each other through vertices to form a 2D layer with 8,12-nets. The adjacent layers are further linked by the dimeric B2O7 cluster units, resulting in a 3D framework with 12- and 8-ring channels along the a and b axes, respectively. In addition, there is a unique B2GeO9 3-ring in the structure.     

Details of the reaction graphs for intramolecular isomerizations of the carboranes

From proposed mechanisms for framework reorganizations of the carboranes C₂B _n-2H _n ,n = 5–12, we present reaction graphs in which points or vertices represent individual carborane isomers, while edges or arcs correspond to the various intramolecular rearrangement processes that carry the pair of carbon heteroatoms to different positions within the same polyhedral form. Because they contain both loops and multiple edges, these graphs are actually pseudographs. Loops and multiple edges have chemical significance in several cases. Enantiomeric pairs occur among carborane isomers and among the transition state structures on pathways linking the isomers. For a carborane polyhedral structure withn vertices, each graph hasn(n -1)/2 graph edges. The degree of each graph vertex and the sum of degrees of all graph vertices are independent of the details of the isomerization mechanism. The degree of each vertex is equal to twice the number of rotationally equivalent forms of the corresponding isomer. The total of all vertex degrees is just twice the number of edges orn(n - 1). The degree of each graph vertex is related to the symmetry point group of the structure of the corresponding isomer. Enantiomeric isomer pairs are usually connected in the graph by a single edge and never by more than two edges.     

Unique description of chemical structures based on hierarchically ordered extended connectivities (HOC procedures). V. New topological indices,ordering of graphs,and recognition of graph similarity

The vertex numbering obtained by application of the HOC algorithm can be converted into two sequences of numbers: If each vertex starting with vertex 1 is only counted once, the sums of numberings of adjacent vertices form sequence S_i (i = 1?N), while the sums of S_i values form sequence M_i (i = 1?N). These two sequences can be used for (i) two new topological indices, ?? and ??, the latter being of extremely low degeneracy, and the former correlating with boiling points of alkanes; (ii) a criterion based on sequence S_i for ordering graphs which possess the same number N of vertices; and (iii) a quantitative measure, also based on sequence S_i, for appreciating the similarity or dissimilarity of pairs of graphs. Comparisons with other topological indices, ordering criteria, and similarity measures for graphs show that the newly devised procedures compare favorably with those known previously.     

Unique description of chemical structures on hierarchically ordered extended connectivities (HOC procedures). II. Mathematical proofs for the HOC algorithm

The basic notions and definitions, necessary for the better understanding of Part I of this series, are presented. The mathematical proof is given for sufficiency of the various HOC procedures for vertex canonical numbering and graph orbit finding.     

The graph center concept for polycyclic graphs

While the concept of the graph center is unambiguous (and quite old) in the case of acyclic graphs, an attempt has been made recently to extend the concept to polycyclic structures using the distance matrix of a graph as the basis. In this work we continue exploring such generalizations considering in addition to the distance matrix, self-avoiding walks or paths as graph invariants of potential interest for discriminating distinctive vertex environments in a graph of polycyclic structures. A hierachy of criteria is suggested that offers a systematic approach to the vertex discrimination and eventually establishes in most cases the graph center as a single vertex, a single bond (edge), or a single group of equivalent vertices. Some applications and the significance of the concept of the graph center are presented.     

Symmetry properties of chemical graphs. IV. Rearrangement of tetragonal-pyramidal complexes

Using a canonical numbering of vertices for the graph corresponding to a particular rearrangement of tetragonal–pyramidal complexes, all 120 permutations defining the symmetry for the rearrangement are derived. An examination of the permutations points to the symmetric group S₅, which has previously been found for isomerizations of trigonal–bipyramidal complexes and in the rearrangement of homotetrahedryl cations.