# Some Chemistry Indices of Clique-Inserted Graph of a Strongly Regular Graph

Authors: Chun-Li Kan; Ying-Ying Tan; Jia-Bao Liu; Bao-Hua Xing
Journal: Complexity
 (2021)

---

## Abstract

In this paper, we give the relation between the spectrum of strongly regular graph and its clique-inserted graph. The Laplacian spectrum and the signless Laplacian spectrum of clique-inserted graph of strongly regular graph are calculated. We also give formulae expressing the energy, Kirchoff index, and the number of spanning trees of clique-inserted graph of a strongly regular graph. And, clique-inserted graph of the triangular graphTt, which is a strongly regular graph, is enumerated.


---

## Body

## 1. Introduction

Gutman in [1] officially gave the definition of graph energy, which has a widespread application in chemistry and physics [1–3]. Koolen and Moulton in [4] proved that the graph with maximal energy is a strongly regular graph. Furthermore, Haemers in [5] show that the maximal energy of strongly regular graphs is corresponding to a type of Hadmada matrix. Zhang in [6] suggested that the iterative operation of clique-insertion can be considered as a way to extend complex networks. It is meaningful to calculate some indices of clique-inserted graph of a strongly regular graph.Algebraic graph theory, as a part of graph theory, mainly investigates the relationship between parameters and structure of a graph by matrix theory. The research on the spectrum of graph enriches graph theory. Collatz and Sinogowitz [7] firstly used adjacency matrix to study the spectrum and structure of graphs. However, many scholars gradually find that the adjacency spectrum has limitations, especially in solving the chemical problem of distinguishing isomers (i.e., homographs). Compared with adjacency matrix, Laplacian matrix can reflect the properties of graphs more accurately, see [8]. The Laplacian spectrum of a graph contributes to many invariants of a graph, such as Kirchhoff index and connectivity. These indices can further reflect some of the chemical properties of a graph. A tree of diameter 4 with minimum Laplacian spectral radius is determined in [9]. The properties of the Laplacian matrix and the application of the topological indices were studied in [10]. Cvetkovic’ et al. in [8] defined the signless Laplacian spectrum of finite graphs and their properties. With the further research on the internal characteristics of networks, some scholars have found that many actual networks are composed of several groups or clusters. These groups or clusters have relatively close connections among nodes, but relatively few connections between each cluster, which is called “community structure.” Revealing its community structure is very important for the analysis of network structure, and the community division method based on the graph spectrum effectively solves this problem.The research on topological indices of graphs is a hot topic in graph theory. Many topological indices have applied in the field of chemistry and physics [11]. For an electrical network, the Kirchhoff index is proportional to the electrical energy consumed by the network per unit time [6]. Richard defines the Bruhat graph and gives the topological indices for it in [12]. From the perspective of complex networks, topological indices can reflect the overall characteristics [13], effectively evaluate the reliability of complex networks [14], protect useful networks, and block viral network [15]. The geometric arithmetic indices are proposed by Vukicˇevic’ and Furtula in [16], which have a nice predictive ability to entropy, centrifugal factor, and other physical properties.The paper is arranged as follows. We give some preliminaries and calculate spectrum of clique-inserted graph of a strongly regular graph in Section2. In Section 3, we introduce some energies and typical topological indices. An example is given with respect to indices in Section 4.


## 2. Spectra of Clique-Inserted Graph of a Strongly Regular Graph

