Acyclic graph

The Wiener index was originally defined only for acyclic graphs and was initially called the path number [6]. "The path number, W, is defined as the sum of the distances between any two carbon atoms in the molecule in terms of carbon-carbon bonds". Hosoya extended the Wiener index and defined it as the half-sum of the off diagonal elements of a distance matrix D in the hydrogen-depleted molecular graph of Eq, (15), where dij is an element of the distance matrix D and gives the shortest path between atoms i and j. 

One can also see that the Gordon-Scantlebury N2 index 19) can similarly be expressed as half the number of distances of length two, but for acyclic graphs only ... 

It is seen that the Smolenskii term X2 is identical to the N2 index, while the term X3 is identical (in the case of acyclic graphs only) to the polarity number p. 

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

For acyclic graphs only, if in the above formula only distances between endpoints are taken into account, the related endpoint mean square topological index Df1 results. 

Alternatively, for acyclic graphs Z can be defined as the sum of the absolute values of coefficients in the characteristic polynomial PH(G, x) ... 

N is the number of atoms, A and E are the adjacency and unit matrix, respectively, while s is the largest number of edges disconnected to each other in the acyclic graph. Thus, for Gx one obtains ... 

Fig. 2. Examples of simple bipartite graphs, (a) Acyclic graph for the reaction Aj - A2 A (b) cyclic graph for the reaction A A2 (c) graph for the irreversible...

Balaban S, Filip PA, Ivanciuc O, Computer generation of acyclic graphs based on local vertex invariants and topological indices derived canonical labelling and coding of trees and alkanes, J. Math. Chem., 11 79-105, 1992. 

A fourth system of mathematical interest, but of little historical or chemical interest, is the Matula system for naming rooted trees (acyclic alkanes) [10] and its extension to all graphic representation of moieties [11-15], The output of this system is a single very large integer, which can be decoded into a unique acyclic graph. For example, the alkane depicted in Figure 16 has as its Matula name 548,813,133,611. ... 

Only for acyclic graphs, after special rearrangment, does the formula take the form ... 

Defined only for acyclic graphs and substituents, it is calculated as -> total information... 

For any acyclic graphs two general rules are observed i) the power of x decreases by two, and ii) the absolute values of T (G", x) coefficients are equal to the coefficients of the - Z-counting polynomial Q (G, x). Therefore, the characteristic polynomial for an acyclic graph is given by ... 

It is worth pointing out that the symmetric Cluj-distance matrix CJD is identical to the Wiener matrix W for acyclic graphs obviously, the corresponding - graph invariants coincide. 

For acyclic graphs, the matrix CJA is equal to the symmetric Cluj-distance matrix CJD and therefore to the Wiener matrix W, while it is different from the -> Szeged matrix SZ. 

For acyclic graphs, CJDp = CJAp = WW = Dp SZDp, where WW is the -> hyper-Wiener index. Dp the hyper-distance-path index, and SZDp the - hyper-Szeged index, while for cyclic graphs all these descriptors are different. 

This definition is exactly the opposite of the definition of the - distance matrix whose off-diagonal elements are the lengths of the shortest paths between the considered vertices. However, the distance and detour matrices coincide for acyclic graphs, there being only one path connecting any pair of vertices. 

For acyclic graphs, the hyper-detour index ww is equal to the index Dp obtained from the distance-path matrix Dp and to the WW obtained from the - Wiener matrix W. 

It must be noted that for acyclic graphs the following relation holds ... 

For acyclic graphs the hyper-distance-path index Dp coincides with the - hyper-Wiener index WW derived from the - Wiener matrix and with the -> hyper-detour index derived from the detour-path matrix. Moreover, it was proposed as an extension of the hyper-Wiener index for any graph [Klein et al., 1995],... 

A molecular branching index was proposed for acyclic graphs, based on the double invariant approach and called - AA/ branching index. A calculation example [Randic, 1997d Randic, 1998a] for 2-methylpentane is given in Box D-7, where the symbol " p represents a path of length m. 

For acyclic graphs the topological edge distance can be calculated by the following formula , ... 

It can be observed that P is the adjacency matrix A and that for acyclic graphs each of the above defined path matrices is coincident with the corresponding sparse matrix of the distance matrix. 

For acyclic graphs, the expanded distance matrix can be obtained simply as ... 

The Harary index and hyper-Harary index, defined only for acyclic graphs, are obtained from, respectively, the P -order sparse -> reciprocal Wiener matrix W ... 

---