A RELATION BETWEEN BOND AND VERTEX ERASURES OF GRAPHS
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/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 xk are differences
of corresponding terms of the parent polynomial:
D(a xk) = 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 |
*----*----*----*
|
|
x4
-3x2 + 1 |
|
**----*----* |
x3
-2x |
|
*----**----* |
x3
-2x + 1 |
|
*----*----** |
x3
-2x |
|
|
Sum
3x3 -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
xn - (n - 1)xn-2.
The
sum of edge erased subgraphs polynomials is
(n- 1)[xn-1 -(n-2)xn-2].
Here
the dividing coefficients appear explicitly.
The
acyclic polynomial of 3 isolated edges is
P(3
K2) = x6 - 3x4 + 3x2 -1.
The
3 edge erased subgraphs of 3 K2 have polynomials
P(2K2
+ K1) = x6 - 2x4 + x2.
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 SST
or GGT of
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 wij 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 WTW , on their diagonals sum of
squares appears as wj numbers, counting how many times the bond j
was used in all walks or paths. The differences
pj =n{n -1}/2 - wj
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, vj
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 cyclles bond erased subgraphs have
multiplicity {n -1} and vertex erased subgraphs {n -2}. Bond erased subgraphs
are linear chains Ln and vertex erased subgraphs Ln-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 djSTS of
Laplace-Kirchhoff matrices
E =
{djSTS}-1,
djM 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 STS has just one zero
eigenvalue and its last but one Frame matrix Bn-2 must give STSBn-2
= nI - JJT,where I is the unit diagonal matrix
and J is the unit vector column. Then
Bn-1 = -JJT and STSJJT
= 0.
Vertex
erasures at matrices give {n -2} off-diagonal elements and {n -1} diagonal
elements. At simple cycles, djSTS coincides
with the matrix SST
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 WT
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}= - |
0 |
W |
WT |
0 |
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´}= |
0 |
P´ |
(P´)T |
0 |
where
P´ = Jn{n-1}/2JTn-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
JTA3J = JTVAVJ
,
where
V is the diagonal
matrix of vertex degrees vj, by direct counting of corresponding paths in the
product VAV and
comparing them with A3.
But the proof can be made simple using bracket rules
JT{VAV}J = {JTV}A{VJ}
and
inserting the identities
JTV =JTA
and VJ =AJ.
But can we compare
JTV1/2AV1/2J = JTA2J
?
JTV0AV0J= JT
JTV-1/2AV-1/2J = JTA0J ?
All
identities are true for regular graphs. For the Randic index it was already
shown [9], for V1/2A1/2V is the proof similar. In each
row of the product vj, elements vj are. Together they give in each row as sums
v2j. 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/2STSV-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 STS.
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 WWT [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.