All graphs in this paper are simple and connected. A simple graph requires that there be neither a cycle nor a pair of vertices connected by two edges. LetG be a graph whose vertices are 1,2,…,n. The adjacency matrix of G is a square matrix of order n, represented by AG. If vertices i and j are adjacent, then i,j is 1 and 0, otherwise. The eigenvalues of a graph G are the eigenvalues of the adjacency matrix AG, denoted by λ1≥λ2≥⋯≥λn. Let DG be a diagonal matrix, and the diagonal elements are the degrees of the corresponding vertices of G. The Laplacian matrix and the signless Laplacian matrix of G are LG=DG−AG and L+G=DG+AG, respectively. We denote the eigenvalues of LG by μ1≤μ2≤⋯≤μn and the eigenvalues of L+G by μ1+≥μ2+≥⋯≥μn+.A graph withn vertices is said to be k-regular if each of its vertices has degree k. Furthermore, if any two adjacent vertices have a common neighbour and any pair of distinct nonadjacent vertices have c common neighbour, then the graph is called a strongly regular graph with parameters n,k,a,c. The strongly regular graph has exactly three eigenvalues: k,θ,andτ (because θτ<0, we usually assume that τ<0) with θ=a−c+E/2andτ=a−c−E/2, where E=a−c2+4k−c. The multiplicities mθ and mτ corresponding to θ and τ are given, respectively, by(1)mθ=−n−1τ+kθ−τ,mτ=n−1θ+kθ−τ.By the property of the adjacency matrix, we have(2)mθ+mτ=n−1,mθθ+mττ=−k.The graph obtained by replacing every vertex of a graphG by a clique (i.e., a complete graph) with s vertices is called an s-clique-inserted graph of G [17, 18]. Let u be a vertex in G whose degree is greater than 0. If we obtain G by replacing the vertex u with a 3-clique (as illustrated in Figure 1), then G˜ is said to a 3-clique-inserted graph at u.Figure 1
The 3-clique-inserted graph at vertexu.
(a)(b)Next, we will calculate the spectrum of clique-inserted graph of a strongly regular graph. We firstly introduce a lemma before this.Lemma 1 (see [19]).
LetG˜ be an s-clique-inserted graph of a graph G. If the adjacency spectrum of G is(3)λ0n0,λ1n1,…,λtnt,then the adjacency spectrum of G˜ is(4)sλ0+1−1n0,sλ1+1−1n1,…,sλt+1−1nt,−1s−1n0+n1+⋯+nt.
LetG be a strongly regular graph; its parameters and spectrum are n,k,a,c and k1,θmθ,τmτ, respectively. And, G˜ is a clique-inserted graph of G. We can see that G˜ is a regular graph with degree k˜=sk+1−1. By Lemma 1, we conclude that the adjacency spectrum of G˜ is sk+1−11,sθ+1−1mθ,sτ+1−1mτ,−1s−11+mθ+mτ. The eigenvalues of G˜, denoted by λi1≤i≤4, are sk+1−1,sθ+1−1,sτ+1−1,−1.
For the regular graphG˜, we have μi=k˜−λi. Then, we obtain that the Laplacian eigenvalues of G˜ are 0,sk−θ,sk−τ,andsk+1. So, the Laplacian spectrum of G˜ is 01,sk−θmθ,sk−τmτ,sk+1s−11+mθ+mτ. By μi+=k˜+λi, the signless Laplacian eigenvalues of G˜ are 2sk+1−2,sk+θ+2−2,sk+τ+2−2,andsk+1−2. The signless Laplacian spectrum of G˜ is {2sk+1−21,sk+θ+2−2mθ,sk+τ+2−2mτ,sk+1−2s−11+mθ+mτ}. Then, we have the theorem as follows.Theorem 1.
LetG be a strongly regular graph with parameters n,k,a,c, and adjacency spectrum is k1,θmθ,τmτ. If G˜ is a clique-inserted graph of G, then the adjacency spectrum of G˜ is(5)sk+1−11,sθ+1−1mθ,sτ+1−1mτ,−1s−11+mθ+mτ,the Laplacian spectrum of G˜ is(6)01,sk−θmθ,sk−τmτ,sk+1s−11+mθ+mτ,and the signless Laplacian spectrum of G˜ is(7)2sk+1−21,sk+θ+2−2mθ,sk+τ+2−2mτ,sk+1−2s−11+mθ+mτ.


## 3. Applications of Spectra

In Section2, we obtain the spectrum of G˜. Now, we use the spectrum of G˜ to explore the corresponding other quantities. There are a lot of literature studies about the applications of spectrum of matrix, see [3, 9, 20, 21]. Some definitions will be given at first in each part.


### 3.1. Energy, Laplacian Energy, and Signless Laplacian Energy ofG˜

