|
|
About Additivity of Eigenvalues of the Graph Matrices
Milan Kunz
Introduction
It is well known that the Laplace-Kirchhoff matrices STS of oriented graphs have (n-1) nonzero eigenvalues. Both quadratic forms STS and SST have the same eigenvalues. Therefore, matrices SST of trees are nonsingular, and have true inverses, which I defined as walk matrices WTW. Moreover, matrices STS have generalized inverses E, defined as the sum of partial inverses of differences
S
(JSTS)-1,or the decomposition into the Ulam subgraphs (the set of n subgraphs, each with one eliminated vertex and its adjacent arcs). It follows that the spectra of the Laplace-Kirchhoff matrix of a graph G and its complementary graph G (G + G = K) are complementary, too.
The purpose of this note is to find relations for the analogue of the Laplace-Kirchhoff matrix of unoriented graphs GTG, and the other quadratic form SST. Recall that the elements sij = -1, if the arc starts in the vertex j, sij =1, if the arc ends in the vertex j, sij = 0 otherwise, and gij = 1, if the edge starts or ends in the vertex j, sij = 0 otherwise. Moreover
STS = V - A
GTG = V + A,
where = V is the diagonal matrix of the vertex degrees and A is the adjacency matrix, aij = 1, if the bond starts or ends in the vertex j, and
SST = 2Im - AL
GGT = 2Im + AL
where Imis the unit diagonal matrix and ALis the adjacency matrix of the corresponding line graph.
The incidence matrix of the complete unoriented graph GT can be written in the block form similarly as the incidence matrix of the complete oriented graph ST in the transposed form as
G Tn-1 | I |
0 | J T |
where I is the unit diagonal matrix, JT is the unit vector- row.
Its quadratic forms have forms
GTG =
S TS + I | J |
J T | n-1 |
GG
T=GG T | G |
G | I + JJ T |
Evaluating directly, we find that the eigenvalues are
(2n -2), (n -2)n-1.
Since STS + GTG =2(n -1)Ia, the sum of eigenvalues of S and G are additive, too. S has (n - 1) eigenvalues equal n and one zero eigenvalue. Thus
| (2n -2) | (n -2) | (n -2) | (n-1) times |
0 | nn-1 | nn-1 | (n-1) times | |
S | (2n -2)n | (2n -2)n | (2n -2)n | (n-1) times |
The question is, if such a complementarity is true for all regular graphs. The eigenvalues must be
[vi +/-
Since it is possible to choose the orientation of arcs at bipartite graphs in such a way, that arcs meet always head-head or tail-tail, all signs in the quadratic form SST can be positive, both SST and
GGT = 2Im + AL.
Thus the matrices bipartite graphs have the same eigenvalues. This is obvious, if the spectrum is symmetrical.
In the quadratic form SST a bundle of (n-1) arcs appears to which only one nonzero eigenvalue belongs. They form a star S which eigenvalues are n, 1(n-1). They add to the previous eigenvalues as
n-1 | n-1 | ..... | 0 | 0 | ... |
1 | 1 | ..... | n | 0 | ... |
n | n | ..... | n | 0 | ... |
There exist the additivity of the eigenvalues the Laplace-Kirchhoff matrices of a graph G and its complementary graph (K-G), where K is the complete graph.
The additivity of the eigenvalues of graphs which can be expressed as the sum of the star graph and the subgraph has the consequence that leads to the eigenvalues of such a graph are the sum of eigenvalues of both subgraphs.
For example:
The complete graph K(4) can be decomposed as: K(4) = S(4) + C(3).
The eigenvalues:
4, 4, 4, 0 = 4, 1, 1, 0 + 0, 3, 3, 0.
Graph G = K(4) - S(3) has the eigenvalues: 4, 3, 1, 0. This is the sum:
4, 1, 1, 0 + 0, 2, 0, 0.
The eigenvalues: 4, 3, 1, 0 are formed in its turn by the sum of two linear chains L(3) with the eigenvalues: 3, 1, 0, 0:
3, 0, 1, 0, + 1, 3, 0, 0 = 4, 3, 1, 0.
The sum of the eigenvalues of the complete graph is n(n – 1). It has n(n – 1)/2 arcs, therefore, it can be decomposed into n(n – 1) complete graphs K(2) which eigenvalues are 2.
The decomposition of the complete graph into subgraphs is a necessary condition for the decomposition of the eigenvalues, but it is not a sufficient condition.
The eigenvalues of the Laplace-Kirchhoff matrices are natural numbers, except if the graph G or its complementary graph is the selfcomplementary graph, for example: L(4), C(5). The eigenvalues of L(4) are (2+
Ö 2), 2, (2-Ö 2), 0, the sum after the proper ordering is 4, 4, 4, 0.The arcs of complete graphs lies in n dimensional space on the plane orthogonal to the unit diagonal matrix, it is on (n-1) dimensional body. Therefore there are only limited number of nonzero eigenvalues. Adding a new vertex increases the dimensionality only for one dimension. This new dimension is correlated to one from the previous vertices. Other arcs within the vertex set must be expressed as linear combinations of the previous set of orthogonal vectors.