The Radenković and Gutman conjecture establishes a relationship between the Laplacian eigenvalues of any tree \(T_n\), the star graph \(S_n\), and the path graph \(P_n\), i.e., \({LE}(P_n) \leq {LE}(T_n) \leq {LE}(S_n).\) In this paper, we prove this conjecture for a class of trees with \(n\) vertices and having diameter \(16\) to \(30\).
The “energy” of a graph is a concept that comes from spectral graph theory, a branch of graph theory that emphasizes the connections between the eigenvalues and eigenvectors of certain matrices associated with a graph. Graph energy have wide range of applications in the field of chemistry particularly in the study of molecular graphs and their properties. The energy of graph has been served as a structure descriptor in case of \(\sigma\)-electron systems. The graph energy gives better results than the traditional structure-descriptors. In this context, Liu et al. [8,7] introduced Hosoya index of graphs formed by a fractal graph and minimize Kirchhoff index among graphs with a given vertex bipartiteness. Understanding the structure, stability, and reactivity of molecules in many chemical situations is made possible by the useful tools provided by graph energy and Laplacian energy analyses, which further advances synthetic chemistry.
Energy of graph is defined as the total of the absolute eigenvalues values of the adjacency matrix \(\mathbf{A}({G})\) denoted by \[{E}({G}) = \sum_{r=1}^n|\lambda_r|,\] where \(\lambda_1, \lambda_2,\ldots,\lambda_n\) are the eigenvalues of \(\mathbf{A}({G}).\)
The Laplacian energy of a directed graph is denoted by \[{LE}({G}) = \sum_{r=1}^n|\mu_r-\frac{2m}{n}|,\] where \(m\) is total number of edges and \(n\) is total number of vertices and \(\mu_1, \mu_2,\ldots,\mu_n\) are the eigenvalues of \(L({G}).\) The Laplacian matrix is defined as \(L({G}) = D({G}) – \mathbf{A}({G}),\) where \(D({G})\) is the degree matrix.
Fiedler’s theorem [3] established that if the second smallest eigenvalue of the Laplacian matrix \(L({G})\) of a graph is equal to zero i.e \(\mu_2=0\), then the graph is disconnected. Consequently, this eigenvalue, denoted as \(a({G})\), is defined as the algebraic connectivity of the graph \({G}\). The corresponding eigenvectors are referred as Fiedler vectors of \({G}\). The relationship among energy and Laplacian energy of trees was investigated by Radenkovic and Gutman in [8].
If this hypothesis is correct, it suggests that the Laplacian energy’s extremal energy trees show an unusual inversion when compared to the extremal energy trees. This surprising result implies that the structural features that raise a tree’s energy actually decrease its Laplacian energy, and conversely, the structural features that decrease a tree’s energy increase its Laplacian energy. This finding highlights a striking and illogical link between these two energy measurements.
Ganie et al. [4] showed the truth of conjecture for all trees with number of non-pendent vertices at most \(\dfrac{9n}{25}-2.\) It is possible to repeat Radenković and Gutman’s experiment and validate that the star has the highest Laplacian energy and the path structure has the lowest Laplacian energy for all the trees in the database. The conjecture was confirmed by Trevisan et al. [11] for all trees with a diameter of \(3\) and trees with a maximum of \(18\) vertices also Rahman et al. [10] investigate this conjecture’s validity for all the trees of diameter \(4\).
In this work, we established the validity of Conjecture 1.1 for trees with diameter \(16\) to \(30\). Two stars with diameter \(16\) can be observed in a tree having \(14\) edges connecting the cores of them as shown in Figure 1, diameter \(17\) can be seen as two stars with \(15\) edges connecting the cores of them and so on till diameter \(30\). In this note, a class of trees of diameter \(16\) to \(30\) with \(n\) vertices will be represented by \(T_{n_i} (v, w)\) for \(1\leq i \leq 15,\) respectively. Where \(n_i = v + w +(13+i)\) is the total number of vertices and \(v\geq w \geq 1\) are the leaves at each end of \(T_{n_i} (v, w)\). We demonstrate that, \[{LE}(P_n) \leq {LE}(T_{n_i} (v, w)) \leq {LE}(S_n),\text{ where }1\leq i \leq 15.\]
In the class of trees of diameter \(16\) to \(30\), we also provide a total order by indicating that the Laplacian energies within \(T_{n_i} (v, w)\) for \(1\leq i \leq 15,\) are strictly reducing as a function of \(v\). Furthermore, we observe that in this class of trees, the order by Laplacian energy depends only on their algebraic connectivity, or more specifically, the Laplacian energy of \(T_{n_i} (v, w)\) for \(1\leq i \leq 15,\) increases as their algebraic connectivity decreases.
The theorem mentioned above suggests that Conjecture 1.1’s upper bound holds true for each tree \(T_n\) with \(n\) vertices. It is still unclear what the lower border suggested by Conjecture 1.1. While it is often easy to show that \({LE}(P_n) \leq {LE}(T_n),\) for some specific circumstances, the difficulty occurs when dealing with trees of higher diameters like trees diameter \(16\) to \(30\). Due to the set \({T_n}\)’s unlimited number of trees, the problem still exists in these situations.
Consider the following trees \(T_{n_i} (v, w)\) for \(1\leq i \leq 15,\) of diameter \(16\) to \(30,\) respectively. Note that the integers \(v, w\geq 1\) are the number of pendent vertices of tree. The order of \(T_{n_i} (v, w)\) is \(n_i = v + w + (13+i),\) where \(1\leq i \leq 15.\)
This paper follows the following structure. In section 2 some history and important definitions are reviewed. Section 3 is dedicated to explore the Laplacian characteristic polynomials of \(T_{n_i} (v, w),\) where \(1\leq i \leq 15\) having diameter \(16\) to \(30,\) respectively. Additionally, in the same part, count of Laplacian eigenvalues that exceed the average degree of \(T_{n_i} (v, w),\) where \(1\leq i \leq 15\) will be examined and the Conjecture 1.1 is proved with the help of related results. Finally, in the concluding section 4, we summarize our findings and draw conclusions.
For a simple graph \({G}=(V,E)\) with vertex set \(V = \{v_1,\ldots,v_n\}\), the adjacency matrix is basically a square matrix \(\mathbf{A}\) such that its element \(A_{ij}\) is \(1\) when there is an edge between vertex \(v_i\) and vertex \(v_j\), and \(0\) when there is no edge. The degree matrix \(D({G})\) is a diagonal matrix that tells the degree of each vertex (number of edges connecting to it) of the graph.
For a simple and undirected graph \({G}=(V, E)\) of order \(n\), with adjacency matrix \(\mathbf{A}({G})\)and the degree matrix \(D({G}),\) we will denote the eigenvalues of \(\mathbf{A}({G})\) by \(\lambda_1, \lambda_2,\ldots,\lambda_n,\) which follow to the preceding relations: \[\sum\limits_{r=1}^n\lambda_r=0;~~~\sum\limits_{r=1}^n{\lambda_r}^2= 2m. \tag{1}\] The energy of a graph can be expressed as the total of the absolute values of the of adjacency matrix’s eigenvalues denoted by \[{E}({G}) = \sum_{r=1}^n|\lambda_r|. \tag{2}\] The Laplacian matrix, denoted by \(L({G})\), is defined as \(L({G}) = D({G}) – \mathbf{A}({G})\) and the eigenvalues of \(L({G})\) denoted by \(\mu_1, \mu_2,\ldots,\mu_n\). A well known fact about \(L({G})\) is that it is positive semi-definite with smallest eigenvalue \(\mu_n=0\). Algebraic concreteness, or the eigenvalue \(\mu_{n-1},\) is always smaller than \(1.\) The eigenvalues of \(L({G})\) correspond to the subsequent relations: \[\label{q2} \sum\limits_{r=1}^n\mu_r=2m;~~~\sum\limits_{r=1}^n{\lambda_r}^2= 2m+\sum\limits_{r=1}^n{d_r}^2. \tag{3}\] The Laplacian energy of an undirected graph is denoted by \[\label{q1} {LE}({G}) = \sum_{r=1}^n|\mu_r-\hat{d}|, \tag{4}\] where \(\hat{d}\) is the average degree of \({G}\). It’s important to note that there is a discussion available regarding the graph’s signless Laplacian matrix \({G}\) in [1]. Let \(x_i\) denote the number of vertices of degree \(i, 0\leq i\leq n-1\). We represent by \((x_1, x_2,\cdots, x_{n-1})\), the degree vector of any graph \({G}\). a tree with degree vector isomorphic to \((2, n-1, 0,\cdots, 0)\) is called a path graph, denoted by \(P_n\), and a graph with degree vector isomorphic to \((n-1, 0,0,\cdots, 0, 1)\) is called a star graph and is denoted by \(S_n\). It is a well-known fact that the size of any tree \(T_n\) of order \(n\) is \(n-1.\) The average degree \(d\) of trees was determined by Trevisan et al. [11].
Trevisan et al. [11] have established a lemma regarding the Laplacian energy of path \(P_n.\)
We can now delve into a discussion regarding Laplacian eigenvalues and the Laplacian characteristic polynomial, specifically focusing on trees. There exists a notable lemma in this context, credited to Brouwer and Haemers [2].
We use the technique described in references [6] and [5] to determine the characteristic polynomial of a tree \(T_n\) with \(n\) vertices. This approach may be simply modified to determine the characteristic polynomial of the Laplacian matrix because it is made to operate directly on the tree structure. Let’s give a brief summary of this process in order to assure a thorough knowledge.
The algorithm functions by assigning a rational function \(a(v)=\frac{t}{c}\) to each vertex \(v\) in the tree, where both \(t\) and \(c\) are polynomials within the polynomial ring \({\bf Q}[\lambda].\) Beginning with the tree’s leaves, which are originally given the value \(\lambda- 1\) (assuming the tree is rooted arbitrarily), the process follows a bottom-up methodology. After all of \(v\)’s children have undergone this computation, vertex \(v\) is then assigned the resulting rational function. \[ a(v)= \lambda – d_v – \sum_{c\in C}\frac{1}{a(c),} \tag{5}\] where \(d_v\) is the degree of vertex \(v\) and \(C\) is the collection of its offspring. Following this procedure for each vertex, the characteristic polynomial is calculated by multiplying each function \(a(v)\) by the total number of vertices. \[ \chi(\lambda)=\prod_{v\in V}a(v). \tag{6}\]
In this section, we will explore characteristic polynomials of trees \(T_{n_i} (v, w),\) where \(1\leq i \leq 15,\) having diameters \(16\) to \(30\) respectively, using the above mentioned algorithm. The number of Laplacian eigenvalues greater than the average degree value will also be investigated. Further, the relationship between Laplacian energies of path graphs,trees of diameters \(16\) to \(30\) and star graphs will be discussed by proving the Radenković and Gutman conjecture, that is \[{LE}(P_n) \leq {LE}(T_n) \leq {LE}(S_n).\]
Proof. The algorithm depicted in the previously mentioned section 2 is applied here. ◻
In the forthcoming lemma, we will examine the number of Laplacian eigenvalues that exceed the average degree of \(T_{n_i} (v, w)\) for \(1 \leq i \leq 15,\) respectively.
Proof. We prove the result by considering \(T_{n_1}(v, w)\) for \(i=1\). By Proposition 3.1, it is evident that the multiplicity of Laplacian eigenvalue \(1\) is \(n – 17\). The Laplacian eigenvalues \(\mu_{n}=0\) and \(\mu_{n-1}\leq 1\) are also known. This indicates that there are at least \(n – 15,\) Laplacian eigenvalues less than \(\hat{d}\), since \(1<\hat{d} <2.\) By Lemma 2.3, we have \[\mu_{1}\geq d_{1}+1 = v+2\geq3,~ \rm{for} ~ v\geq 1,\] \[\mu_{2}\geq d_{2} = w + 1\geq 2,~\rm{for} ~ w\geq 1.\] As a result, precisely two Laplacian eigenvalues exceed the value of \(\hat{d}\). Using a similar approach, we can establish the same conclusion for the remaining cases. ◻
Now we will prove that left side of the Conjecture 1.1 is true for class of trees \(T_{n_{i}}(v, w)\) for \(1\leq i \leq 15,\) having diameters \(16\) to \(30,\) respectively.
Proof. Initially, it is important to acknowledge that Trevisan et al. [11], asserted the validity of the inequality \({LE}(P_{n})\leq {LE}(T_{n})\) for \(n\) vertices in the context of any tree \(T_{n}\), specifically for cases where \(n\leq 18\). In the course of our proof, we can safely suppose that \(n\geq 19\). Consider the case \(T_{n_i}(v, w),\) for \(i=1.\)
From Eq. (5), by Proposition 3.1 and by Lemma 3.2, we see that
\[\begin{aligned} {LE}(T_{n_{1}}(v, w))& =|\mu_{1}-\hat{d}| +|\mu_{2}-\hat{d}| +|\mu_{3}-\hat{d}|+\ldots+|\mu_{15}-\hat{d}|+(n-17)|1-\hat{d}|+|\mu_{n-1}-\hat{d}|+|\mu_{n}-\hat{d}|\notag \\ &=\hat{d} +(n-17)(\hat{d}-1) +(\mu_{1}-\hat{d}) +(\mu_{2}-\hat{d}) +(\hat{d}-\mu_{3})+\ldots+(\hat{d}-\mu_{15})+(\hat{d}-\mu_{n-1})\notag \\ & = 15\hat{d} – 2\hat{d} + (n-17)(\hat{d}-1) +(\mu_{1}+\mu_{2})-(\mu_{3}+\ldots+\mu_{15}+\mu_{n-1})\\ & = 13\hat{d} + (n-17)(\hat{d}-1) +(\mu_{1}+\mu_{2})-(\mu_{3}+\ldots+\mu_{15}+\mu_{n-1}). \end{aligned} \tag{7}\]
through the use of Proposition 3.1 and Eq. (6), we observe that \(\mu_{1}+\ldots+\mu_{15}+\mu_{n-1}= v+w+29= n+15\) and substituting \(\hat{d}=2-\frac{2}{n},\) Eq. (7) implies that: \[\label{q4} \begin{aligned} {LE}(T_{n_{1}}(v, w))& = 2n+24+\frac{8}{n}-2(\mu_{3}+\ldots+\mu_{15}+\mu_{n-1}). \end{aligned} \tag{8}\] through the use of Lemma 2.2 and Eq. (8), the above equation becomes: \[\begin{aligned} {LE}(P_{n})-{LE}(T_{n_{1}}(v, w))&\leq n\left(\frac{4}{\pi}-2\right) – \frac{8}{n}-22+2(\mu_{3}+\ldots+\mu_{15}+\mu_{n-1}). \end{aligned}\] Since \(\mu_{3}+\ldots+\mu_{15}<2, \quad \mu_{n-1}<1\) and \(\frac{8}{n}>0,\) so it follows; \[{LE}(P_{n})-{LE}(T_{n_{1}}(v, w))\leq n\left(\frac{4}{\pi}-2\right) – \frac{8}{n}+6,\] which is negative for \(n > 18.\) ◻
In this research study, Conjecture 1.1 was examined for some special classes of trees \(T_{n_i} (v, w),\) where \(1\leq i \leq 15,\) having diameters \(16\) to \(30,\) respectively.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.