# The Terminal Hosoya Polynomial of Some Families of Composite Graphs

Authors: Emeric Deutsch; Juan Alberto Rodríguez-Velázquez
Journal: International Journal of Combinatorics
 (2014)

---

## Abstract

LetG be a connected graph and let Ω(G) be the set of pendent vertices of G. The terminal Hosoya polynomial of G is defined as TH
(
G
,
t
)
∶
=
∑
x
,
y
∈
Ω
(
G
)
:
x
≠
y
t
d
G
(
x
,
y
), where d
G
(
x
,
y
) denotes the distance between the pendent vertices x and y. In this note paper we obtain closed formulae for the terminal Hosoya polynomial of rooted product graphs and corona product graphs.


---

## Body

## 1. Introduction

Throughout this paperG
=
(
V
,
E
) denotes a connected, simple, and finite graph with vertex set V
=
V
(
G
) and edge set E
=
E
(
G
). Thedistance
d
G
(
u
,
v
) between two vertices u and v is the minimum of the lengths of paths between u and v.TheWiener index
W
(
G
) of a graph G with vertex set {
v
1
,
v
2
,
…
,
v
n
}, defined as the sum of distances between all pairs of vertices of G,
(1)
W
(
G
)
∶
=
1
2
∑
i
=
1
,
j
=
1
n
‍
d
G
(
v
i
,
v
j
)
,
is the first mathematical invariant reflecting the topological structure of a molecular graph.This topological index has been extensively studied; for instance, a comprehensive survey on the direct calculation, applications, and the relation of the Wiener index of trees with other parameters of graphs can be found in [1]. Moreover, a list of 120 references of the main works on the Wiener index of graphs can be found in the referred survey.The Hosoya polynomial of a graph was introduced in Hosoya's seminal paper [2] in 1988 and received a lot of attention afterwards. The polynomial was later independently introduced and considered by Sagan et al. [3] under the name Wiener polynomial of a graph. Both names are still used for the polynomial but the term Hosoya polynomial is nowadays used by the majority of researchers. The main advantage of the Hosoya polynomial is that it contains a wealth of information about distance based graph invariants. For instance, knowing the Hosoya polynomial of a graph, it is straightforward to determine the Wiener index of a graph as the first derivative of the polynomial at the point t
=
1. Cash [4] noticed that the hyper-Wiener index can be obtained from the Hosoya polynomial in a similar simple manner. A comprehensive survey on the main properties of the Hosoya polynomial, which includes a wide list of bibliographic references, can be found in Gutman et al. [5]. Also, Estrada et al. [6] studied several chemical applications of the Hosoya polynomial.TheHosoya polynomial of a connected graph G is defined as
(2)
H
(
G
,
t
)
∶
=
∑
x
,
y
∈
V
(
G
)
:
x
≠
y
‍
t
d
G
(
x
,
y
)
.
As we pointed out above, the Wiener index of a graph G is determined as the first derivative of the polynomial H
(
G
,
t
) at t
=
1.The Hosoya polynomial has been obtained for trees, composite graphs, benzenoid graphs, tori, zig-zag open-ended nanotubes, certain graph decorations, armchair open-ended nanotubes, zigzag polyhex nanotorus,TU
C
4
C
8
(
S
) nanotubes, pentachains, polyphenyl chains, the circumcoronene series, Fibonacci and Lucas cubes, Hanoi graphs, and so forth. See the references in [7].Thedegree of a vertex v in G is the number of edges incident to it and is denoted by de
g
G
(
v
). If de
g
G
(
v
)
=
1, then v is called apendent vertex of G. The set of pendent vertices of G will be denoted by Ω
(
G
).Gutman et al. proposed the concept ofterminal Wiener index, which is defined as the sum of distances between all pairs of pendent vertices of G [8]. For detailed information on the terminal Wiener index the readers may refer to the recent papers [8–11] and the references cited therein.By analogy to the definition of Hosoya polynomial, theterminal Hosoya polynomial was defined by Narayankar et al. [12] as
(3)
TH
(
G
,
t
)
∶
=
∑
x
,
y
∈
Ω
(
G
)
:
x
≠
y
‍
t
d
G
(
x
,
y
)
,
and recently Ramane et al. studied TH
(
G
,
t
) for the case of line graphs [13]. As we can expect, the terminal Wiener index, denoted by TW
(
G
), is obtained from TH
(
G
,
t
) as
(4)
TW
(
G
)
=
∂
(
TH
(
G
,
t
)
)
∂
t
|
t
=
1
.Among the most known products of graphs, namely, Cartesian product, lexicographic product, strong product, rooted product, and corona product, the two latest ones are the only cases in which we can obtain connected graphs having pendent vertices. So, in this paper we obtain formulae for the terminal Hosoya polynomial of both types of graphs, rooted product graphs and corona product graphs.The remaining definitions will be given the first time that the concept is found in the text.


