Hamiltonian circuits,Hamiltonian paths and branching graphs of benzenoid systems

A benzenoid systemH is a finite connected subgraph of the infinite hexagonal lattice with out cut bonds and non-hexagonal interior faces. The branching graphG ofH consists of all vertices ofH of degree 3 and bonds among them. In this paper, the following results are obtained:

1. A necessary condition for a benzenoid system to have a Hamiltonian circuit.
2. A necessary and sufficient condition for a benzenoid system to have a Hamiltonian path.
3. A characterization of connected subgraphs of the infinite hexagonal lattice which are branching graphs of benzenoid systems.
4. A proof that if a disconnected subgraph G of the infinite hexagonal lattice given along with the positions of its vertices is the branching graph of a benzenoid system H, then H is unique.

     

Graph theory of synthons

A graph-theory model of synthons is suggested. A synthon is a special kind of the molecular graph in which some vertices are distinguished from other ones, and they are called the virtual vertices. The most important property of the synthons is that the constraint of strict stoichiometry is removed and the virtual vertices formally correspond to functional groups that are not closely specified.     

Normal components of benzenoid systems

Summary Consider a benzenoid system with fixed bonds and the subgraph obtained by deleting fixed double bonds together with their end vertices and fixed single bonds without their end vertices. It has often been observed for particular benzenoid systems, and conjectured (or stated) that, in general, such a subgraph has at least two components, and that each component is also a benzenoid system and is normal. But there are no rigorous proofs for that. The aim of this paper is to present mathematical proofs of those two facts. It is also shown that if a benzenoid system has a single hexagon as one of its normal components then it has at least three normal components.     

Computing weighted Szeged and PI indices from quotient graphs

The weighted (edge-)Szeged index and the weighted (vertex-)PI index are modifications of the (edge-)Szeged index and the (vertex-)PI index, respectively, because they take into account also the vertex degrees. As the main result of this article, we prove that if G is a connected graph, then all these indices can be computed in terms of the corresponding indices of weighted quotient graphs with respect to a partition of the edge set that is coarser than the Θ^*-partition. If G is a benzenoid system or a phenylene, then it is possible to choose a partition of the edge set in such a way that the quotient graphs are trees. As a consequence, it is shown that for a benzenoid system, the mentioned indices can be computed in sublinear time with respect to the number of vertices. Moreover, closed formulas for linear phenylenes are also deduced.     

On isospectral benzenoid graphs

The recently Proposed procedure [5] for the construction of isospectral benzenoid graphs has been examined in detail. Necessary and sufficient conditions for the construction of isospectral benzenoid graphs with isomorphicH-graphs are formulated. The inapplicability of the Procedure for the construction of isospectral benzenoid graphs with an even number of vertices has been proven.     

k-resonant benzenoid systems and k-cycle resonant graphs.

A benzenoid system (or hexagonal system) H is said to be k-resonant if, for 1 < or = t < or = k, any t disjoint hexagons of H are mutually resonant; that is, there is a Kekule structure (or perfect matching) K of H such that each of the k hexagons is an K-alternating hexagon. A connected graph G is said to be k-cycle resonant if, for 1 < or = t < or = k, any t disjoint cycles in G are mutually resonant. The concept of k-resonant benzenoid systems is closely related to Clar's aromatic sextet theory, and the concept of k-cycle resonant graphs is a natural generalization of k-resonant benzenoid systems. Some necessary and sufficient conditions for a benzenoid system (respectively a graph) to be k-resonant (respectively k-cycle resonant) have been established. In this paper, we will give a survey on investigations of k-resonant benzenoid systems and k-cycle resonant graphs.     

Discriminating tests of information and topological indices. Animals and trees

