A RELATION BETWEEN BOND AND VERTEX ERASURES OF GRAPHS

	Sign In Sign-Up

Milan Kunz

Abstract

The relation between the number P´ of paths in edge erased subgraphs of trees and their Wiener number W, P´ + W = n{n - 1}²/2, which was found recently by Randic, is explained as the complementarity of bond and vertex erasures of trees and simple cycles. Using walk matrices W and their complements, there can be defined bipartite graphs in joined space of bonds and vertices to bond and vertex erasures.

1. Introduction

Ulam subgraphs conjecture about sets of vertex erased graphs holds interest in the connection to the characteristic polynomials of graphs. Chemical interpretation of vertex erasures is rather low. From a molecule, one atom can be removed with all its bonds in one reaction step only if it is a terminal atom or a group in hydrogen depleted skeletons. Bond (edge or arc) erasures are more interesting for chemists, they represent molecules in which only one bond is missing. Therefore it is interesting to study effects of edge erasures on graphs.

The possibilities of application of the edge erasure technique were studied by Gutman and Shalabi. Recently Randic defined a new topological index based on sets of all bond erased subgraphs.

In this paper we will show a relation of between acyclic polynomials of bond erased subgraphs to the acyclic polynomial of the parent graph, we explain the relation of the Randic index P´ to the Wiener index W at acyclic graphs and we discuss differences between vertex and bond erasures.

2. Bond difference of the acyclic polynomial

The sum of characteristic polynomials S P of Ulam subgraphs D(G) is the difference of the characteristic polynomial P(G) of the parent graph G

S P[D(G)] = DP(G) (1)

Ulam subgraphs are differences of the parent graph according to the number of vertices n which appears as the power n of the characteristic polynomial. Subgraphs have (n - 1) vertices and their terms x^k are differences of corresponding terms of the parent polynomial:

D(a x^k) = a kx^(k-1) .

Edge erased subgraphs contain n vertices and therefore their characteristic polynomials have the same degree as the polynomial of the parent graph. There are m subgraphs, one for each edge. At trees these subgraphs have 2 components and their set coincides with Ulam subgraphs, they are only divided regularly into (n - 1) sets instead into n sets with 1 till (n-1) components. It is possible to rearrange subgraphs into Ulam groups, each containing v components, but it were necessary to find a general algorithm. But there exists a relation between the sums of acyclic polynomials of edge erased graphs and the acyclic polynomial of the parent graph which can be formulated analogously to (1). Recall that the acyclic polynomial counts k-tuples of isolated bonds in a graph and that at trees, it coincides with their characteristic polynomial.

Theorem: The sum of acyclic polynomials of the edge erased subgraphs D of a tree T is a difference of the acyclic polynomial of the parent graph according to the number m of edges

S P[D(T)] = DP(T)(2)

This is accurate till the integration constant provided that the differentiation is done by multiplication of the terms counting k tuples of isolated edges by (m-k).

In a difference DP(T) of the acyclic polynomial the coefficients at x are multiplied by (n-k), where k is the number of isolated edges in the acyclic polynomial. Otherwise, when the sum of acyclic polynomials of edge erased subgraphs is integrated, the sum of corresponding terms is divided by these coefficients. For example:

Tree	Edge erased subgraphs	Polynomials
------------		x⁴ -3x² + 1
	*--------*	x³ -2x
	--------	x³ -2x + 1
	--------**	x³ -2x
		Sum 3x³ -6x + 1

The first term of the sum must be divided by 3, the second by 2 for obtaining the terms of parent polynomial .

For stars, which edge erased subgraphs are all the star with (n -1) vertices and one loose vertex, the relation (2) can be formulated generally: The parent polynomial is

xⁿ - (n - 1)x^n-2.

The sum of edge erased subgraphs polynomials is

(n- 1)[x^n-1 -(n-2)x^n-2].

Here the dividing coefficients appear explicitly.

The acyclic polynomial of 3 isolated edges is

P(3 K₂) = x⁶ - 3x⁴ + 3x² -1.

The 3 edge erased subgraphs of 3 K₂ have polynomials

P(2K₂ + K₁) = x⁶ - 2x⁴+ x².

Here the integration constant vanished because no subgraph contained the complete 3-tuples of 3 isolated vertices.

The proof of the theorem is trivial. Each k tuple is not counted in exactly k polynomials of edge erased subgraphs in which the edge necessary to form the given k tuple is missing. Therefore, the multiplicities of k all tuples in subgraphs are (m-k). These coefficients appear as the differentiation coefficients at corresponding terms of the acyclic polynomial in the sum of acyclic polynomials of edge erased subgraphs.

