# On the Eccentric Connectivity Polynomial ofℱ-Sum of Connected Graphs

Authors: Muhammad Imran; Shehnaz Akhter; Zahid Iqbal
Journal: Complexity
 (2020)

---

## Abstract

The eccentric connectivity polynomial (ECP) of a connected graphG=VG,EG is described as ξcG,y=∑a∈VGdegGayecGa, where ecGa and degGa represent the eccentricity and the degree of the vertex a, respectively. The eccentric connectivity index (ECI) can also be acquired from ξcG,y by taking its first derivatives at y=1. The ECI has been widely used for analyzing both the boiling point and melting point for chemical compounds and medicinal drugs in QSPR/QSAR studies. As the extension of ECI, the ECP also performs a pivotal role in pharmaceutical science and chemical engineering. Graph products conveniently play an important role in many combinatorial applications, graph decompositions, pure mathematics, and applied mathematics. In this article, we work out the ECP of ℱ-sum of graphs. Moreover, we derive the explicit expressions of ECP for well-known graph products such as generalized hierarchical, cluster, and corona products of graphs. We also apply these outcomes to deduce the ECP of some classes of chemical graphs.


---

## Body

## 1. Introduction

LetG be an n-vertex simple and connected graph with the vertex set VG and the edge set EG. For a given graph G, the order and size are symbolized by VG and EG, respectively. The degree of a∈VG is the number of adjacent vertices to a in G, and it is represented by degGa. For a1,a2∈VG, the distance between a1 and a2, denoted with dGa1,a2, is defined as the length of the shortest path among a1 and a2 in G, and the eccentricity ecGa1 is the largest distance among a1 and any other vertex a2 of G. We use notions Pn and Cn for the n-vertex path and cycle, respectively. The line graph denoted by LG of G is the graph whose vertices are the edges of the original graph; two vertices e1 and e2 are connected if and only if they share a common end vertex in G. The joint G+G′ of graphs G and G′ is the graph union G∪G′ including all the edges joining VG and VG′.A molecular descriptor is a numeric measure of a graph which characterizes its topology. In organic chemistry, topological invariants have established many applications in pharmaceutical drug design, QSAR/QSPR studies, chemical documentation, and isomer discrimination. Some effective topological classes such as degree based, degree distance, eccentric connectivity indices, and so on are established as molecular invariants. In recent years, the study of eccentric invariants for chemical molecular structure has become one of the flourishing lines of research in theoretical chemistry.The ECI ofG is a newly discovered distance-based topological invariant which was put forward by Sharma et al. [1] and is defined as follows:(1)ξcG=∑a∈VGdegGaecGa.In recent times, a modification ofξcG is used and famous as the total eccentricity index τG. It can be defined as(2)τG=∑a∈VGecGa.The study of polynomials has been a valuable tool to describe the complex and classical behavior of dynamical systems. Furthermore, the polynomial approaches have also been utilized to figure out the central problems such as robustness, stability, and controllability. Polynomial theory can also be implemented in nonlinear, uncertain, hybrid, and time-delay systems and model predictive control. In recent years, there have been numerous works on graph polynomials related with various topological indices. For the detailed discussion about the different types of polynomials such as characteristic, chromatic, edge cover, domination, matching, and clique polynomials and their related studies, we refer the readers to [2–7].Ashraf and Jalali gave the concept of ECP in [8], which can be specified as(3)ξcG,y=∑a∈VGdegGayecGa.The total eccentricity polynomial ofG can be expressed as follows:(4)τG,y=∑a∈VGyecGa.It is an easy exercise to see that the eccentric connectivity and total eccentricity indices can be acquired from their related polynomials by taking their first derivatives aty=1.Graph products play a significant role in many combinatorial applications, graph decompositions into isomorphic subgraphs, and not only in pure mathematics but also in applied mathematics. In [9, 10], Akhter and Imran investigated the degree-based topological invariants for ℱ-sum of graphs. De et al. [11] presented the results related to the total eccentricity index of some products of graphs. The ECI of ℱ-sum graphs in the form of different invariants has been computed in [12]. Došlić and Saheli [13] established the ECI of composite graphs. The ECP of several classes of composite graphs, including Cartesian product, symmetric difference, disjunction, join of graphs, and composition of graphs have been computed in [14]. For more information on different aspects of ECP, one can see [15–21].Inspired by Yang et al. [22], we continue the research on finding the indices and polynomials of ℱ-sum of graphs. This article is arranged as follows. First, we find the ECP of the generalized hierarchical product of graphs, and as applications, we give explicit outcomes for chemical graphs such as a truncated cube and linear phenylene. Furthermore, we compute the ECP of ℱ-sum of graphs and give its applications in Section 3. Finally, we determine the ECP of the cluster and the corona products of graphs in the last section.Proposition 1.
(see [23]). Let Cl and Pl denote the l-vertex cycle and path, respectively. Then,(1)
ξcCl,y=2lyl−1/2iflis odd,2lyl/2iflis even.(2)
τCl,y=lyl−1/2iflis odd,lyl/2iflis even.(3)
ξcPl,y=2yl−1+4∑i=2l−1/2yl−i+2yl−1/2iflis odd,2yl−1+4∑i=2l/2yl−iiflis even.(4)
τPl,y=2∑i=1l−1/2yl−i+yl−1/2iflis odd,2∑i=1l/2yl−iiflis even.


