# Terminal Hosoya Polynomial of Line Graphs

Authors: H. S. Ramane; A. B. Ganagi; K. P. Narayankar; S. S. Shirkol
Journal: Journal of Discrete Mathematics
 (2013)

---

## Abstract

The terminal Hosoya polynomial of a graphG is defined as TH(G,λ)=∑k≥1‍dT(G,k)λk, where dT(G,k) is the number of pairs of pendant vertices of G that are at distance k. In this paper we obtain terminal Hosoya polynomial of line graphs.


---

## Body

## 1. Introduction

LetG be a connected graph with vertex set V(G)={v1,v2,…,vn} and edge set E(G)={e1,e2,…,em}. The degree of a vertex v in G is the number of edges incident to it and is denoted by degG(v). If degG(v)=1, then v is called a pendant vertex or terminal vertex. An edge e=uv of a graph G is called a pendant edge if degG(u)=1 or degG(v)=1. Two edges are said to be independent if they are not adjacent to each other. The distance between the vertices vi and vj in G is equal to the length of a shortest path joining them and is denoted by d(vi,vj∣G).The Hosoya polynomial of a graph is a distance based polynomial introduced by Hosoya [1] in 1988 under the name “Wiener polynomial.” However today it is called the Hosoya polynomial [2–6]. For a connected graph G, the Hosoya polynomial denoted by H(G,λ) is defined as
(1)H(G,λ)=∑k≥1‍d(G,k)λk=∑1≤i<j≤n‍λd(vi,vj∣G),
where d(G,k) is the number of pairs of vertices of G that are at distance k and λ is the parameter.Estrada et al. [7] studied the chemical applications of Hosoya polynomial. The interesting property of H(G,λ) is that its first derivative at λ=1 is equal to the well-known Wiener index W(G) of G, the sum of the distances between all pairs of vertices of G [8]. That is,
(2)W(G)=∑1≤i<j≤n‍d(vi,vj∣G)=ddλ(H(G,λ))|λ=1.Gutman et al. [9] put forward another topological index called terminal Wiener indexTW(G) defined as the sum of the distances between all pairs of pendant vertices of  G. Thus if VT(G)={v1,v2,…,vk} is the set of pendant vertices of G, then
(3)TW(G)=∑{u,v}⊆VT(G)‍d(u,v∣G)=∑1≤i<j≤k‍d(vi,vj∣G).For recent work on the terminal Wiener index, see [10–14].In analogy of (1), the terminal Hosoya polynomialTH(G,λ) of a graph G was put forward by Narayankar et al. [15] and is defined as follows: if v1, v2, …, vk are the pendant vertices of G, then
(4)TH(G,λ)=∑k≥1‍dT(G,k)λk=∑1≤i<j≤k‍λd(vi,vj∣G),
where dT(G,k) is the number of pairs of pendant vertices of the graph G that are at distance k.It is easy to check that(5)TW(G)=ddλ(TH(G,λ))|λ=1.In [15], the terminal Hosoya polynomial of thorn graphs is obtained. In the present paper we obtain the terminal Hosoya polynomial of line graphs.If the graphG has no pendant vertex or has only one pendant vertex, then we write TH(G,λ)=0, for n≠2.If we writeTH(G,λ)=a1λ+a2λ2+⋯+adiam(G)λdiam(G), where diam(G) is the diameter of G, then a1=0 for all graphs of order n≥3 and a1=1 for G=K2, a complete graph on two vertices.


## 2. Terminal Hosoya Polynomial of  Line Graphs