3. Topological index P´

Randic defined [1] a novel bond descriptor P´/P as the ratio of the number of paths P´ in all subgraphs G´ of a graph G which an edge is erased and the number of paths P in the parent graph. He was surprised that the descriptor P´/P although defined without explicit references to the Wiener number W is simply related with this number, at least in the case of acyclic connected graphs.

The explanation is trivial. We can apply walk or path matrices W which are quadratic roots of the inverses of quadratic forms SS^T or GG^Tof the incidence matrices S or G of oriented and unoriented trees respectively [2]. The definition of the Wiener number W is that it is the sum of n{n - 1}/2 distances between n vertices of a graph [3]. A walk or path matrix W is the incidence matrix of n{n -1}/2 walks or paths i with {n -1} bonds j of a tree. The elements w_ij are +1 or -1, if the bond j is in the walk or path i and zero otherwise. The sign depends on the orientation of an arc in the walk or on the ordering of an edge in the path, but for our discussion we need not bother with them. We will work with quadratic forms W^TW , on their diagonals sum of squares appears as w_j numbers, counting how many times the bond j was used in all walks or paths. The differences

p_j =n{n -1}/2 - w_j

is the number of walks or paths in the subgraph G´ of the graph G in which the bond j is erased .

4. Bond and vertex erasures

A set of n Ulam subgraphs d_j{G} contains n subgraphs. In each of them, v_j bonds incident with the vertex j are erased. This gives 2 complete graphs G. Therefore the sum of all subgraphs is {n -2} multiple of the graph G. In the set of m bond erased subgraphs {m -1} bonds are erased which together form the parent graph. The multiplicity of all bond erased subgraphs is thus {m - 1}.

At trees m = {n -1} and the bond and vertex erasures give the same multiplicity {n - 2} of bonds in both sets. At simple cycles bond erased subgraphs have multiplicity {n -1} and vertex erased subgraphs {n -2}. Bond erased subgraphs are linear chains L_n and vertex erased subgraphs L_n-1. Both sets have different contents and are no more comparable.

But there is still another coincidence. Twice the Wiener number W was found to be the trace of Eichinger matrices E of trees. Eichinger matrices are obtained either as sums of inverses of vertex erased submatrices d_jS^TS of Laplace-Kirchhoff matrices

E = {d_jS^TS}^-1,

d_jM being a matrix M which j-th row and column are deleted. Or the matrix E is obtained at the LaValiere-Frame-Faddeyev technique of finding the coefficients of the matrix polynomial [4]. The Laplace-Kirchhoff matrix S^TS has just one zero eigenvalue and its last but one Frame matrix Bn-2 must give S^TSB_n-2 = nI - JJ^T,where I is the unit diagonal matrix and J is the unit vector column. Then

B_n-1 = -JJ^T and S^TSJJ^T = 0.

Vertex erasures at matrices give {n -2} off-diagonal elements and {n -1} diagonal elements. At simple cycles, d_jS^TS coincides with the matrix SS^T of the linear chain with n vertices and {n - 1}bonds which spectrum is identical with the spectrum of bond erased subgraphs of the cycle which is also the linear chain with n vertices.

5. Bipartite path /walk/ graphs.

If we write a walk matrix W and its transpose W^T in the block form, we obtain an adjacency matrix of a bipartite graphs in the joined space of n{n -1}/2 paths and {n - 1} bonds

A{W}= -

W^T

The eigenvalues of A{W} are squared eigenvalues of the matrix W which are inversed eigenvalues of the Laplace-Kirchhoff matrix [5]. Now, we can define the complementary bipartite graph to the graph with the adjacency matrix A{W} having the adjacency matrix in the block form

A{P´}=

P´

(P´)^T

where

P´ = Jn{n-1}/2J^T_n-1 - W.

The definition is good only at linear oriented chains which arcs have equal orientations, otherwise it is complicated by signs. The elements of the adjacency matrix A in the Laplace-Kirchhoff matrix have all negative signs without regard of arc orientations. From all walk and path matrices the positive signs can be obtained only at linear chains [2] and at matrices with unequal signs the complementary graphs have multiple bonds [4].

4. Discussion

Heissenberg admitted :"Then I did not know what a matrix was " [6]. We must ask if we know it really even now? Compared with the long history of mathematics matrices are relatively a recent invention. They were studied as as tools transforming one vector into another and everything started with determinants. If it was zero, interest vanished.