In this paper we consider 13 information and topological indices based on the distance in a molecular graph with respect to their discrimination power. The numerical results of discriminating tests on 3490528 trees up to 21 vertices are given. The indices of the highest sensitivity are listed on the set of 1528775 alkane trees. The discrimination powers of indices are also examined on the classes of 849285 hexagonal, 298382 square, and 295365 triangular simply connected animals. The first class of animals corresponds to the structural formulas of planar benzenoid hydrocarbons. The values of all indices were calculated for all classes of animals as well as for the united set of 1443032 animals. The inspection of the data indicates the great sensitivity of four information indices and one topological index.     

On the spectacular structural isomorphism between CnHs monoradical and Cn+sHs+3 diradical benzenoid hydrocarbons: from reactive intermediates to vacancy (Hole) defects in graphite

The formula/structure informatics of monoradical and diradical benzenoid hydrocarbons that are potential reactive intermediates is studied. Some new enumeration and structural results with analytical expressions are presented. The topological paradigm and one-to-one correspondence between the monoradical and diradical constant-isomer series is demonstrated. Constant-isomer benzenoid monoradicals of the formula CnHs have a one-to-one correspondence in isomer number and topology to constant-isomer diradicals of the formula Cn+sHs+3. Some electronic properties of benzenoid radicals are delineated. Excising out a monoradical or diradical benzenoid carbon molecule from a perfect hexagonal graphite layer leaves a matching monoradical or diradical vacancy hole defect called an antimolecule; this observation can be generalized to include excising out all nondisjoint and obvious benzenoid polyradicals from a perfect (Kekuléan) hexagonal graphite layer. It is shown that the characteristics of graphite vacancies (antimolecules) can be deduced from knowledge about the carbon molecules removed in their formation.     

The number of Kekulé structures and the thermodynamic stability of conjugated systems

The dependence of Hückel π-electron energies, E_π, on the basic graph theoretical parameters N (the number of vertices), ν (the number of edges) and ASC (the algebraic structure count) is explored. The form with the ASC enters E_π is established and an equation for E_π is developed. It is shown how the early and apparent success of the (resonance) theory rested on the fortunate fact that all Kekulé structures for benzenoid hydrocarbons and acyclic polyenes have the same parity. The significance of ASC in determining chemical stability and reactivity is dicussed briefly.     

Fibonacci numbers in the topological theory of benzenoid hydrocarbons and related graphs

Fibonacci numbers are studied with respect to the topological theory of benzenoid hydrocarbons. These numbers are identified as the number of Kekulé structures of nonbranched all-benzenoid hydrocarbons, the number of matchings of paths, the number of independent sets of vertices of paths, the number of nonattacking rooks of certain rook boards, as well as the number of Clar structures of certain benzenoid hydrocarbons. Fibonacci numbers were also identified as the number of conjugated circuits of certain benzenoid hydrocarbons and thus they were also related to the structure-resonance model. Maximal independent sets of caterpillar trees are also shown to be Fibonacci numbers.     

Fibonacci relations. On the computation of some counting polynomials of very large graphs

A definition of a set of Fibonacci graphs is introduced which allows construction of several counting polynomials of very large graphs quite easily using a pencil-and-a-paper approach. These polynomials include matching, sextet, independence, Aihara and Hosoya polynomials. Certain combinatorial properties of Kekulé counts of benzenoid hydrocarbons are given. A relation to a new topological function that counts the cardinality of graph topology [23] is given.Dedicated to Professor Oskar E. Polansky for his enthusiastic support, participation and promotion of chemical graph theory.     

π-Electron currents in fixed π-sextet aromatic benzenoids

In view of different patterns of π-electron density currents in benzenoid aromatic compounds it is of interest to investigate the pattern of ring currents in various classes of compounds. Recently such a study using a graph theoretical approach to calculating CC bond currents was reported for fully benzenoid hydrocarbons, that is, benzenoid hydrocarbons which have either π-sextets rings or “empty” rings in the terminology of Clar. In this contribution we consider π-electron currents in benzenoid hydrocarbons which have π-electron sextets and C=C bonds fully fixed. Our approach assumes that currents arise from contributions of individual conjugated circuits within the set of Kekulé valence structures of these molecules.     

