Milan Kunz

Laplace-Kirchhoff matrices, perturbed by rooting a vertex by the unit element e₁₁, have true inverses, which are combinations of unit matrices and partial inverses. The inverses are quadratic forms of matrices in the lower triangular form. At trees, they determine path coordinates of vertices. The resistance distances are obtained by a graph algorithm.

The Laplace-Kirchhoff matrices are quadratic forms S^TS of incidence matrices of oriented graphs S, where s_ij = -1, if the arc i goes from the vertex j, s_ij = 1, if the arc i goes in the vertex j, s_ij = 0 otherwise. They have one zero eigenvalue and therefore they are singular. They have generalized inverses (1), in fact, there are infinite many generalized inverses (2). One from these (3), the Eichinger matrix E, can be found summing up partial inverses obtained by deleting j th row and column

If the Laplace-Kirchhoff matrix is n-dimensional, then the other quadratic form at trees is (n -1)- dimensional and is not singular. The inverse (4) was formulated as the quadratic form of the path matrix W, which elements are +1, if the arc j has the same orientation as the path i, -1, if the arc j has the opposite orientation, and 0, if the arc j is not on the path.

Graph theory deals with a problem of coding of rooted trees (5). These impractical results contained implicitly a simple solution of the given problem.

Only one unit element corresponds to each arc in path and walk matrices W, the arc (or edge) itself. The columns match with arcs (edges). In the descendant code, a tree is characterized by (n-1) paths from the root. There can be n roots and therefore the whole set of codes to each tree has n(n-1) rows, which is twice of the path matrix W. The root code is thus a submatrix of the matrix W. The code is defined in the subspace of vertices, and each path is coded by all its vertices (as columns), including its both ends. Moreover, the root itself is induced as the unit element e₁₁ in the first row. The convention is, that arcs are always proceding from the root. The resulting code has the lower triangular form and the unit matrix I is on the diagonal. At trees, the first column is the unit matrix J, but the code can be used for forests, too.

The inverses of code matrices W are in the lower triangular form, and the unit matrix I is on the diagonal. The off diagonal elements are -1, if the vertex j is the child of the vertex i, and 0 otherwise. Since each child has only one parent, only two nonzero elements are in each row, except the first one, and this part of the matrix W is the incidence matrix S of the given tree.

For our purposes, it is necessary to allow any vertex to become the root without changing the indexes. For it, we define the path matrix as vertices on the path between the vertex i and the root j. It is only a permutation of the lower triangular form. For example

The row with the unit element is inserted into the incidence matrix and all arcs are oriented from the vertex 3.

Since both matrices are mutually inverse, their transpose and quadratic forms must have this property taken in proper order. This leads to the relation

This relation is true not only for the trees, but also for all connected graphs. Their incidence matrices S with the unit element e_ij are not square matrices, but rectangular m,n matrices, m>n. Therefore, they do not have inverses, but their quadratic forms S^TS have, since they are overdetermined. It will be shown for the case of simple cycles C(n).

The diagonal elements of the quadratic form W^TW give resistance distances of the vertices from the root (2,6). They can be calculated directly as (1/d_l + 1/d_r) , where d_l and d_r are left and right distances from the root, respectively. The third possibility, how they can be calculated, is the asymmetric triangular decomposition. It is instructive at cycles. It shows, how fractions in the triangular decomposition can be reached from the path matrix. E. g., for C(5)

The elements of the matrices are (n - i)/(n - j - 1) and (n-j)/(n-i), respectively.

Multiple bonds can be expressed in the incidence matrices S by repeating rows. This multiplicity k of an arc will decrease the code of the vertex, the arc is going in, and as 1/k. This corresponds to conductivity, e. g. 1,2-propen has three codes (square roots are not shown) corresponding to roots 1, 2, 3, respectively:

Some physicochemical properties of molecules are connected with specific atoms. They are rooted in them, and the property is determined by the surrounding of the atoms.

If the chemical shift of all atoms is determined positively by the first and second neighbors and negatively by the third neighbors, then the sum will show roughly the same trend (9) as an index combining their numbers.

Boiling points of alkanes are physicochemical properties of whole molecules. They correlate well with the sum of distances, the Wiener index. This index fails at monosubstituted alkanes, as alcohols are (10).