## 2. Generalized Hierarchical Product

Barrière et al. [24] brought in the concept of the generalized hierarchical product, that is, a generalization of the (standard) hierarchical product and Cartesian product of graphs [25]. The generalized hierarchical product of G and G′ with ∅≠U⊆VG is represented by GU⊓G′. It has vertex set VG×VG′ and a1,b1a2,b2∈EGU⊓G′ if a1=a2∈U and b1b2∈EG′ or b1=b2 and a1a2∈EG. For a1,a2∈VG, a path between a1 and a2 through U is a a1a2-path in G including some vertex c∈U (vertex c could be the vertex a1 or a2). For a1,a2∈VG, the distance between these vertices through U, symbolized as dGUa1,a2, is the length of a smallest a1a2-path through U. It is easily seen that, if one of the vertices a1 and a2 belongs to U, then dGUa1,a2=dGa1,a2 (see [26]). Now, in Lemma 1, we describe the distinct properties of this product.Lemma 1.
(see [24]). Let G and G′ be graphs with U⊆VG. Then,(a)
VGU⊓G′=VGVG′ and EGU⊓G′=EGVG′+EGU.(b)
degGU⊓G′a1,b1=degGa1+degG′b1ifa1∈U,degGa1ifa1∈VG\U.(c)
dGU⊓G′a1,b1,a2,b2=dGUa1,a2+dG′b1,b2ifb1≠b2,dGa1,a2ifb1=b2.(d)
ecGU⊓G′a1,b1=ecGUa1+ecG′b1.
In the next theorem, we give the expression of the ECP ofGU⊓G′ in terms of eccentric connectivity and total eccentricity polynomials of GU and G′.Theorem 1.
LetG and G′ be graphs with U⊆VG. Then,(5)ξcGU⊓G′,y=ξcGU,yτG′,y+εGU,yξcG′,y,where εGU,y=∑a∈UyecGUa.Proof.
From Lemma1 and formula (3), we get(6)ξcGU⊓G′,y=∑a,b∈VGU⊓G′degGU⊓G′a,byecGU⊓G′a,b=∑a∈U∑b∈VG′degGa+degG′byecGUa+ecG′b+∑a∈VG∖U∑b∈VG′degGayecGUa+ecG′b=∑a∈UdegGayecGUa∑b∈VG′yecG′b+∑a∈UyecGUa∑b∈VG′degG′byecG′b+∑a∈VG∖UdegGayecGUa∑b∈VG′yecG′b=ξcGU,yτG′,y+εGU,yξcG′,y.
This finishes the proof.
The Cartesian productG□G′ of graphs G and G′ has the vertex set VG×VG′ and a1,b1a2,b2∈EG□G′ if a1=a2 and b1b2∈EG′ or b1=b2 and a1a2∈EG. By using Theorem 1, we can deduce the following theorem by putting U=VG.Theorem 2.
(see [14]). Let G and G′ be two connected graphs. Then,(7)ξcG□G′,y=ξcG,yτG′,y+τG,yξcG′,y.Example 1.
The molecular graph of truncated cube can be represented as a generalized hierarchical product ofGU and P2 (depicted in Figure 1), with U=a1,a4,a9,a12. It is easy task to see that τP2,y=ξcP2,y=2y and(8)εGU,y=∑a∈UyecGUa=4y5,ξcGU,y=∑a∈VGdegGayecGUa=32y5.
Then by Theorem1, we have ξcGU⊓P2,y=32y52y+4y52y=72y6.Figure 1
The molecular graph of truncated cube.Example 2.
The linear phenyleneFn with n>1 benzene ring is the graph that is also recognized by P3nU⊓P2 (depicted in Figure 2), with U=a3k1≤k≤n∪a3k+10≤k≤n−1. By tedious computation, we get τP2,y=ξcP2,y=2y and(9)εP3nU,y=∑a∈UyecP3nUa=2∑i=1n/2y3n−iy2+1,ifnis even,2∑i=1n−1/2y3n−iy2+1,ifnis odd,ξcP3nU,y=∑a∈VGdegGayecGUa=2y3n−1+4∑i=23n/2y3n−i,ifnis even,2y3n−1+4∑i=23n+1/2y3n−i+2y3n+1/2,ifnis odd.
Then by Theorem1, we have(10)ξcP3nU⊓P2,y=4y3n+8∑i=23n/2y3n−i+1+4∑i=1n/2y3n−i+1y2+1,ifnis even,4y3n−1+8∑i=23n+1/2y3n−i+1+4y3n+1/2+4∑i=1n−1/2y3n−i+1y2+1,ifnis odd.Figure 2
The linear phenyleneFn=P3nU⊓P2.


