Cyclic graphs

The cyclomatic number must not be confused with the graph - cyclicity CA. Thus, for example, naphthalene has a cyclomatic number equal to two (the two benzene rings) and a cyclicity equal to three (the two benzene rings plus the more external 10-atom ring). 

The edge-cycle incidence matrix is a rectangular unsymmetrical matrix vhose rows represent the edges and columns the circuits of the graph. This matrix of dimension Bx, where is the graph cyclicity, is formally defined as... 

Klein, D.J. and Ivanciuc, O. (2001) Graph cyclicity, excess conductance, and resistance deficit./. Math. Chem., 30, 271-287. 

The molecular index based on the resistance-distance/vertex-distance matrix is called the Kirchhoff-sum index (Babic et al 2002). Matrices D/Q and QAD have been used to study the graph cyclicity (Klein and Ivanciuc, 2002) ... 

The minimum number of cycles is given by the nullity or Frerejacque number ( ) according to Eq. (5). It is the difference between the number of nodes a = atoms) and the number of edges h = bonds). The value of 1 stands for the number of compounds considered (here, one compound). This minimum number corresponds to the munber of chords. These are defined as nodes that turn a cyclic graph or structure into an acyclic one. 

Other techniques that work well on small computers are based on the molecules topology or indices from graph theory. These fields of mathematics classify and quantify systems of interconnected points, which correspond well to atoms and bonds between them. Indices can be defined to quantify whether the system is linear or has many cyclic groups or cross links. Properties can be empirically fitted to these indices. Topological and group theory indices are also combined with group additivity techniques or used as QSPR descriptors. 

Fig. 2.9 The state transition graph Gc, computed for a Tdim lattice consisting of iV = 4 points (with periodic boundary conditions), and totalistic rule T2 . The vertices labeled ti represent transient configurations those labeled cd represent cyclic states, and give rise to the formal cycle cum decomposition C[ j =[3, lj-f[2,2].

Figures 3.38 and 3.39 show typical space-time patterns generated by a few r = 1 reversible rules starting from both simple and disordered initial states. Although analogs of the four generic classes of behavior may be discerned, there are important dynamical differences. The most important difference being the absence of attractors, since there can never be a merging of trajectories in a reversible system for finite lattices this means that the state transition graph must consist exclusively of cyclic states. We make a few general observations.

Although we will not worry about the precise tree structure, we note that for all graphs, and therefore all additive rules, every cyclic state is a root of a tree which is isomorphic to the null tree (the one terminating on S = 0) ... 

Table 5.2 Number of topologically distinct connected graphs ) ), number of cyclic equivalence classes Q, maximal numbers of possible cycle sets Cot and Ct for OT and T rules, respectively, and the maximal number of possible distinct topologies of the state transition graph, calculated for graphs with size fV=5,6,..., 12 in T 2. ...

Since we will be dealing with finite graphs, we can analyze the behavior of random Boolean nets in the familiar fashion of looking at their attractor (or cycle) state structure. Specifically, we choose to look at (1) the number of attractor state cycles, (2) the average cyclic state length, (3) the sizes of the basins of attraction, (4) the stability of attractors with respect to minimal perturbations, and (4) the changes in the attractor states and basins of attraction induced by mutations in the lattice structure and/or the set of Boolean rules. 

Consider an order W system and a random function 4> which maps each of the H = 2 possible binary states Si to unique successor states Sj = cyclic structure of the corresponding state transition graph... 

If the cyclic group 2 is associated with the coronas of order k k 1, 2,. ..) then two graphs which are congruent according to the definition of Sec. 34 are called "planar nondistinct", while jf they are noncongruent in this sense they are called "planar distinct". 

BalA76a Balaban, A. T. Enumeration of Cyclic Graphs. Chap. 5. 

Figure 6. Real full line) and apparent (broken lines) relations in the graph E versus AS, hydrolysis of cyclic anhydrides (202).

In the foregoing discussion the properties of the incidence matrix and the cycle matrix were illustrated in terms of a cyclic digraph, but the results on the ranks of these matrices actually hold true for any connected digraph with N vertices. For an undirected graph, M and C contain only 0 and 1 (sometimes referred to as binary matrices), mathematical relations of identical form are obtained except that modulo 2 arithmetic2 is used instead of ordinary arithmetic. The ranks of M and defined in terms of modulo 2 arithmetic are JV — 1 and C, as before, and Eqs. (10) and (11) are modified to read... 

Randles-Sev ik plot A graph derived from the Randles-Sev5ik equation, showing a plot of the cyclic voltammetry peak height Ip, (as y ) as a function of (as x ), where v is the scan rate. 

The "cyclic order" Cjj of a molecule -or of the corresponding graph- is equal to... 

Figure 51. Cathodic and anodic stability of LiBOB-based electrolytes on metal oxide cathode and graphitic anode materials Slow scan cyclic voltammetry of these electrode materials in LiBOB/EC/EMC electrolyte. The scan number and Coulombic efficiency (CE) for each scan are indicated in the graph. (Reproduced with permission from ref 155 (Eigure 2). Copyright 2002 The Electrochemical Society.)...

Each graph has a certain cyclic order n. This order is equal to the number of edges minus the number of vertices plus one3). The maximum number of circuits in the graph is equal to 2 — 1. 

Hosoya29) extended the Altenburg polynomial (originally devised for acyclic graphs) to cyclic graphs. 

---