An explanation could be, that all carbon atoms of alkanes have equivalent weights as roots. Hydroxyl group is a dominant root hawing the greatest effect on the boiling point. This hypothesis can be checked by simple calculations (in Table 1), exploiting walks to carbon atoms from the hydroxyl group as descriptors. The corrective term is formed by the CH group in any position in the chain (difference between predicted and calculated value for isopropyl alkohol).

Table 1. Boiling points of some alcohols

The results are inferior to the results obtained by sophisticated techniques (10, 11), but are better then with the Wiener index, even after its splitting into the Altenburg polynomial and inserting in the analogical matrix as in Table 1.

There are n(n-1) paths from n roots to other vertices of connected graphs. In the walk matrices W, only a half of them was used, the second half being redundant. The walk (path) matrices W can be differentiated, similarly as graph themselves, by choosing a vertex as the root. Walk (path) matrices W can be formulated in the space of bonds as well as in the space of vertices. They are rooted in the space of vertices by the unit element.

Each from n partial differences determines some properties of the graph and the corresponding molecule. The quadratic rooted form gives a perturbed Laplace-Kirchhoff matrix, which has a true inverse. Its eigenvalues correlate with undisturbed Laplace-Kirchhoff matrices, as preliminary checks show. At large graphs, the induced error will be relatively small, and a rooted inverse could replace the sum of all n partial inverses, the Eichinger matrix E, which eigenvalues are inverted eigenvalues of the corresponding Laplace-Kirchhoff matrix (except the zero eigenvalue). The inverse has resistance distances (plus 1 as the perturbation) on its diagonal.

The distances of nodes from the roots are evaluated in the DARC topological analysis, of course (e. g. refs 12 and 13). The reported results are not new, and they give a better insight, how different elements of the topological space are related. Since the mathematical techniques used are elementary, they can help students to understand associations.

If topological distances are inverse elements of the Laplace-Kirchhoff matrices, then geometrical distances must be related with valences in molecules, especially in crystals. This task remains to be an open problem.

REFERENCES

1. Kunz M. Moebius Inversion of the Ulam Subgraphs Conjecture J. Math. Chem., 1992, 11, 297-305.

2. Klein D.J.; Randic M. Resistance Distance. J. Math. Chem., 1993, 12, 81-95.

3. Kunz M. Inverses of Perturbed Laplace-Kirchhoff and Some Distance Matrices. MATCH, 1995, 32, 221-234.

4. Kunz M. Path and Walk Matrices of Trees. Coll.Czech.Chem. Commun., 1989, 54, 2148-2155.

5. Aissen M.; Shay B. Numerical Codes for Operation Trees. In Graph Theory and Its Applications: East and West, Capobianco, M. F.; Guan, M.; Hsu, D. F.; Tian, F., Eds., Annals of the New York Academy of Sciences, 1989, Vol. 576, p. 1.

6. Kunz M. An Equivalence Relation between Distance and Coordinate Matrices, MATCH, 1995, 32, 193-204.

7. Grant D. M.; Paul E. G. Carbon-13 Magnetic Resonance II. Chemical Shifts for Alkanes. J. Amer. Chem. Soc., 1964, 86, 2984-2990.

8. Lindenman P. L.; Adams J. Q. Carbon-13 Nuclear Magnetic Resonance Spectrometry. Chemical Shifts for the Paraffins through C₈. Anal. Chem., 1971, 43, 1243-1252.

9. Miyashita Y.; Okuyama T.; Ohsako H.; Sasaki S. Graph Theoretical Approach to Carbon-13 Chemical Shift Sum in Alkanes. J. Amer. Chem. Soc., 1989, 111, 3469-3470.

10. Randic M. On Computation of Optimal Parameters for Multivariate Analysis of Structure-Property Relationship. J. Comput. Chem., 1991, 12, 970-980.

11. Smeeks F. C.; Jurs P. C. Prediction of Boiling Points of Alcohols from Molecular Structure. Anal. Chim. Acta., 1990, 233, 11-119.

12. Dubois J. E.; Carabedian M.,;Ancian B. Automatic Structural Elucidation by Carbon-13 NMR DARC-EPIOS method. C. R. Seances Acad. Sci. Ser. C, 1980, 290, 369-372.

13. Razinger M.; Chretien J. R.; Dubois J. E. Comparison of Distances in Different Topological Descriptors. Vestn. Slov. Kem. Drus., 1986, 33, 49-68.