The energy of a graph is defined as the spectrum of adjacency matrix of graph which is put forward firstly by Gutman in [1]. The study of graph energy is one of the earliest and the most extensively studied in graph theory. The chemist Huckel obtained the graph model of the corresponding molecules through the approximate treatment of unsaturated hydrocarbons when he studied organic molecular energy. And, he used the eigenvalues of the corresponding matrix to represent the energy levels of specific electrons [8]. Graph energy has a strong application background in chemistry, such as establishing mathematical models for organic molecules and analysing energy levels and stability.LetG be a connected simple graph with n vertices. Then the energy of G is(8)EG=∑i=1nλiG.Now we calculate the energy ofG˜. For τ≤−1/2, by Theorem 1, we have(9)EG˜=∑i=1snλiG˜=1sk+1−1+mθsθ+1−1+mτ1−sτ+1+s−11+mτ+mθ=sk+1+mθθ+1−mττ+1+1+mθ+mτ−1−mθ+mτ−1+mθ+mτ=sk+mθθ−mττ+21+mθs−1.By (2),(10)EG˜=s−2mττ+21+mθs−1.Substitute the valuesmθ and mτ in (1) into (10), we get(11)EG˜=−2τsn−1θ+kθ−τ+21−n−1τ+kθ−τs−1.For−1/2≤τ<0, substitute the eigenvalue of G˜ into equation (8):(12)EG˜=∑i=1snλiG˜=1sk+1−1+mθsθ+1−1+mτsτ+1−1+s−11+mτ+mθ=2ns−1.The energy of the graph is calculated from the spectrum of the adjacency matrix, and in algebraic graph theory, the Laplacian spectrum of graphs and the applications have also received extensive attention. Although the adjacency spectrum can reflect some properties of the graph, there are limitations, especially in the problem of the same spectrum. In [22], the Laplacian energy is used to propagate viruses in intuitionistic fuzzy networks. Cvetković et al. in [23] defined the signless Laplacian spectrum of finite graphs and their properties. Some scholars studied the maximization problem of the signless Laplacian spectrum of some special graphs [24, 25].The Laplacian matrix adds degree matrix, a parameter closely related to graph structure, on the basis of adjacency matrix. The Laplacian spectrum has some properties of the adjacency spectrum. Letμ1,μ2,…,μn be the Laplacian eigenvalues of G. And, the Laplacian energy is defined as(13)LEG=∑i=1nμi−2mn.Letμ1+,μ2+,…,μn+ be the signless Laplacian eigenvalues of G. The signless Laplacian energy is defined as(14)LE+G=∑i=1nμi+−2mn.IfG is a regular graph with n vertices and m edges and degree k, we have 2m=nk. Then, LEG=∑i=1nμi−k=∑i=1n−λi=EGandLE+G=∑i=1nμi+−k=∑i=1nλi=EG. So, for the clique-inserted graph G˜, we have(15)LE+G˜=LEG˜=EG˜=−2τsn−1θ+kθ−τ+21−n−1τ+kθ−τs−1,τ≤−12,2ns−1,−12<τ<0.


### 3.2. Kirchhoff Index ofG˜

In the early research on the topological index of graphs, many scholars focused their attention on the ordinary graph distance. Until the rise of electrical network theory, D. J. Klein and M. Randic′ put forward the concept of the resistance distance of graphs in [26], which is a topology index defined by the resistance distance. This new distance function has been favoured by chemists since it was proposed. In the field of physics and engineering, the calculation of resistance between two points is the core problem of circuit theory research. In mathematics, various formulae for calculating resistance distance are produced one after another. For an electrical network, it is a direct proportion to the electrical energy consumed by the network per unit time [10]. The Kirchhoff index can be used to describe the structural characteristics of molecules and define the topological radius of polymers in chemistry [26]. Small value of Kirchhoff index means strong network robustness in network science [27, 28].The Kirchhoff index andμ1,μ2,…,μn have the following relationship:(16)KfG=n∑i=2n1μi.According to Theorem1, substituting the Laplacian spectrum of G˜ into equation (16), we get the Kirchhoff index of G˜:(17)KfG˜=sn∑i=2sn1μi=snmθ⋅1sk−θ+mτ⋅1sk−τ+s−1n⋅1sk+1=n2s−1k+1+nmθk−θ+mτk−τ.


### 3.3. The Number of Spanning Trees ofG˜