## 2. The Terminal Hosoya Polynomial of Rooted Product Graphs

Arooted graph is a graph in which one vertex is labeled in a special way so as to distinguish it from the other vertices. The special vertex is called theroot of the graph. Let G be a labeled graph on n vertices. Let ℱ be a sequence of n rooted graphs G
1
′
,
G
2
′
,
…
,
G
n
′. Therooted product graph
G
(
ℱ
) is the graph obtained by identifying the root of G
i
′ with the ith vertex of G [14]. In this paper we consider a particular case of rooted product graphs where ℱ consists of n isomorphic rooted graphs [15]. More formally, assuming that V
(
G
)
=
{
u
1
,
…
,
u
n
} and that the root vertex of G
′ is v, we define therooted product graph
G
∘
v
G
′ as the graph whose vertex set is V
(
G
∘
v
G
′
)
=
V
(
G
)
×
V
(
G
′
) and whose edge set is
(5)
E
(
G
∘
v
G
′
)
=
⋃
i
=
1
n
{
(
u
i
,
b
)
(
u
i
,
y
)
:
by
∈
E
(
G
′
)
}
∪
{
(
u
i
,
v
)
(
u
j
,
v
)
:
u
i
u
j
∈
E
(
G
)
}
.As an example of a chemical compound whose graph is obtained as a rooted product graph we consider the Cycloalkanes with a single ring, whose chemical formula isC
n
H
2
n, and whose molecular graph can be expressed as C
n
∘
v
P
3, where C
n is the cycle graph of order n, P
3 is a path of order 3, and v is the central vertex of P
3 (see Figure 1).Figure 1
The graphC
6
∘
v
P
3, where C
6 is the cycle graph of order 6, P
3 is a path of order 3, and v is the central vertex of P
3. This chemical graph that corresponds to the Cyclohexane (C6H12) is a naturally occurring chemical that is also produced synthetically and used as a solvent in numerous industries.To begin with, we need some additional notation. We define theterminal Hosoya polynomial with respect to
u as
(6)
T
H
u
(
G
,
t
)
∶
=
∑
w
∈
Ω
(
G
)
-
{
u
}
‍
t
d
G
(
u
,
w
)
.Theorem 1.
LetG be a connected graph of order n
≥
2 and let G
′ be a connected nontrivial graph. Then for any v
∈
V
(
G
′
)
-
Ω
(
G
′
),
(7)
T
H
(
G
∘
v
G
′
,
t
)
=
n
·
T
H
(
G
′
,
t
)
+
H
(
G
,
t
)
(
T
H
v
(
G
′
,
t
)
)
2
.Proof.
LetV
(
G
)
=
{
u
1
,
u
2
,
…
,
u
n
} and let G
i
′ be the ith-“copy” of G
′ in G
∘
v
G
′; that is, G
i
′ is the subgraph of G
∘
v
G
′ generated by the set {
u
i
}
×
V
(
G
′
), which is isomorphic to G
′. Then,
(8)
Ω
(
G
∘
v
G
′
)
=
⋃
i
=
1
n
‍
Ω
(
G
i
′
)
.
So, if Ω
(
G
′
)
=
∅, then Ω
(
G
∘
v
G
′
)
=
∅ and, as a consequence, T
H
v
(
G
′
,
t
)
=
TH
(
G
′
,
t
)
=
TH
(
G
∘
v
G
′
,
t
)
=
0. So, we assume that Ω
(
G
′
)
≠
∅.
Notice that for every pairx
,
y of pendent vertices of G
′ and u
i
∈
V
(
G
) we have
(9)
d
G
∘
v
G
′
(
(
u
i
,
x
)
,
(
u
i
,
y
)
)
=
d
G
i
′
(
(
u
i
,
x
)
,
(
u
i
,
y
)
)
=
d
G
′
(
x
,
y
)
.
Also, for u
i
,
u
j
∈
V
(
G
), i
≠
j, we have
(10)
d
G
∘
v
G
′
(
(
u
i
,
x
)
,
(
u
j
,
y
)
)
=
d
G
′
(
x
,
v
)
+
d
G
(
u
i
,
u
j
)
+
d
G
′
(
v
,
y
)
.
Hence, TH
(
G
∘
v
G
′
,
t
) splits as the sum of two polynomials P
(
t
)
+
Q
(
t
), where P
(
t
) is obtained from pairs of pendent vertices in the same G
i and Q
(
t
) is obtained from pairs (
u
i
,
x
)
,
(
u
j
,
y
), where i
≠
j. On the one hand,
(11)
P
(
t
)
=
∑
i
=
1
n
‍
(
∑
x
,
y
∈
Ω
(
G
′
)
:
x
≠
y
‍
t
d
G
′
(
x
,
y
)
)
=
n
·
TH
(
G
′
,
t
)
,
and, on the other hand,
(12)
Q
(
t
)
=
∑
u
i
,
u
j
∈
V
(
G
)
:
i
≠
j
‍
t
d
G
(
u
i
,
u
j
)
(
∑
x
∈
Ω
(
G
′
)
‍
t
d
G
′
(
x
,
v
)
)
=
∑
u
i
,
u
j
∈
V
(
G
)
:
i
≠
j
‍
×
(
∑
y
∈
Ω
(
G
′
)
‍
t
d
G
′
(
y
,
v
)
)
=
(
T
H
v
(
G
′
,
t
)
)
2
∑
u
i
,
u
j
∈
V
(
G
)
:
i
≠
j
‍
t
d
G
(
u
i
,
u
j
)
=
(
T
H
v
(
G
′
,
t
)
)
2
H
(
G
,
t
)
.
Therefore, the result follows.Given a vertexv
∈
V
(
G
′
), we define
(13)
d
T
(
v
)
∶
=
∑
w
∈
Ω
(
G
′
)
-
{
v
}
‍
d
G
′
(
v
,
w
)
.
Notice that we can see d
T
(
v
) as theterminal Wiener index with respect to
v; that is, d
T
(
v
) is the first derivative of the polynomial T
H
v
(
G
′
,
t
) at t
=
1. As a direct consequence of Theorem 1 we obtain the following result on the terminal Wiener index.Corollary 2.
LetG
′ be a connected nontrivial graph. Then for any v
∈
V
(
G
′
)
-
Ω
(
G
′
) and any connected graph G of order n
≥
2,
(14)
T
W