Distances and volumina for graphs

It has long been realized that connected graphs have some sort of geometric structure, in that there is a natural distance function (or metric), namely, the shortest-path distance function. In fact, there are several other natural yet intrinsic distance functions, including: the resistance distance, correspondent “square-rooted” distance functions, and a so‐called “quasi‐Euclidean” distance function. Some of these distance functions are introduced here, and some are noted not only to satisfy the usual triangle inequality but also other relations such as the “tetrahedron inequality”. Granted some (intrinsic) distance function, there are different consequent graph-invariants. Here attention is directed to a sequence of graph invariants which may be interpreted as: the sum of a power of the distances between pairs of vertices of G, the sum of a power of the “areas” between triples of vertices of G, the sum of a power of the “volumes” between quartets of vertices of G, etc. The Cayley–Menger formula for n-volumes in Euclidean space is taken as the defining relation for so-called “n-volumina” in terms of graph distances, and several theorems are here established for the volumina-sum invariants (when the mentioned power is 2). This revised version was published online in July 2006 with corrections to the Cover Date.     

Recognizing Kekuléan benzenoid systems byC-P-V path elimination

In this paper, we define the concept of a canonicalP-V pathP(p _i– _i ) on the boundary of a benzenoid systemH, and prove thatH has a Kekulé structure if and only ifH-P(p _i–v _i) has a Kekulé structure, whereH-P(p _i–v _i) is the graph obtained fromH by deleting the vertices onP(p _i–v _i) . It is also proved that there are at least two canonicalP-V paths in a benzenoid system. By the above results, we give an efficient and simple algorithm, called the canonicalP-V (C-P-V) path elimination, for determining whether or not a given benzenoid systemH has Kekulé structures. IfH is Kekuléan, the algorithm can find a Kekulé structure ofH.Supported by NSFC.     

Applications of caterpillar trees in chemistry and physics

The relations of caterpillar trees (which are also known as Gutman trees and benzenoid trees) to other mathematical objects such as polyhex graphs, Clar graphs, king polyominos, rook boards and Young diagrams are discussed. Potential uses of such trees in data reduction, computational graph theory, and in the ordering of graphs are considered. Combinatorial and physical properties of benzenoid hydrocarbons can be studied via related caterpillars. It thus becomes possible to study the properties of large graphs such as benzenoid (i.e. polyhex) graphs in terms of much smaller tree graphs. Generation of the cyclic structures of wreath and generalized wreath product groups through the use of caterpillar trees is illustrated.     

Benzenoid links

In this paper, we study new configurations of benzenoid hydrocarbons, called benzenoid links. Roughly speaking, a primitive corofusene is a closed narrow hexagonal ribbon with out-of-plane curvature 0. A primitive corofusene or the union of disjoint primitive corofusenes in \mathbbR³{\mathbb{R}^{3}} is called a benzenoid link. In this paper, we determine the minimum number of hexagons needed for a nontrivial benzenoid link in different senses. We also determine the structures of the smallest and the second smallest nontrivial benzenoid links of different types and their numbers of Kekule structures. We list all the benzenoid Hopf links of type III with 22–25 hexagons by their canonical codes in the appendix.     

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.     

Balancing the Pauling bond orders in Kekuléan benzenoid hydrocarbons

We consider a cutting of the molecular graph B of a Kekuléan benzenoid molecule into two disconnected subgraphs, S and the other, by deleting from B certain edges. It is required that both subgraphs remain Kekuléan. The edges involved in this cutting are classified as starred and unstarred. A starred edge is incident to a starred carbon site of the subgraph S, whereas an unstarred edge to an unstarred carbon site of S. The following regularity is established: for any above-described cutting of any Kekuléan benzenoid system, the sum of the Pauling bond orders of the starred edges is equal to that for the unstarred edges.