The number of spanning trees is a minimum connected subgraph that containing all vertices of the connected graph. It is also a measure of the structure of a graph. The spanning trees are used in network reliability analysis, circuit design in physics, self-organized criticality [29], and so on. In computer network, it is an important index to evaluate network security [30, 31]. In the router system, the whole router network can be regarded as a graph G, all routers as vertex i of graph G, and the connection relationship between routers as edge e of graph G. When a vertex and its adjacent edges are removed from a graph G, the less the number of spanning trees of the new graph, the more important the point is.The number of spanning trees of a graphG with order n is defined as(18)τG=1n∏i=2nμi.We can determine the connectivity of the graphG from the number of spanning trees τG. The larger the number is, the more connected the graph is, see [8]. There are two graphs in Figure 2. The left graph of Figure 2 is Petersen graph with Laplacian spectrum 0,25,54. The Laplacian spectrum of the right graph is 0,1.4384,33,5.5616. According to formula (16), we get τG of the left graph is 2000 and the right graph is 43. The connectivity in left graph is stronger than that in the right graph.Figure 2
Which graph is best according to connectivity?.
(a)(b)According to Theorem1, substitute the Laplacian spectrum of G˜ into formula (18), we obtain the number of spanning trees of G˜ is(19)τG˜=1sn∏i=2snμi=1snsk−θmθsk−τmτsk+1s−1n=1nssn−2k−θmθk−τmτk+1s−1n.


## 3.1. Energy, Laplacian Energy, and Signless Laplacian Energy ofG˜

The energy of a graph is defined as the spectrum of adjacency matrix of graph which is put forward firstly by Gutman in [1]. The study of graph energy is one of the earliest and the most extensively studied in graph theory. The chemist Huckel obtained the graph model of the corresponding molecules through the approximate treatment of unsaturated hydrocarbons when he studied organic molecular energy. And, he used the eigenvalues of the corresponding matrix to represent the energy levels of specific electrons [8]. Graph energy has a strong application background in chemistry, such as establishing mathematical models for organic molecules and analysing energy levels and stability.LetG be a connected simple graph with n vertices. Then the energy of G is(8)EG=∑i=1nλiG.Now we calculate the energy ofG˜. For τ≤−1/2, by Theorem 1, we have(9)EG˜=∑i=1snλiG˜=1sk+1−1+mθsθ+1−1+mτ1−sτ+1+s−11+mτ+mθ=sk+1+mθθ+1−mττ+1+1+mθ+mτ−1−mθ+mτ−1+mθ+mτ=sk+mθθ−mττ+21+mθs−1.By (2),(10)EG˜=s−2mττ+21+mθs−1.Substitute the valuesmθ and mτ in (1) into (10), we get(11)EG˜=−2τsn−1θ+kθ−τ+21−n−1τ+kθ−τs−1.For−1/2≤τ<0, substitute the eigenvalue of G˜ into equation (8):(12)EG˜=∑i=1snλiG˜=1sk+1−1+mθsθ+1−1+mτsτ+1−1+s−11+mτ+mθ=2ns−1.The energy of the graph is calculated from the spectrum of the adjacency matrix, and in algebraic graph theory, the Laplacian spectrum of graphs and the applications have also received extensive attention. Although the adjacency spectrum can reflect some properties of the graph, there are limitations, especially in the problem of the same spectrum. In [22], the Laplacian energy is used to propagate viruses in intuitionistic fuzzy networks. Cvetković et al. in [23] defined the signless Laplacian spectrum of finite graphs and their properties. Some scholars studied the maximization problem of the signless Laplacian spectrum of some special graphs [24, 25].The Laplacian matrix adds degree matrix, a parameter closely related to graph structure, on the basis of adjacency matrix. The Laplacian spectrum has some properties of the adjacency spectrum. Letμ1,μ2,…,μn be the Laplacian eigenvalues of G. And, the Laplacian energy is defined as(13)LEG=∑i=1nμi−2mn.Letμ1+,μ2+,…,μn+ be the signless Laplacian eigenvalues of G. The signless Laplacian energy is defined as(14)LE+G=∑i=1nμi+−2mn.IfG is a regular graph with n vertices and m edges and degree k, we have 2m=nk. Then, LEG=∑i=1nμi−k=∑i=1n−λi=EGandLE+G=∑i=1nμi+−k=∑i=1nλi=EG. So, for the clique-inserted graph G˜, we have(15)LE+G˜=LEG˜=EG˜=−2τsn−1θ+kθ−τ+21−n−1τ+kθ−τs−1,τ≤−12,2ns−1,−12<τ<0.


