For a simple graph G of order n, let \(\mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{n}=0\) be its Laplacian eigenvalues, and let \(q_{1}\geq q_{2}\geq\cdots\geq q_{n}\geq0\) be its signless Laplacian eigenvalues. The Laplacian-energy-like invariant and incidence energy of G are defined as, respectively,
In this paper, we present some new upper and lower bounds on LEL and IE of line graph, subdivision graph, para-line graph and total graph of a regular graph, some of which improve previously known results. The main tools we use here are the Cauchy-Schwarz inequality and the Ozeki inequality.
Hinweise
Competing interests
The authors declare that they have no competing interests.
Authors’ contributions
All authors contributed equally and significantly in writing this article. All authors read and approved the final manuscript.
1 Introduction
There are a large number of remarkable chemical applications in graph theory, one of which is based on the close correspondence between the graph eigenvalues and the molecular orbital energy levels of π-electrons in conjugated hydrocarbons. For the Hüchkel molecular orbital (HMO) approximation, the total π-electron energy in conjugated hydrocarbons is given by the sum of absolute values of the eigenvalues of the corresponding molecular graph in which the degree of each vertex is not more than three in general. In 1978, Gutman [1] extended the concept of energy to all simple graphs, and defined the energy of a graph G (of order n) as
$$E(G)=\sum_{i=1}^{n}| \lambda_{i}|, $$
where \(\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}\) are the eigenvalues of the adjacency matrix \(A(G)\) of G (also called the eigenvalues of the graph G). The concept of graph energy was further extended to any matrix in [2]: the energy \(E(M)\) of a (not necessarily square) matrix M is the sum of its singular values, where the singular values of M are the square roots of the eigenvalues of the (square) matrix \(MM^{T}\) (\(M^{T}\) stands for the transpose of M). Obviously, \(E(G)=E(A(G))\). For more details in the theory of graph energy, see [3] by Li et al.
The Laplacian matrix \(L(G)\) of a graph G is another important and well-studied matrix in graph theory, which is defined to be \(L(G)=D(G)-A(G)\), where \(D(G)\) is the diagonal matrix of vertex degrees of G. The eigenvalues of \(L(G)\) are also called the Laplacian eigenvalues of the graph G, which are always denoted by \(\mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{n-1}\geq \mu_{n}=0\). Based on the Laplacian eigenvalues, Liu and Liu [4] conceived the following invariant:
They called this invariant the Laplacian-energy-like invariant, which was later proved to be an energy like invariant [5]. Nowadays, LEL has become a successful molecular descriptor [6]. A great deal of work has been done on LEL, see [7] for a comprehensive survey.
Anzeige
Recall that giving an arbitrary orientation to each edge of G would yield an oriented graph G⃗. Let \(B(\vec{G})\) be the (vertex-edge) incidence matrix of G⃗. Then \(B(\vec{G})B(\vec{G})^{T}=L(G)\), and hence \(\mathit{LEL}(G)=E(B(\vec{G}))\). This provides a new interpretation for LEL: oriented incidence energy [8], and furnishes a new insight into its possible physical or chemical meaning.
Let \(B(G)\) be the (vertex-edge) incidence matrix of G. Motivated by Nikiforov’s idea and LEL, Jooyandeh et al. [9] introduced the concept of incidence energy of a graph G: if the singular values of \(B(G)\) are \(\sigma_{1},\sigma_{2},\ldots,\sigma_{n}\) then the incidence energy of G is \(\mathit{IE}(G)=\sum_{i=1}^{n}\sigma_{i}=E(B(G))\). Note that \(B(G)B(G)^{T}=A(G)+D(G)=Q(G)\) is the signless Laplacian matrix of G, with its eigenvalues \(q_{1}\geq q_{2}\geq\cdots\geq q_{n}\geq0\) (also called the signless Laplacian eigenvalues of the graph G). Thus, it follows that
LetGbe a graph of ordern. Then\(\mathit{LEL}(G)\leq\mathit{IE}(G)\), with the equality holding if and only ifGis bipartite.
Anzeige
For more results on IE, we refer the reader to [9, 11‐13].
The line graph, subdivision graph, para-line graph and total graph are the well-known operations on graphs, which can produce many new types of graphs. In [14], Ramane et al. studied the spectra and energies of (iterated) line graphs of regular graphs, and based on the derived results they found a systematic construction of pairs of equienergetic graphs. Gao et al. [15] established formulas and lower bounds of the Kirchhoff index of line, subdivision and total graphs of a regular graph. Yan et al. [16] considered the asymptotic behavior of the number of spanning trees and the Kirchhoff index of iterated line graphs and iterated para-line graphs of a regular graph. Recently, in [17], Wang and Luo presented upper and lower bounds for the Laplaican-energy-like invariant of line graph, subdivision graph and total graph of a regular graph. In addition, upper and lower bounds for the incidence energy of (iterated) line graphs of a regular graph were also obtained by Gutman et al. [12].
In this paper, we give some new upper and lower bounds on the Laplacian-energy-like invariant and the incidence energy of line graph, subdivision graph, para-line graph and total graph of a regular graph, some of which improve the corresponding bounds in [17] and [12].
2 Preliminaries
In this section, we recall the concepts of line graphs and related graph operations, and list some lemmas that will be used in the subsequent sections.
The line graph \(\mathcal{L}(G)\) of a graph G is the graph whose vertices are the edges of G, with two vertices in \(\mathcal {L}(G)\) adjacent whenever the corresponding edges in G have exactly one vertex in common. If G is a regular graph of degree r with n vertices and m (\(=nr/2\)) edges, then characteristic polynomial of \(\mathcal{L}(G)\) can be expressed in terms of the characteristic polynomial of G, namely [18]
where we write \(P_{M}(x)\) for the characteristic polynomial of a matrix M. By (3), we have the following lemma immediately.
Lemma 2.1
LetGbe a regular graph of degreerwithnvertices. If the eigenvalues ofGare\(\lambda_{1},\lambda_{2} , \ldots,\lambda_{n}\), then the eigenvalues of\(\mathcal{L}(G)\)are\(r-2+\lambda_{1},r-2+\lambda_{2},\ldots,r-2+\lambda_{n}\), and −2 (with multiplicity\(n(r-2)/2\)).
The subdivision graph \(\mathcal{S}(G)\) of a graph G is the graph obtained by inserting a new vertex into every edge of G. Clearly, \(\mathcal{S}(G)\) is a bipartite graph. Moreover, if G is a regular graph of degree r with n vertices and m edges, then [19]
From (4) we arrive at the next lemma (see also [17]).
Lemma 2.2
LetGbe a regular graph of degreerwithnvertices. If the Laplacian eigenvalues ofGare\(\mu_{1},\mu_{2} , \ldots,\mu_{n}\), then\(\mathcal{S}(G)\)has\(n(r-2)/2\)Laplacian eigenvalues equal to 2 and the following 2nLaplacian eigenvalues:
The para-line graph \(\mathcal{C}(G)\) of a graph G, which was first introduced in [20], is defined to be the line graph of the subdivision graph of G. In [21], the para-line graph is also called the clique-inserted graph.
LetGbe a regular graph of degreerwithnvertices. If the eigenvalues ofGare\(\lambda_{1},\lambda_{2} , \ldots,\lambda_{n}\), then the eigenvalues of\(\mathcal{C}(G)\)are −2 (with multiplicity\(n(r-2)/2\)), 0 (with multiplicity\(n(r-2)/2\)), and
The total graph \(\mathcal{T}(G)\) of a graph G is the graph whose vertices are the vertices and edges of G, with two vertices of \(\mathcal{T}(G)\) adjacent if and only if the corresponding elements of G are adjacent or incident.
LetGbe a regular graph of degreer (\(r>1\)) havingnvertices. If the eigenvalues ofGare\(\lambda_{1},\lambda_{2} , \ldots,\lambda_{n}\), then\(\mathcal{T}(G)\)has\(n(r-2)/2\)eigenvalues equal to −2 and the following 2neigenvalues:
LetGbe a graph of ordernwith at least one edge. Then\(\mu_{1}=\mu_{2}=\cdots=\mu_{n-1}\)if and only if\(G\cong K_{n}\).
Finally, we should remark that if G is a regular graph of degree \(r=1\), then G is nothing but the disjoint union of independent edges. Hence, in the following, for avoiding the triviality we always assume that \(r\geq2\).
3 The Laplacian-energy-like invariant
In this section, we consider LEL of line graph, subdivision graph, para-line graph, and total graph of a regular graph. We begin with the case of line graphs.
with the right equality if and only if \(G\cong K_{n}\). Evidently, the lower bound in Corollary 3.2 is better than that in (6). For the upper bound, our bound is also better than that in (6). To see this, we only need to show that
LetGbe a regular graph of degreerwithnvertices. Then
(i)
\(\mathit{LEL}(\mathcal{S}(G))\leq(n-1)\sqrt{r+2+\frac{2}{n-1}\mathit {LEL}(G)} +\sqrt{r+2}+\frac{\sqrt{2}n(r-2)}{2}\), with the equality if and only if\(G\cong K_{n}\);
Suppose that \(\mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{n-1}\geq\mu_{n}=0\) are the Laplacian eigenvalues of G. Then from (1) and Lemma 2.2, it follows that
Moreover, it is easy to see that the equality holds if and only if \(\mu_{1}=\mu_{2}=\cdots=\mu_{n-1}\), which, by Lemma 2.7, is equivalent to \(G\cong K_{n}\). Hence, (i) follows.
We now prove (ii). Take \(a_{i}=\sqrt{r+2+2\sqrt{\mu_{i}}}\) and \(b_{i}=1\), \(i=1,2,\ldots,n-1\). Set \(A=\sqrt{r+2+2\sqrt{2r}}\), \(a=\sqrt{r+2}\), and \(B=b=1\). Clearly, \(0< a\leq a_{i}\leq A\) (as \(0\leq\mu_{n-1}\leq\cdots\leq\mu _{1}\leq2r\)), and \(0< b\leq b_{i}\leq B\). Furthermore, we get
Theorem 3.3, together with (5), would yield the next immediate corollary.
Corollary 3.4
LetGbe a regular graph of degreerwithnvertices. Then
(i)
\(\mathit{LEL}(\mathcal{S}(G))\leq(n-1)\sqrt{r+2+\frac{2 (\sqrt {r+1}+\sqrt{(n-2)(nr-r-1)} )}{n-1}} +\sqrt{r+2}+\frac{\sqrt{2}n(r-2)}{2}\), with the equality if and only if\(G\cong K_{n}\);
the right equality holds if and only if \(G\cong K_{2}\). Note that the lower and upper bounds in Corollary 3.2 are better than those in (9), respectively. Indeed, for the lower bound, since \(\sqrt{\frac{r}{r+1}}\geq\frac{\sqrt{2}}{2}\) and \(n>n-1\), we have
Next, we turn our attention to the case of para-line graphs. Notice that if G is r-regular, then \(\mathcal{C}(G)\) is also r-regular, and hence it follows from Lemma 2.3 that the Laplacian eigenvalues of \(\mathcal{C}(G)\) are \(r+2\) (with multiplicity \(n(r-2)/2\)), r (with multiplicity \(n(r-2)/2\)), and
where \(\mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{n}\) are the Laplacian eigenvalues of G. Using the same argument as the proof of Theorem 3.3, we may arrive at the following result.
Theorem 3.5
LetGbe a regular graph of degreerwithnvertices. Then
(i)
\(\mathit{LEL}(\mathcal{C}(G))\leq(n-1)\sqrt{r+2+\frac{2}{n-1}\mathit {LEL}(G)} +(\frac{n(r-2)}{2}+1)\sqrt{r+2}+\frac{n(r-2)}{2}\sqrt{r}\), with the equality if and only if\(G\cong K_{n}\);
Likewise, the next corollary follows evidently from Theorem 3.5 and (5).
Corollary 3.6
LetGbe a regular graph of degreerwithnvertices. Then
(i)
\(\mathit{LEL}(\mathcal{C}(G))\leq(n-1)\sqrt{r+2+\frac{2 (\sqrt {r+1}+\sqrt{(n-2)(nr-r-1)} )}{n-1}} +(\frac{n(r-2)}{2}+1)\sqrt{r+2}+\frac{n(r-2)}{2}\sqrt{r}\), with the equality if and only if\(G\cong K_{n}\);
Note first that \(\mathcal{T}(G)\) is a regular graph of degree 2r with \(\frac{n(r+2)}{2}\) vertices. Then from Lemma 2.4, it follows that \(\mathcal{T}(G)\) has \(\frac{n(r-2)}{2}\) Laplacian eigenvalues equal to \(2r+2\) and the following 2n Laplacian eigenvalues:
On the other hand, by using the Cauchy-Schwarz inequality and the fact that \(\sum_{i=1}^{n-1}\mu_{i}=nr\) and \(\sum_{i=1}^{n-1}\mu_{i}^{2}=nr^{2}+nr\), we have
which, together with (10), yields the required upper bound. For the sharpness of this bound, it is not difficult to check that if \(G\cong K_{n}\) then the equality holds. Conversely, we assume that the equality holds. Then the above two inequalities should be equalities. Thus, it follows from the second inequality that, for any \(1\leq i,j\leq n-1\) and \(i\neq j\), \(\sqrt{\mu_{i}^{2}+(r+3)\mu_{i}}=\sqrt{\mu_{j}^{2}+(r+3)\mu_{j}}\), that is, \((\mu_{i}-\mu_{j})(\mu_{i}+\mu_{j}+r+3)=0\), which implies that \(\mu_{i}=\mu_{j}\). In other words, we have \(\mu_{1}=\mu_{2}=\cdots=\mu_{n-1}\). Note that in this case, the first inequality is also an equality. Eventually, by Lemma 2.7, we get \(G\cong K_{n}\).
We next prove (ii). Since \(\mu_{i}\geq0\), \(i=1,2,\ldots,n-1\), by (10) we get
We now take \(a_{i}=\sqrt{r+2+2\mu_{i}+2\sqrt{(r+3)\mu_{i}}}\) and \(b_{i}=1\), \(i=1,2,\ldots,n-1\). Set \(A=\sqrt{5r+2+2\sqrt{2(r+3)r}}\), \(a=\sqrt{r+2}\), and \(B=b=1\). It is easy to see that \(0< a\leq a_{i}\leq A\), and \(0< b\leq b_{i}\leq B\). Furthermore, if \(r\geq3\), then \(A=\sqrt{5r+2+2\sqrt{2(r+3)r}}\leq\sqrt {9r+2}\) and hence,
with the equality if and only if \(G\cong K_{2}\). Obviously, the lower bound in Theorem 3.7 is better than that in (12). For the upper bound, it is easy to check that, for \(n\geq2\) and \(r>1\),
from which we would find that the upper bound in Theorem 3.7 is better than that in (13).
4 The incidence energy
In this section, we investigate IE of line graph, subdivision graph, para-line graph and total graph of a regular graph.
Theorem 4.1
LetGbe a regular graph of degreerwithnvertices. Then
(i)
(see [11]) \(\mathit{IE}(\mathcal{L}(G))\leq(n-1)\sqrt {\frac {3n-4}{n-1}r-4} +\sqrt{4r-4}+\frac{n(r-2)}{2}\sqrt{2r-4}\), with the equality if and only if\(G\cong K_{n}\);
Suppose that \(\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}\) are the eigenvalues of G and that \(q_{1}\geq q_{2}\geq\cdots\geq q_{n}\) are the signless Laplacian eigenvalues of G. Noticing that G is r-regular, we have \(q_{i}=r+\lambda_{i}\), \(i=1,2,\ldots,n\). Moreover, since \(\mathcal{L}(G)\) is \((2r-2)\)-regular, from Lemma 2.1, it follows that the signless Laplacian eigenvalues of \(\mathcal{L}(G)\) are \(2r-4+q_{1},2r-4+q_{2},\ldots,2r-4+q_{n}\), and \(2r-4\) (with multiplicity \(n(r-2)/2\)). Thus, from (2) and noting that \(q_{1}=2r\), it follows that
Remark that (i) has been proved in [11] by Gutman et al. Hence, we here only give a proof for (ii). Take \(a_{i}=\sqrt{2r-4+q_{i}}\) and \(b_{i}=1\), \(i=2,3,\ldots,n\). Set \(A=\sqrt{4r-4}\), \(a=\sqrt{2r-4}\), and \(B=b=1\). It is clear that \(0< a\leq a_{i}\leq A\) (as \(0\leq q_{n}\leq\cdots\leq q_{2}\leq q_{1}=2r\)), and \(0< b\leq b_{i}\leq B\). Furthermore, we have
Obviously, the lower bound in Theorem 4.1 is better than that in (15), since \(\frac{5n-7}{2n-2}>2\) always holds for \(n\geq4\).
Since the subdivision graph \(\mathcal{S}(G)\) of any graph G is bipartite, by Theorem 1.1 we have \(\mathit{IE}(\mathcal{S}(G))=\mathit {LEL}(\mathcal{S}(G))\). Consequently, the next theorem is obvious.
Theorem 4.2
LetGbe a regular graph of degreerwithnvertices. Then
(i)
\(\mathit{IE}(\mathcal{S}(G))\leq(n-1)\sqrt{r+2+\frac{2 (\sqrt {r+1}+\sqrt {(n-2)(nr-r-1)} )}{n-1}} +\sqrt{r+2}+\frac{\sqrt{2}n(r-2)}{2}\), with the equality if and only if\(G\cong K_{n}\);
LetGbe a regular graph of degreerwithnvertices. Then
(i)
\(\mathit{IE}(\mathcal{C}(G))\leq(n-1)\sqrt{3r-2+2\sqrt{2r^{2}-\frac{nr}{n-1}}} +\sqrt{2r}+\sqrt{r-2}+\frac{n(r-2)}{2} (\sqrt{r}+\sqrt{r-2} )\), with the equality if and only if\(G\cong K_{n}\);
Since \(\mathcal{C}(G)\) is a regular graph of degree r, it follows from Lemma 2.3 that the signless Laplacian eigenvalues of \(\mathcal{C}(G)\) are \(r-2\) (with multiplicity \(n(r-2)/2\)), r (with multiplicity \(n(r-2)/2\)), and
which, together with (16), yields the desired upper bound. Moreover, it is easily seen that the equality holds if and only if \(q_{1}=2r\) and \(q_{2}=q_{3}=\cdots=q_{n}\), which, in turn, implies that \(\mu_{1}=\mu_{2}=\cdots=\mu_{n-1}\) (since G is r-regular and hence \(\mu_{i}=2r-q_{n-i+1}\), \(i=1,2,\ldots,n\)). Thus, by Lemma 2.7, we have \(G\cong K_{n}\). Hence, (i) follows.
We next prove (ii). Take \(a_{i}=\sqrt{3r-2+2\sqrt{2(r-1)r+q_{i}}}\) and \(b_{i}=1\), \(i=2,3,\ldots,n\). Set \(A=\sqrt{(3+2\sqrt{2})r-2}\), \(a=\sqrt{(3+2\sqrt{2})r-(2\sqrt {2}+2)}\), and \(B=b=1\). Clearly, \(0< a\leq a_{i}\leq A\) and \(0< b\leq b_{i}\leq B\). Furthermore, we get
Now, take \(a_{i}=\sqrt{2(r-1)r+q_{i}}\) and \(b_{i}=1\), \(i=2,3,\ldots,n\), and set \(A=\sqrt{2}r\), \(a=\sqrt{2(r-1)r}\), and \(B=b=1\). It is easy to check that \(0< a\leq a_{i}\leq A\), \(0< b\leq b_{i}\leq B\), and \((AB-ab)^{2}<1\). Thus, recalling that \(\sum_{i=2}^{n}q_{i}=(n-2)r\), and again by Lemma 2.5 we have
which, together with (17), yields the required result.
The proof is completed. □
Theorem 4.4
LetGbe a regular graph of degreerwithnvertices. Then
(i)
\(\mathit{IE}(\mathcal{T}(G))\leq n\sqrt{3r-2}+\sqrt {2(n-1)(n-2)r}+\sqrt {4r}+\frac{n(r-2)}{2}\sqrt{2r-2}\), with the equality if and only if\(G\cong K_{n}\);
Since \(\mathcal{T}(G)\) is a regular graph of degree 2r, it follows from Lemma 2.4 that the signless Laplacian eigenvalues of \(\mathcal{T}(G)\) are \(2r-2\) (with multiplicity \(n(r-2)/2\)), and
On the other hand, by using the Cauchy-Schwarz inequality and the fact that \(\sum_{i=2}^{n}q_{i}=(n-2)r\) and \(\sum_{i=2}^{n}q_{i}^{2}=(n-4)r^{2}+nr\), we obtain
which, together with (18), would yield the desired upper bound. For the sharpness of this bound, it is easy to check that if \(G\cong K_{n}\) then the equality holds. Conversely, we assume that the equality holds. Then the above two inequalities should be equalities. Thus, it follows from the second inequality that, for any \(2\leq i,j\leq n\) and \(i\neq j\), \(\sqrt{q_{i}^{2}+3(r-1)q_{i}+2(r-1)r}=\sqrt{q_{j}^{2}+3(r-1)q_{j}+2(r-1)r}\), that is, \((q_{i}-q_{j})[q_{i}+q_{j}+3(r-1)]=0\), which implies that \(q_{i}=q_{j}\). In other words, we have \(q_{2}=q_{3}=\cdots=q_{n}\). Note also that in this case, the first inequality is also an equality. Now, using the same argument as in the proof of Theorem 4.3, we eventually arrive at \(G\cong K_{n}\). Hence, (i) follows.
Now take \(a_{i}=\sqrt{3r-2+2\sqrt{2}(r-1)+4q_{i}}\) and \(b_{i}=1\), \(i=2,3,\ldots,n\). Set \(A= \sqrt{11r-2+2\sqrt{2}(r-1)}\), \(a=\sqrt{3r-2+2\sqrt{2}(r-1)}\), and \(B=b=1\). Evidently, \(0< a\leq a_{i}\leq A\) (as \(0\leq q_{n}\leq\cdots\leq q_{2}\leq q_{1}=2r\)), and \(0< b\leq b_{i}\leq B\). Furthermore, we get
which, together with (19), yields the desired lower bound.
This completes the proof. □
Acknowledgements
The authors would like to thank the anonymous referees for their helpful comments and suggestions toward improving the original version of this paper. This work was supported in part by National Natural Science Foundation of China (Nos. 11501133, 11571101, 11461004), China Postdoctoral Science Foundation (No. 2015M572252), Guangxi Natural Science Foundation (No. 2014GXNSFBA118008) and the Scientific Research Fund of Guangxi Provincial Education Department (No. YB2014007).
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Competing interests
The authors declare that they have no competing interests.
Authors’ contributions
All authors contributed equally and significantly in writing this article. All authors read and approved the final manuscript.