(
G
∘
v
G
′
,
t
)
=
n
·
T
W

(
G
′
)
+
W
(
G
)
|
Ω
(
G
′
)
|
2
+
n
(
n
-
1
)
|
Ω
(
G
′
)
|
d
T
(
v
)
.Now we consider the case of rooted product graphsG
∘
v
G
′ where the root v is a pendent vertex of G
′.Theorem 3.
LetG be a connected graph of order n
≥
2 and let G
′ be a connected nontrivial graph. Then for any v
∈
Ω
(
G
′
),
(15)
T
H

(
G
∘
v
G
′
,
t
)
=
n
(

T
H

(
G
′
,
t
)
-
T
H

v
(
G
′
,
t
)
)
+
H
(
G
,
t
)
(

T
H

v
(
G
′
,
t
)
)
2
.Proof.
We proceed as in the proof of Theorem1, with the only difference that in this case P
(
t
) is obtained as follows:
(16)
P
(
t
)
=
∑
i
=
1
n
‍
(
∑
x
,
y
∈
Ω
(
G
′
)
-
{
v
}
:
x
≠
y
‍
t
d
G
′
(
x
,
y
)
)
=
n
(
∑
x
,
y
∈
Ω
(
G
′
)
:
x
≠
y
‍
t
d
G
′
(
x
,
y
)
-
∑
x
∈
Ω
(
G
′
)
-
{
v
}
‍
t
d
G
′
(
x
,
v
)
)
=
n
(
TH
(
G
′
,
t
)
-
T
H
v
(
G
′
,
t
)
)
.Corollary 4.
LetG
′ be a connected nontrivial graph. Then for any v
∈
Ω
(
G
′
) and any connected graph G of order n
≥
2, one has
(17)
T
W