## 3.2. Kirchhoff Index ofG˜

In the early research on the topological index of graphs, many scholars focused their attention on the ordinary graph distance. Until the rise of electrical network theory, D. J. Klein and M. Randic′ put forward the concept of the resistance distance of graphs in [26], which is a topology index defined by the resistance distance. This new distance function has been favoured by chemists since it was proposed. In the field of physics and engineering, the calculation of resistance between two points is the core problem of circuit theory research. In mathematics, various formulae for calculating resistance distance are produced one after another. For an electrical network, it is a direct proportion to the electrical energy consumed by the network per unit time [10]. The Kirchhoff index can be used to describe the structural characteristics of molecules and define the topological radius of polymers in chemistry [26]. Small value of Kirchhoff index means strong network robustness in network science [27, 28].The Kirchhoff index andμ1,μ2,…,μn have the following relationship:(16)KfG=n∑i=2n1μi.According to Theorem1, substituting the Laplacian spectrum of G˜ into equation (16), we get the Kirchhoff index of G˜:(17)KfG˜=sn∑i=2sn1μi=snmθ⋅1sk−θ+mτ⋅1sk−τ+s−1n⋅1sk+1=n2s−1k+1+nmθk−θ+mτk−τ.


## 3.3. The Number of Spanning Trees ofG˜

The number of spanning trees is a minimum connected subgraph that containing all vertices of the connected graph. It is also a measure of the structure of a graph. The spanning trees are used in network reliability analysis, circuit design in physics, self-organized criticality [29], and so on. In computer network, it is an important index to evaluate network security [30, 31]. In the router system, the whole router network can be regarded as a graph G, all routers as vertex i of graph G, and the connection relationship between routers as edge e of graph G. When a vertex and its adjacent edges are removed from a graph G, the less the number of spanning trees of the new graph, the more important the point is.The number of spanning trees of a graphG with order n is defined as(18)τG=1n∏i=2nμi.We can determine the connectivity of the graphG from the number of spanning trees τG. The larger the number is, the more connected the graph is, see [8]. There are two graphs in Figure 2. The left graph of Figure 2 is Petersen graph with Laplacian spectrum 0,25,54. The Laplacian spectrum of the right graph is 0,1.4384,33,5.5616. According to formula (16), we get τG of the left graph is 2000 and the right graph is 43. The connectivity in left graph is stronger than that in the right graph.Figure 2
Which graph is best according to connectivity?.
(a)(b)According to Theorem1, substitute the Laplacian spectrum of G˜ into formula (18), we obtain the number of spanning trees of G˜ is(19)τG˜=1sn∏i=2snμi=1snsk−θmθsk−τmτsk+1s−1n=1nssn−2k−θmθk−τmτk+1s−1n.


## 4. An Example

In this section, we will give an example of calculations, that is, the clique-inserted graph of the triangular graphTt. The Johnson graph Jt,2 is also called the triangular graph Tt (see Figure 3, for example, T4).Figure 3
A graph ofT4.In [20], we know Tt is a strongly regular graph with parameters t2,2t−4,t−2,4 and spectrum 2t−41,t−4t−1,−2t2−3t/2. Let T˜ be the clique-inserted graph of Tt. Because τ=−2<−1/2, according to (10), the energy of T˜ is(20)ET˜=2st2−3t+2ts−1=2tst−2−1.By (17), the Kirchhoff index of T˜ is(21)KfT˜=t2t−1242t−3s−1+t−122+t2t−38.By (19), the number of spanning trees of T˜ is(22)τT˜=4⋅sstt−1/2−2⋅tt−2⋅2t−2tt−3/2−1⋅2t−3s−1tt−1/2.


## 5. Conclusions

In this paper, we get the graphG˜ by applying the operation of clique insertion to a strongly regular graph G and obtain the relationships between the adjacency spectrum of graph G and G˜. Furthermore, the Laplacian spectrum and signless Laplacian spectrum of G˜ are calculated. Based on the above conclusions, we give formulae expressing the energy, Kirchhoff index and the number of spanning trees of G˜.



---

*Source: 7671212-2021-06-29.xml*