In chemistry matrices are used as maps of molecules and their assemblies [7,8]. We can be sure that many known relations of matrix invariants with physicochemical properties of molecules can not be accidental. They must express properties of molecules themselves and therefore matrices are models of molecules.

Chemical matrices seem to be rather elementary structures but despite we do not understand them or we are unable to exploit all their algebraic properties.

In my paper about connectivity indices [9], I proved a matrix identity

J^TA³J = J^TVAVJ ,

where V is the diagonal matrix of vertex degrees vj, by direct counting of corresponding paths in the product VAV and comparing them with A³. But the proof can be made simple using bracket rules

J^T{VAV}J = {J^TV}A{VJ}

and inserting the identities

J^TV =J^TA and VJ =AJ.

But can we compare

J^TV^1/2AV^1/2J = J^TA²J ?

J^TV⁰AV⁰J= J^T

J^TV^-1/2AV^-1/2J = J^TA⁰J ?

All identities are true for regular graphs. For the Randic index it was already shown [9], for V^1/2A^1/2V is the proof similar. In each row of the product vj, elements vj are. Together they give in each row as sums v²_j. If we insert in the center of the matrix product of the last identity the Laplace-Kirchhoff matrix, the product normalizes its diagonal

V^-1/2S^TSV^-1/2 = I - V^-1/2AV^-1/2.

We must ask if the Randic index is derived from the adjacency matrix A or if it corresponds to normalized eigenvalues of the Laplace-Kirchhoff matrix S^TS.

Similarly, the Balaban index J is constructed as the product of the adjacency matrix with diagonal matrices Q^-1/2 from both sides, where qj are distances of the vertex j to all other vertices. But these distances are derived from the other quadratic form of walk matrices WW^T [4] and their sum is sum of inversed eigenvalues of the Laplace-Kirchhoff matrix. Nobody studied what such multiplication makes with eigenvalues.

Many authors tried orthogonality of different topological indices [10]. But either two topological indices characterize a whole molecule and then they are both differently rotated forms of one matrix vector or they express only some of its properties and then they must be complementary, at least from a part. If a matrix vector is inverse to the other, then they can not be orthogonal unless one has at least one zero eigenvalue and the other is infinite. But such solutions are unacceptable and we must replace orthogonality by another properties, as in the case of bond and edge erasures by the complementarity inside of complete bipartite graphs.

There are two ways how to approach our problems. One possibility is based on abstract ideas of metric spaces and exploits sophisticated techniques of formal mathematics [11]. The other is founded on real objects as molecules are and graphs seems to be. It tries to investigate all hidden niches of the vector space and their secrets. Its methods are cumbersome but they give insight how the space we live in is built. There appear several surprises because properties of high dimensional spaces are contraintuitive [11].

The incidence matrices S and G have just two unit elements in each row. Despite it their wreath product symmetry is complicated enough to keep us busy for long time before we learn to spell all God´s names.

Acknowledgement

I would like to thank Professor Milan Randic and other for sending me numerous reprints.

References

[1] M. Randic, J. Math. Chem., 7 {1991}155.

[2] M. Kunz, Collect. Czech. Chem. Commun., 54 {1989}2148.

[3] H. Wiener, J. Amer. Chem. Soc., 69 {1947} 17.

[4] M. Kunz, J. Math. Chem., 13{1993} 145.

[5] B. Mohar in Stud. Phys. Theor. Chem. 63 MATH/CHEM/COMP 1988 ed. A. Graovac/ Elsevier, Amsterdam, 1989/1.

[6] W. Heissenberg in The Physicist´s Conception of Nature,ed. J. Mehra /D. Reidel, Dortrecht, 1968, 267.

[7] J. Dugundji, I. Ugi, Topics Curr. Chem. 39 {1973} 19.

[8] D. H. Rouvray in Chemical Applications of Graph Theory ed. A. T. Balaban /Academic Press, London, 1976, 175.

[9] M. Kunz, Coll. Czech. Chem. Commun. 55 {1990} 630.

[10] K. Kovacevic, D. Plavsic, N. Trinajstic, D. Horvat in Studies in Phys. Theor. Chem. 63 MATH/ CHEM/ COMP 1988, ed. A.Graovac /Elsevier, Amsterdam, 1989, 213.

[11] P. G. Mezey in Studies in Phys. Theor. Chem. 51, Graph Theory and Topology ed. R. B. King, D. H. Rouvray / Elsevier, Amsterdam, 1987, 91.