(
G
∘
v
G
′
,
t
)
=
n
(

T
W

(
G
′
)
-
d
T
(
v
)
)
+
W
(
G
)
(
|
Ω
(
G
′
)
|
-
1
)
2
+
n
(
n
-
1
)
(
|
Ω
(
G
′
)
|
-
1
)
d
T
(
v
)
.


## 3. The Terminal Hosoya Polynomial of Corona Graphs

LetG and G
′ be two graphs of order n and n
′, respectively. The corona product G
⊙
G
′ is defined as the graph obtained from G and G
′ by taking one copy of G and n copies of G
′ and joining by an edge each vertex from the ith-copy of  G
′ with the ith-vertex of G [16]. We will denote by V
=
{
v
1
,
v
2
,
…
,
v
n
} the set of vertices of G and by G
i
′
=
(
V
i
,
E
i
) the copy of G
′ such that v
i is adjacent to v for every v
∈
V
i. Thus, the vertex set of G
⊙
G
′ is V
∪
(
∪
i
=
1
n
′
V
i
) and, consequently, G
⊙
G
′ has order n
(
n
′
+
1
) and, if G is connected, then G
⊙
G
′ is also connected and it has diameter D
(
G
⊙
G
′
)
=
D
(
G
)
+
2.Notice that the corona graphK
1
⊙
G
′ is isomorphic to the join graph K
1
+
G
′. Now, if G is a tree and G
′
=
N
r is an empty graph (An empty graph on r nodes consists of r isolated nodes with no edges. Such graphs are sometimes also called edgeless graphs or null graphs), then the corona graph G
⊙
N
r is a tree and the set of leaves (pendent vertices) of G
⊙
N
r is ∪
i
=
1
n
V
i. In particular, if G
=
P is a path, then P
⊙
N
r is a caterpillar graph and the path P, that is formed by the nonleaves of P
⊙
N
r, is known as the backbone of the caterpillar.The formula for the Hosoya polynomial of corona graphs was previously obtained in [17]. In this section we obtain the formula for the terminal Hosoya polynomial of corona graphs G
⊙
G
′. Of course, G
⊙
G
′ has pendent vertices if and only if G
′ has isolated vertices.Corollary 5.
For any connected graphG of order n
≥
2 and any graph G
′ having r isolated vertices,
(18)
T
H
(
G
⊙
G
′
,
t
)
=
n
(
r
2
)
t
2
+
r
2
t
2
H
(
G
,
t
)
.Proof.
First of all, notice thatG
⊙
G
′
=
G
∘
v
(
〈
v
〉
+
G
′
), where 〈
v
〉 is the trivial graph composed by the vertex v. Now, since TH
(
〈
v
〉
+
G
′
,
t
)
=
(
r
2
)
t
2 and T
H
v
(
〈
v
〉
+
G
′
,
t
)
=
r
t, the result immediately follows from Theorem 1.Finally, Corollary5 (and also Corollary 2) leads to the following formula for the terminal Wiener index of G
⊙
G
′.Remark 6.
For any connected graphG of order n
≥
2 and any graph G
′ having r isolated vertices,
(19)
TW
(
G
⊙
G
′
)
=
n
r
(
n
r
-
1
)
+
r
2
W
(
G
)
.



---

*Source: 696507-2014-04-16.xml*