On Radenković and Gutman conjecture for certain classes of trees

1. Introduction

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,\dots ,{\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,\dots ,{\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 ${\displaystyle \frac{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\le i\le 15,$ respectively. Where $n_i=v+w+(13+i)$ is the total number of vertices and $v\ge w\ge 1$ are the leaves at each end of $T_{n_i}(v,w)$. We demonstrate that, $$LE(P_n)\le LE(T_{n_i}(v,w))\le LE(S_n),\text{ where }1\le i\le 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\le i\le 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\le i\le 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)\le 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\le i\le 15,$ of diameter $16$ to $30,$ respectively. Note that the integers $v,w\ge 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\le i\le 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\le i\le 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\le i\le 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.

2. Meterials and methods

For a simple graph $G=(V,E)$ with vertex set $V=\{v_1,\dots ,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,\dots ,{\lambda }_n,$ which follow to the preceding relations: $$\begin{array}{}\text{(1)}& \sum _{r=1}^n{\lambda }_r=0;\sum _{r=1}^n{{\lambda }_r}^2=2m.\end{array}$$ The energy of a graph can be expressed as the total of the absolute values of the of adjacency matrix’s eigenvalues denoted by $$\begin{array}{}\text{(2)}& E(G)=\sum _{r=1}^n|{\lambda }_r|.\end{array}$$ 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,\dots ,{\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: $$\begin{array}{}\text{(3)}& \sum _{r=1}^n{\mu }_r=2m;\sum _{r=1}^n{{\lambda }_r}^2=2m+\sum _{r=1}^n{d_r}^2.\end{array}$$ The Laplacian energy of an undirected graph is denoted by $$\begin{array}{}\text{(4)}& LE(G)=\sum _{r=1}^n|{\mu }_r-\hat{d}|,\end{array}$$ 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\le i\le 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 $\mathbf{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. $$\begin{array}{}\text{(5)}& a(v)=\lambda –d_v–\sum _{c\in C}\frac{1}{a(c),}\end{array}$$ 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. $$\begin{array}{}\text{(6)}& \chi (\lambda )=\prod _{v\in V}a(v).\end{array}$$

3. Results and discussions

3.1. Construction of Laplacian characteristic polynomial and Laplacian eigenvalues

In this section, we will explore characteristic polynomials of trees $T_{n_i}(v,w),$ where $1\le i\le 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)\le LE(T_n)\le LE(S_n).$$

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\le i\le 15,$ respectively.

3.2. Proof of Conjecture

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\le i\le 15,$ having diameters $16$ to $30,$ respectively.

4. Conclusion

In this research study, Conjecture 1.1 was examined for some special classes of trees $T_{n_i}(v,w),$ where $1\le i\le 15,$ having diameters $16$ to $30,$ respectively.