## 3.ℱ-Sum of Graphs

Eliasi and Taeri initiated the notion ofℱ-sum of a graph in [27], and they studied the Wiener index of it. Some explicit expressions of various PI indices have been presented for ℱ-sum graphs in [28]. Metsidik et al. [29] studied the Wiener indices of ℱ-sum graphs.The subdivision graph ofG, symbolized by SG, can be sketched from G by interchanging each edge of G with a path P2. The line superposition graph QG of G can be attained from G by placing a new vertex into each edge of G and then linking with edges of each pair of new vertices on adjacent edges of G. The triangle parallel graph of G is symbolized by ℛG, and it can be constructed from G by interchanging each edge of G with a triangle.The total graph ofG is represented by TG, which has edges and vertices of G as its own vertices, and adjacency in TG is described as the adjacency or incidence of the related elements (vertices and edges) of G.Letℱ be one of the aforementioned operations S,T,Q, or ℛ. The ℱ-sum of graphs G and G′ is represented by G+ℱG′. It has vertex set VG∪EG×VG′, and a1,b1a2,b2∈EG+ℱG′ if and only if a1=a2∈VG and b1b2∈EG′ or b1=b2∈VG′ and a1a2∈EℱG.Lemma 2 (see [12]).
LetG be a connected graph. If U=VG, then(a)
VSG=VG+EG and ESG=2EG.(b)
degSGUa=degGaifa∈U,2ifa∈VSG\U.(c)
ecSGUa=2ecGaifa∈U,2ecLGa+1ifa∈VSG\U.Theorem 3.
LetGn≥2 and G′ be graphs. Then,(11)ξcG+SG′,y=ξcG,y2τG′,y+2yτLG,y2τG′,y+τG,y2ξcG′,y.Proof.
Followed by formula (3) and Lemma 2, we have(12)ξcSGU,y=∑a∈VSGdegSGayecSGUa=∑a∈UdegSGayecSGUa+∑a∈VSG\UdegSGayecSGUa=∑a∈UdegGay2ecGa+2∑a∈VSG\UyecSGUa=∑a∈UdegGay2ecGa+2∑a∈VLGy2ecLGa+1=ξcG,y2+2yτLG,y2.(13)εSGU,y=∑a∈UyecSGUa=∑a∈VGy2ecGa=τG,y2.
Combining these results with (5), we get the desired result. This finishes the proof.Lemma 3 (see [12]).
LetG be a connected graph. If U=VG, then(a)
VℛG=VG+EG and EℛG=3EG.(b)
degℛGUa=2degGaifa∈U,2ifa∈VℛG\U.(c)
ecℛGUa=ecGaifa∈U,ecLGa+1ifa∈VℛG\U.Theorem 4.
LetGn≥2 and G′ be graphs. Then,(14)ξcG+ℛG′,y=2ξcG,y2τG′,y+2yτLG,yτG′,y+τG,yξcG′,y.Proof.
With the help of definition of the ECP and Lemma3, we have(15)ξℛGU,y=∑a∈VℛGdegℛGayecℛGUa=∑a∈UdegℛGayecℛGUa+∑a∈VℛG\UdegℛGayecℛGUa=∑a∈UdegGay2ecGa+2∑a∈VℛG\UyecℛGUa=2∑a∈UdegGay2ecGa+2∑a∈VLGyecLGa+1=2ξcG,y2+yτLG,y.(16)εℛGU,y=∑a∈UyecℛGUa=∑a∈VGyecGa=τG,y.
Combining these results with (5), we get following:(17)ξcG+ℛG′,y=2ξcG,y2+yτLG,yτG′,y+τG,yξcG′,y=2ξcG,y2τG′,y+2yτLG,yτG′,y+τG,yξcG′,y.
This completes the proof.Lemma 4.
(see [12]). Let G be a connected graph. If U=VG, then(a)
VQG=VG+EG and EQG=2EG+ELG.(b)
degQGUa=degGaifa∈U,degLGa+2ifa∈VQG\U.(c)
ecQGUa=ecGa+1ifa∈U,ecLGa+1ifa∈VQG\U.Theorem 5.
LetGn≥2 and G′ be graphs. Then,(18)ξcG+QG′,y=yξcG,y+ξcLG,y+yτLG,yτG′,y+yτG,yξcG′,y.Proof.
By formula (3) and Lemma 4, we have(19)ξcQGU,y=∑a∈VQGdegQGayecQGUa=∑a∈UdegQGayecQGUa+∑a∈VQG\UdegQGayecQGUa=∑a∈UdegGayecGa+1+∑a∈VLGdegLGa+1yecLGUa+1=y∑a∈UdegGayecGa+∑a∈VLGdegLGayecLGUa+1+∑a∈VLGyecLGUa+1=yξcG,y+yξcLG,y+yτLG,y.(20)εQGU,y=∑a∈UyecQGUa=∑a∈VGyecGa+1=yτG,y.
Combining these results with (5), we get the required result. This accomplishes the proof.Lemma 5.
(see [12]). Let G be a connected graph. If U=VG, then(a)
VTG=VG+EG and ETG=3EG+ELG.(b)
degTGUa=2degGaifa∈U,degLGa+1ifa∈VTG\U.(c)
ecTGUa=ecGaifa∈U,ecLGa+1ifa∈VTG\U.Theorem 6.
LetGn≥2 and G′ be graphs. Then,(21)ξcG+TG′,y=y2ξcG,y+ξcLG,y+τLG,yτG′,y+τG,yξcG′,y.Proof.
With the help of (3) and Lemma 5, we have(22)ξcTGU,y=∑a∈VTGdegTGayecTGUa=∑a∈UdegTGayecTGUa+∑a∈VTG\UdegTGayecTGUa=2∑a∈UdegGayecGa+1+∑a∈VTG\UdegLGa+1yecLGUa+1=2y∑a∈UdegGayecGa+∑a∈VLG\UdegLGayecLGUa+1+∑a∈VLG\UyecLGUa+1=2yξcG,y+yξcLG,y+yτLG,y.(23)εTGU,y=∑a∈UyecTGUa=∑a∈VGyecGa=τG,y.
Combining these results with (5), we get the needed result. This finishes the proof.Example 3.
Fork≥3, let G be a zig-zag polyhex nanotube TUHC62k,2 as shown in Figure 3. By definition, it is obvious that G≅Ck+SP2, where U=VCk⊆VSCk. By Theorem 3, we get(24)ξcCk+SP2,y=2kyk+12y+3,ifkis even,2kyk2y+3,ifkis odd.Figure 3
The zig-zag polyhex nanotubeTUHC62k,2.Example 4.
LetLk be the hexagonal chain [30] with k≥2 hexagonals (see Figure 4). From definition, it is obvious that Lk≅Pk+1+SP2, with U=VPk+1⊆VSPk+1. Then, by applying Theorem 3, we get(25)ξcPk+1+SP2,y=2yk+14yk+4y+3+4∑i=1k−2/2y2k−2i+12y+3,ifkis even,4yk+12yk+1+4∑i=1k−2/2y2k−2i+12y+3,ifkis odd.Figure 4
The linear hexagonal chainLk.


