This work is licensed under the Creative Commons Attribution 4.0 International License.
Introduction and preliminaries
Let G be a graph with n vertices and m edges and let A = (aij) be the adjacency matrix of G. The eigenvalues λ1,λ2,...,λn of A in non-increasing order are called the eigenvalues of the graph G. As A is real symmetric, the eigenvalues of G are real with sum equal to zero. The energy E(G) of G is defined by I. Gutman, [7], to be the sum of the absolute values of the eigenvalues of G, i.e.
E(G) = \sum\limits_{i = 1}^n |{\lambda _i}|.
For details on the mathematical aspects of the theory of graph energy, see the review [9], papers [4, 5, 8] and the references cited therein. The basic properties including various upper and lower bounds for the energy of a graph have been established in [16, 18], and the notion of graph energy has been found to have remarkable chemical applications in the molecular orbital theory of conjugated molecules, [6, 10]. In [11], a QSPR study is made for the energy of certain graph theoretical matrices. In [17], some graph operations are realized.
The distance matrix of G is the square matrix of order n whose (i, j)-th entry is the distance between the vertices vi and vj which is defined as the length of the shortest path between these two vertices. Let μ1, μ2, ..., μn be the eigenvalues of the distance matrix of G. The distance energy DE is defined by
DE = DE(G): = \sum\limits_{i = 1}^n |{\mu _i}|.
Detailed information on distance energy can be found in [3, 13, 14, 21]. The distance energy of the join of two given graphs can be found in [20]. In [19], a generalization of the distance notion is given.
Recently R. B. Bapat et al., [1], defined a new distance matrix, called as the q-distance matrix denoted by
{A_q}(G) = ({q_{ij}}).
For an indeterminate q, the entries qij of this new matrix are defined by
{q_{ij}} = \left\{ {\matrix{ {1 + q + {q^2} + \cdots + {q^{k - 1}},} & {{\kern 1pt} \,\,\,\,{\rm if}{\kern 1pt} {\kern 1pt} {\kern 1pt} k = {d_{ij}},} \cr {0,} & {{\rm if}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} i = j,} \cr } } \right.
where k = dij is the distance between the vertices vi and vj. Each entry of Aq(G) is a polynomial in q. Observe that Aq(G) is an entry-wise non-negative matrix for all q ≥ −1.
The characteristic polynomial of Aq(G) is defined by
{f_n}(G,\mu ) = det\,(\mu I - {A_q}(G)).
The q-distance eigenvalues of the graph G are similarly the eigenvalues of Aq(G). Since Aq(G) is real and symmetric, its eigenvalues are also real numbers and we label them in non-increasing order μ1 ≥ μ2 ≥ ··· ≥ μn. The q-distance energy of G is denoted by Eq(G) and is defined by
{E_q}(G) = \sum\limits_{i = 1}^n |{\mu _i}|.
Note that the trace of Aq(G) = 0 and also if q = 1, then the q-distance energy coincides with distance energy of a graph.
Here we study some fundamental properties of the q-distance eigenvalues. We start with the following well-known lemmas:
Lemma 2
Let G be a graph with the adjacency matrix A and the spectrum spec(G) = {μ1, μ2,..., μn}. Then it is well-known thatdet\;A = \prod\limits_{i = 1}^n {\mu _i}.In addition, for any polynomial P(x), the value P(μ) is an eigenvalue of P(A) and hencedet\;P(A) = \prod\limits_{i = 1}^n P({\mu _i}).
Lemma 3
LetB = \left( {\matrix{ {{B_0}} & {{B_1}} \cr {{B_1}} & {{B_0}} } } \right)be a symmetric 2 × 2 block matrix. Then the spectrum of B is the union of the spectra of B0 + B1and B0 − B1.
We can now prove the following results on q-distance eigenvalues:
Theorem 4
Let G be an (n,m) graph of diameter 2 with the q-distance eigenvalues μ1, μ2,..., μn. Then\sum\limits_{i = 1}^n {\mu _i}^2 = 2m + ({n^2} - n - 2m)(1 + q{)^2}.
Proof
In a q-distance adjacency matrix Aq(G), there are 2m elements equal to 1 and n2 − n − 2m elements equal to (1 + q). Therefore
\matrix{ {\sum\limits_{i = 1}^n \mu _i^2} \hfill & { = \sum\limits_{i = 1}^n \sum\limits_{j = 1}^n {q_{ij}}{q_{ji}}} \hfill \cr {} \hfill & { = \sum\limits_{i = 1}^n \sum\limits_{j = 1}^n {{({q_{ij}})}^2}} \hfill \cr {} \hfill & { = (2m{{)(1)}^2} + ({n^2} - n - 2m)(1 + q{)^2}} \hfill \cr {} \hfill & { = 2m + ({n^2} - n - 2m)(1 + q{)^2}.} \hfill \cr }
Theorem 5
Let G be an (n,m) graph of diameter 2 and let μ1be its greatest q-distance eigenvalue. Then{\mu _1} \ge {{n(n - 1)(1 + q) - 2mq} \over n}.
Proof
Let G be a connected graph of diameter 2 with its vertices labeled as v1,v2,...,vn and let di denote the degree of vi. As G is of diameter 2, it is easy to observe that the ith row of Aq consists of di times 1s and n − di − 1 times 2s. Let X = [1,1,1,...,1] be a vector containing only 1s. Then by the Rayleigh principle, we have
\matrix{ {{\mu _1}} \hfill & { \ge {{X{A_q}{X^T}} \over {X{X^T}}}} \hfill \cr {} \hfill & { = {{\sum\nolimits_{i = 1}^n ({d_i}(1) + (n - {d_i} - 1)(1 + q))} \over n}} \hfill \cr {} \hfill & { = {{(2m + (n - 1)n(1 + q) - 2m(1 + q))} \over n}} \hfill \cr {} \hfill & { = {{n(n - 1)(1 + q) - 2mq} \over n}.} \hfill \cr }
Theorem 6
Let G be an r-regular graph of diameter 2 with r, μ2,..., μn as its eigenvalues. Then the q-distance eigenvalues of G are −rq + (n − 1)(1 + q),−qμ2 − (1 + q), −qμ3 − (1 + q),...,−qμn − (1 + q).
Proof
Let G be an r-regular graph with diameter 2 and adjacency matrix A.
\overline A
is the adjacency matrix of
\overline G
. Then the q-distance adjacency matrix of G will be
{A_q} = A + (1 + q)\overline A .
If r, μ2,..., μn are the eigenvalues of A with r ≥ μ2 ≥ ··· ≥ μn, then n − 1 − r, −μ2 − 1, −μ3 − 1,...,−μn − 1 are the eigenvalues of
\overline A
. By Eqn. (1), the theorem is proved.
Theorem 7
Let G be a connected r-regular graph of diameter one or two with the adjacency matrix A and spec(G) = {r, μ2, μ3,..., μn}. Then the product graph H = G × K2is (r + 1)-regular and of diameter 2 or 3 with spec(H) = {−rq(1 + q) + 2n(1 + q) + q2(n − 1) − 1,−qμi(1 + q) − (1 + 2q + q2),−rq(1 − q) + q2(1 − n) − 1,−qμi(1 − q) − (1 − q2)} for i = 1,2,3,...,n.
Proof
Since G is of diameter 1 or 2, its q-distance matrix is
A + (1 + q)\overline A
. Then the q-distance matrix of H is of the form
\left( {\matrix{ {A + (1 + q)\overline A } & {J + qA + (q + {q^2})\overline A } \cr {J + qA + (q + {q^2})\overline A } & {A + (1 + q)\overline A } \cr } } \right).
By Lemma 3, the spectrum of H is the union of the spectra of
(1 + q)A + (1 + 2q + {q^2})\overline A + J
and
(1 - q)A + (1 - {q^2})\overline A - J
. If r, μ2,..., μn are the eigenvalues of A with r ≥ μ2 ≥ ··· ≥ μn then n − r − 1,−μ2 − 1,−μ3 − 1,...,−μn − 1 are the eigenvalues of
\overline A
. Also we know that n,0,0,...,0 are the eigenvalues of J. Therefore, the theorem follows.
Bounds for the q-distance energy
In this section, we find several bounds for the q-distance energy Eq(G). The first one is a sequel of the work of McClelland's, [18].
Theorem 8
Let G be a simple (n,m) graph with diameter 2. If P = |detAq(G)|, then\sqrt {2m + ({n^2} - n - 2m)(1 + q{)^2} + n(n - 1){P^{{2 \over n}}}} \le {E_q}(G) \le \sqrt {n(2m + ({n^2} - n - 2m)(1 + q{)^2})} .
Proof
Recall that the Cauchy-Schwarz inequality states that
{(\sum\limits_{i = 1}^n {a_i}{b_i})^2} \le (\sum\limits_{i = 1}^n a_i^2)(\sum\limits_{i = 1}^n b_i^2).
If we substitute ai = 1 and bi = | μi |, then we obtain
{(\sum\limits_{i = 1}^n |{\mu _i}|)^2} \le (\sum\limits_{i = 1}^n 1)(\sum\limits_{i = 1}^n \mu _i^2).
Hence by Theorem 4, we have
E_q^2(G) \le n(2m + ({n^2} - n - 2m)(1 + q{)^2})
and therefore we obtain
{E_q}(G) \le \sqrt {n(2m + ({n^2} - n - 2m)(1 + q{)^2})} .
Since the arithmetic mean is not smaller than the geometric mean, we have
\matrix{ {{1 \over {n(n - 1)}}\sum\nolimits_{i \ne j} |{\mu _i}{\mu _j}|} \hfill & { \ge {{[\prod\nolimits_{i \ne j} |{\mu _i}{\mu _j}|]}^{{1 \over {n(n - 1)}}}}} \hfill \cr {} \hfill & { = [\prod\nolimits_{i = 1}^n |{\mu _i}{|^{2(n - 1)}}{]^{{1 \over {n(n - 1)}}}}} \hfill \cr {} \hfill & { = [\prod\nolimits_{i = 1}^n |{\mu _i}|{]^{{2 \over n}}}} \hfill \cr {} \hfill & { = [\prod\nolimits_{i = 1}^n {\mu _i}{]^{{2 \over n}}}} \hfill \cr {} \hfill & { = |det{A_q}(G{{)|}^{{2 \over n}}}} \hfill \cr {} \hfill & { = {P^{{2 \over n}}}.} \hfill \cr }
Therefore
\sum\limits_{i \ne j} |{\mu _i}{\mu _j}| \ge n(n - 1){P^{{2 \over n}}}.
Now consider
\matrix{ {E_q^2(G)} \hfill & { = {\left(\sum\nolimits_{i = 1}^n |{\mu _i}|\right)^2}} \hfill \cr {} \hfill & { = \sum\nolimits_{i = 1}^n |{\mu _i}{|^2} + \sum\nolimits_{i \ne j} |{\mu _i}||{\mu _j}|.} \hfill \cr }
Therefore, by Theorem 4, we obtain
E_q^2(G) \ge 2m + ({n^2} - n - 2m)(1 + q{)^2} + n(n - 1){P^{{2 \over n}}}
and hence
{E_q}(G) \ge \sqrt {2m + ({n^2} - n - 2m)(1 + q{)^2} + n(n - 1){P^{{2 \over n}}}} .
Now, we find another bound for Eq(G) which is a sequel to the work of Koolen and Moulton's, [12].
Theorem 9
If G is an (n,m) graph with diameter 2 so that{{n(n - 1)(1 + q) - 2mq} \over n} \ge 1,then{E_q}(G) \le {{n(n - 1)(1 + q) - 2mq} \over n} + \sqrt {(n - 1)[(2m + ({n^2} - n - 2m)(1 + q{)^2} - {{({{n(n - 1)(1 + q) - 2mq} \over n})}^2}]} .
Proof
By substituting ai = 1 and bi =| μi | in Cauchy-Schwarz inequality, we have
{\left( {\sum\limits_{i = 2}^n |{\mu _i}|} \right)^2} \le \sum\limits_{i = 2}^n 1\sum\limits_{i = 2}^n \mu _i^2{[{E_q}(G) - {\mu _1}]^2} \le (n - 1)(2m + ({n^2} - n - 2m)(1 + q{)^2}).
Hence
{E_q}(G) \le {\mu _1} + \sqrt {(n - 1)(2m + ({n^2} - n - 2m)(1 + q{)^2} - \mu _1^2)} .
Let
f(x) = x + \sqrt {(n - 1)(2m + ({n^2} - n - 2m)(1 + q{)^2} - {x^2})} .
Then for a decreasing function f (x), the fact f′(x) ≤ 0 implies that
1 - {{x(n - 1)} \over {\sqrt {(n - 1)(2m + ({n^2} - n - 2m)(1 + q{)^2} - {x^2})} }} \le 0.
From this we obtain
x \ge \sqrt {{{2m + ({n^2} - n - 2m)(1 + q{)^2}} \over n}} .
Therefore the function f (x) is decreasing in the interval
\left( {\sqrt {{{2m + ({n^2} - n - 2m)(1 + q{)^2}} \over n}} ,\sqrt {2m + ({n^2} - n - 2m)(1 + q{)^2}} } \right).
Clearly the number (n(n−1)(1+q)−2mq)/n belongs to that interval and since μ1 ≥ (n(n−1)(1+q)−2mq)/n, we have
(n(n - 1)(1 + q) - 2mq)/n \le {\mu _1} \le \sqrt {2m + ({n^2} - n - 2m)(1 + q{)^2}}
. By Lemma 5.3, we can write f (μ1) ≤ f((n(n − 1)(1 + q) − 2mq)/n). Hence
{E_q}(G) \le f({\mu _1}) \le f((n(n - 1)(1 + q) - 2mq)/n)
implying the result.
Bapat and Pati, [2], proved that if the graph energy is a rational number, then it is an even integer. A similar result for q-distance energy can be given as follows:
Lemma 10
Let G be an (n,m) graph. If the q-distance energy Eq(G) of G is a rational number, then{E_q}(G)\;\; \equiv \;\;|0|\;\;(mod\;2).
One of the ways of studying graphs is to make use of smaller graphs usually those subgraphs whose own are the components of the given graph. Similarly to this idea, many graph operations, sometimes called graph products, are defined to make the necessary calculations on some given graphs by means of similar calculations on some smaller graphs. In this section, we shall study one of the most practical of these products, called the join, of two graphs and calculate the q-distance energy of it. Other operations can be applied similarly to obtain some other properties.
Definition 1
The join of two graphs G1 and G2 denoted by G1∇G2 is a larger graph obtained from G1 and G2 by joining each vertex of G1 to all the vertices of G2.
Figure 4.1
Join of two graphs
Theorem 11
Let G1be an r1-regular graph on n1vertices having diam(G1) ≤ 2 and G2be an r2-regular graph on n2vertices having diam(G2) ≤ 2. Let further φ(G1 : μ) and φ(G2 : μ) be the q-distance characteristic polynomials of G1and G2, respectively. Then the q-distance characteristic polynomial of the q-distance matrix of G1∇G2is{{(\mu - (1 + q)({n_1} - 1) + {r_1}q)(\mu - (1 + q)({n_2} - 1) + {r_2}q) - {n_1}{n_2}} \over {(\mu - (1 + q)({n_1} - 1) + {r_1}q)(\mu - (1 + q)({n_2} - 1) + {r_2}q)}}\phi ({G_1}:\mu )\phi ({G_2}:\mu ).
Proof
Let us assume that v1, v2, ..., vn1 be the vertices of the graph G1 and u1, u2, ..., un2 be the vertices of the graph G2. Let qij denote the q-distance between the vertices vi and vj in G1 and
q_{ij}^\prime
denote the q-distance between the vertices ui and uj in G2. In G1, every vertex is at distance 1 from r1 vertices and at distance 1 + q from the remaining n1 − 1 − r1 vertices. Therefore for i = 1, 2, 3, ..., n1, we can write
\matrix{ {\sum\limits_{j = 1}^{{n_1}} {q_{ij}}} \hfill & { = 1({r_1}) + (1 + q)({n_1} - 1 - {r_1})} \hfill \cr {} \hfill & { = {r_1} + (1 + q)({n_1} - 1) - {r_1} - {r_1}q} \hfill \cr {} \hfill & { = (1 + q)({n_1} - 1) - {r_1}q} \hfill \cr }
and similarly, for i = 1,2,3,...,n2, we have
\sum\limits_{j = 1}^{{n_2}} q_{ij}^\prime = (1 + q)({n_2} - 1) - {r_2}q.
Let
{P_1}(\mu ) = (\mu - R)(\mu - K)\phi ({G_1}\nabla {G_2};\mu )
and
{P_2}(\mu ) = ({\mu ^2} - (R + K)\mu + RK - {n_1}{n_2})\phi ({G_1};\mu )\phi ({G_2};\mu ).
The roots of the equation P1(μ) = 0 are R,K and q–distance eigenvalues of G1∇G2. Therefore, the sum of the absolute values of the roots of P1(μ) = 0 is
R + K + {E_q}({G_1}\nabla {G_2})
and similarly the roots of the equation P2(μ) = 0 are q–distance eigenvalues of G1 and G2 and hence
{{R + K + \sqrt {{{(R + K)}^2} - 4(RK - {n_1}{n_2})} } \over 2},\;\;{{R + K - \sqrt {{{(R + K)}^2} - 4(RK - {n_1}{n_2})} } \over 2}.
Therefore, the sum of the absolute values of the roots of P2(μ) = 0 is
{E_q}({G_1}) + {E_q}({G_2}) + \left|{{R + K + \sqrt {{{(R + K)}^2} - 4(RK - {n_1}{n_2})} } \over 2}\right| + \left|{{R + K - \sqrt {{{(R + K)}^2} - 4(RK - {n_1}{n_2})} } \over 2}\right|.
Since P1(μ) = P2(μ), from above equations, we get,
\matrix{ {R + K + {E_q}({G_1}\nabla {G_2})} \hfill & { = {E_q}({G_1}) + {E_q}({G_2})} \hfill \cr {} \hfill & { + \left|{{R + K + \sqrt {{{(R + K)}^2} - 4(RK - {n_1}{n_2})} } \over 2}\right|} \hfill \cr {} \hfill & { + \left|{{R + K - \sqrt {{{(R + K)}^2} - 4(RK - {n_1}{n_2})} } \over 2}\right|.} \hfill \cr }
Case 1: If RK ≥ n1n2, the last equation reduces to
\matrix{ {R + K + {E_q}({G_1}\nabla {G_2})} \hfill & { = {E_q}({G_1}) + {E_q}({G_2})} \hfill \cr {} \hfill & { + {{R + K + \sqrt {{{(R + K)}^2} - 4(RK - {n_1}{n_2})} } \over 2}} \hfill \cr {} \hfill & { + {{R + K - \sqrt {{{(R + K)}^2} - 4(RK - {n_1}{n_2})} } \over 2},} \hfill \cr }
and therefore
R + K + {E_q}({G_1}\nabla {G_2}) = {E_q}({G_1}) + {E_q}({G_2}) + R + K
implying that
{E_q}({G_1}\nabla {G_2}) = {E_q}({G_1}) + {E_q}({G_2}).
Case 2: If RK < n1n2, this time the last equation above reduces to
\matrix{ {R + K + {E_q}({G_1}\nabla {G_2})} \hfill & { = {E_q}({G_1}) + {E_q}({G_2})} \hfill \cr {} \hfill & { + {{R + K + \sqrt {{{(R + K)}^2} - 4(RK - {n_1}{n_2})} } \over 2}} \hfill \cr {} \hfill & { + {{R + K - \sqrt {{{(R + K)}^2} - 4(RK - {n_1}{n_2})} } \over 2}.} \hfill \cr }
Hence we get
R + K + {E_q}({G_1}\nabla {G_2}) = {E_q}({G_1}) + {E_q}({G_2}) + \sqrt {{{(R + K)}^2} - 4(RK - {n_1}{n_2})}
and finally
{E_q}({G_1}\nabla {G_2}) = {E_q}({G_1}) + {E_q}({G_2}) - (R + K) + \sqrt {{{(R + K)}^2} - 4(RK - {n_1}{n_2})} .
Brief summary and conclusion
Energy is a very important subject of graph theory with many applications in physics and chemistry. Similarly to the classical graph energy, there are a few other types of energy in graphs which are similarly defined by means of some other matrices. In this paper, we have defined a new type of energy called q-distance energy. As the distances are calculated between the vertices of the graph representing the atoms in the corresponding molecule, the q-distance energy is expected to have applications in chemistry due to its effect on the intermolcecular forces which affect the graph energy. The q-distance energy has been obtained for the join of two graphs. Similar studies can be made for other graph operations. Also, we have established lower and upper bounds for this new energy.