Theline graph of G, denoted by L(G), is the graph whose vertices are the edges of G, and two vertices of L(G) are adjacent if and only if the corresponding edges are adjacent in G.Theorem 1.
LetG be a connected graph with n≥4 vertices, let D2(G)={v1,v2,…,vq}, where degG(vi)=2, and one neighbor of vi is pendant, i=1,2,…,q. Then
(6)TH(L(G),λ)=λ∑1≤i<j≤q‍λd(vi,vj∣G).Proof.
LetEk={e1,e2,…,ek} be the set of pendant edges of G and Eq={e1,e2,…,eq} the subset of Ek, where, for each ei∈Eq, the edge ei is incident to the vertex vi∈D2(G), i=1,2,…,q. Thus, if ei=uv∈Eq, then degG(u)=1 and degG(v)=2 (or vice versa), i=1,2,…,q.
Consider two edgesei=uvi and ej=vjw of Eq, where degG(u)=degG(w)=1 and degG(vi)=degG(vj)=2, i,j=1,2,…,q.
ThereforedegL(G)(ei)=degG(u)+degG(vi)-2=1. Similarly degL(G)(ej)=1. Therefore ei and ej are pendant vertices of L(G). Thus all edges of Eq are the pendant vertices of L(G), and d(ei,ej∣L(G))=1+d(vi,vj∣G), i≠j and i,j=1,2,…,q. Therefore
(7)TH(L(G),λ)=∑1≤i<j≤q‍λd(ei,ej∣L(G))=∑1≤i<j≤q‍λ1+d(vi,vj∣G)=λ∑1≤i<j≤q‍λd(vi,vj∣G).Theorem 2.
LetG be a connected graph with n≥4 vertices and G′ the graph obtained by removing pendant vertices of G. If (i) G=K1,n-1 or (ii) G has no edge e such that one of the components of G-e is K1,s, s≥2 and G≠K1,n-1, then
(8)TH(L(G),λ)=λTH(G′,λ).Proof.
Case
1. It is obvious that (8) holds for G=K1,n-1.
Case
2. Let D2(G)={v1,v2,…,vq}, where degG(vi)=2, and one neighbor of vi is pendant, i=1,2,…,q. If G≠K1,n-1 and if there is no edge e in G such that one of the component of G-e is K1,s, s≥2, then the vertices of the set D2(G) become pendant in G′. Therefore
(9)d(vi,vj∣G)=d(vi,vj∣G′),wherevi,vj∈D2(G).
Substituting this in (6) we get
(10)TH(L(G),λ)=λ∑1≤i<j≤q‍λd(vi,vj∣G′)=λTH(G′,λ).Corollary 3.
LetG be a connected graph with n≥4 vertices and G′ the graph obtained by removing pendant vertices of G. If all pendant edges of G are mutually independent, then
(11)TH(L(G),λ)=λTH(G′,λ).Proof.
It follows from Theorem2(ii).LetG be the graph with vertices v1, v2, …, vn then G+ is the graph obtained from G by adding n new vertices v1′, v2′, …, vn′ and joining vi′ to vi by an edge, i=1,2,…,n. The graph G+ is called the corona of G [16].Theorem 4.
LetG be a connected graph, then
(12)TH(L(G+),λ)=λTH(G,λ).Proof.
If the graphG has n number of vertices, then G+ has n pendant edges, and all are mutually independent. Removing pendant vertices of G+ we get the graph G. Therefore from Corollary 3,
(13)TH(L(G+),λ)=λTH(G,λ).Theorem 5.
LetG be a connected graph and Ft=L(Ft-1+), t=1,2,…, where F0=G and F1=L(G+); then
(14)TH(Ft,λ)=λtTH(G,λ).Proof.
We prove this by induction ont.
From Theorem4,
(15)TH(F1,λ)=TH(L(G+),λ)=λTH(G,λ).
Let
(16)TH(Ft-1,λ)=λt-1TH(G,λ).
Therefore
(17)TH(Ft,λ)=TH(L(Ft-1+),λ)=λTH(Ft-1,λ)=λλt-1TH(G,λ)=λtTH(G,λ).Thesubdivision graphS(G) is obtained from G by inserting a new vertex of degree 2 on each edge of G. The graph Sl(G) is obtained from G by inserting l new vertices of degree 2 on each edge of G. Thus S1(G)=S(G).Theorem 6.
LetG be a connected graph with k pendant vertices v1, v2, …, vk. Then for l≥1,
(18)TH(L(Sl(G)),λ)=1λ∑1≤i<j≤k‍λ(l+1)d(vi,vj∣G).Proof.
The pendant vertices ofG and pendant vertices of Sl(G) are the same. Further all pendant edges of Sl(G) are mutually independent.
Letu and v be the pendant vertices of G; then u and v are pendant vertices of Sl(G). Let u′ and v′ be the subdivision vertices of Sl(G), where u′ is adjacent to u and v′ is adjacent to v in Sl(G). Let (Sl(G))′ be the graph obtained by removing all pendant vertices of Sl(G). Therefore u′ and v′ are pendant vertices of (Sl(G))′ and d(u′,v′∣(Sl(G))′)=(l+1)d(u,v∣G)-2. Now, since the pendant edges of Sl(G) are mutually independent, from Corollary 3,
(19)TH(L(Sl(G)),λ)=λTH((Sl(G))′,λ)=λ∑{u′,v′}⊆VT((Sl(G))′)‍λd(u′,v′∣(Sl(G))′)=λ∑{u,v}⊆VT(G)‍λ(l+1)d(u,v∣G)-2=1λ∑{u,v}⊆VT(G)‍λ(l+1)d(u,v∣G)=1λ∑1≤i<j≤k‍λ(l+1)d(vi,vj∣G).Corollary 7.
LetG be a connected graph with k pendant vertices v1, v2, …, vk. If d(vi,vj∣G)=d for all i,j=1,2,…,k, where i≠j, then, for l≥1,
(20)TH(L(Sl(G)),λ)=k(k-1)2λ(l+1)d-1.Proof.
It follows from Theorem6.



---

*Source: 857908-2013-06-13.xml*