## 4. Cluster and Corona Product

The cluster product ofG and G′, symbolized by G′G, is achieved by using VG copies of a rooted graph G and a copy of G′ and by specifying the root of the l-th copy of G with the l-th vertex of G′, l=1,2,…,VG. The order and size of G′G are VGVG′ and EG+VGEG′, respectively. If we take a as the root vertex of G′ and U=a⊂VG, then G′G≅GU⊓G′≅Ga⊓G′. Now with the above notions in hand and by applying Theorem 1, we get the following result.Theorem 7.
LetG and G′ be graphs such that U⊆G. Then,(26)ξcG′G,y=τG′,y∑b∈VGdegGbyecGa+dGb,a+ξcG′,yyecGa.Proof.
SinceU=a, εGU,y=yecGa and ξcGU,y=∑b∈VGdegGbyecGa+dGb,a. So, using Theorem 1, we get the desired result.
LetSl+1 be a star graph having l+1 vertices, with the root vertex of degree l. For a given graph G′, the graph G′l can be constructed by taking cluster product of Sl+1 with G′. This is famous as l-fold bristled graph BrstG′. With the help of Theorem 1, the ECP of l-fold bristled graph BrstG′ can be evaluated.Corollary 1.
LetG be a graph. Then,(27)ξcG′t,y=ty1+yτG′,y+yξcG′,y.Proof.
LetG≅St+1, with the central vertex of degree t in St+1 as the root vertex. Then, ecGa=1 and dGa,b=1 for all b∈VG\a. The desired expression is obtained with the help of above theorem.
The corona productG□G′ of graphs G and G′ is a graph, which can be drawn by using VG copies of G′ and a copy of G and linking the l-th vertex of G to every vertex in l-th copy of G′, 1≤l≤n. In Theorem 8, we compute the ECP of G′□G.Theorem 8.
LetG and G′ be graphs. Then,(28)ξcG′□G,y=VGy+y22EG+VGτG′,y+yξcG′,y.Proof.
Leta∈VP1 be the root vertex of G+a, having order VG+1 and size EG+VG. Also note that ecG+aa=1, degG+aa=VG, dG+aa,b=1, degG+ab=degGb+1 for all b∈VG+a\a and G′□G≅G′G+a. By using Theorem 7, we have(29)ξcG′□G,y=degG+aay+∑b∈VGdegGb+1y2τG′,y+yξcG′,y=VGy+y22EG+VGτG′,y+yξcG′,y.Example 5.
For the bottleneck graphP2□G, ξcP2○G,y=2EG+VGy3+VG+2y2.Example 6.
If we use the verticesal, 1≤l≤k, in the construction of a bridge graph, then it is obtained by connecting the vertices al and al+1 of Gl+1 by a link for all l=1,2,…,k−1 and is represented by BG1,G2,…,Gn;a1,a2,…,ak. For G1≅G2≅⋯≅Gk and a1=a2=⋯=ak=a, we can define GkG,a=BG,G,…,G;a,a,…,a. In particular, let Bk=GkP3,a with degP3a=2 and Tk,s=GkCs,a be a type of bridge graphs. Then, we have Bk=Pk□P¯2, Tk,3=Pk□P2, and Jm,k+1=Pm□Ck. The graphs Bk, Tk,3, and Jm,7 are depicted in Figure 5. By using Theorem 8, we gain the following results:(30)ξcBk,y=2yky+2+2y+3∑i=2k/2yk−i+1,ifkis even,2yk+1/2y+21+yk−1/2+2y+3∑i=2k−1/2yk−i+1,ifkis odd,ξcTk,3,y=yk3y+4+3y+2∑i=2k/2yk−i+1,ifkis even,yk+1/23y+41+yk−1/2+3y+2∑i=2k−1/2yk−i+1,ifkis odd,ξcJm,k+1,y=3kym+1+k+2ym+3ky+k+4∑i=2m/2ym−i+1,ifkis even,ym+1/23ky+k+2ym−1/2+1+3ky+k+4∑i=2m−1/2ym−i+1,ifkis odd.Figure 5
The graphsBk, Tk,3, and Jm,7.


## 5. Conclusions

The numerical description of chemical structures with graph invariants is a valuable graph theory application. This characterization may be in the form of spectra, polynomials, molecular, or atomic topological indices. It is also feasible to specify graphs by matrices. A well-known example of such matrices is an adjacency matrix. However, the characterization of graphs by polynomials is a new line of research in modern graph theory. This paper is an effort in this direction, through which the ECP for some product graphs is illustrated by graph structure analysis and a mathematical derivation method.



---

*Source: 5061682-2020-05-31.xml*