Ratio Mathematica Volume 42, 2022

Common Neighbor Polynomial of Some
Special Trees

Shikhi Mandattil*
Anil Kumar Vasu†

Abstract

Let G(V, E) be a simple graph of order n with vertex set V and edge
set E. Let (u, v) denotes an unordered vertex pair of distinct vertices
of G and let N(u) denote the open neighborhood of the vertex u in G.
The i-common neighbor set of G is defined as N(G, i) := {(u, v) :
u, v ∈ V, u ̸= v and |N(u) ∩ N(v)| = i}, for 0 ≤ i ≤ n − 2. The
polynomial N[G; x] =

∑(n−2)
i=0 |N(G, i)|x

i is defined as the common
neighbor polynomial of G. In this paper, we study the common neigh-
bor polynomial of some special type of trees such as complete m-ary
tree, caterpillar tree, star like tree and fire cracker graph.
Keywords: common neighbor, common neighbor polynomial.
2020 AMS subject classifications: 05C31, 05C39.1

*Shikhi Mandattil, Department of Mathematics, Govt. Arts and Science College, Kozhikode,
Kerala, India; shikhianil@gmail.com.

†Anil Kumar Vasu, Department of Mathematics, University of Calicut, Malappuram, Kerala,
India; anil@uoc.ac.in.
1Received on April 9th, 2022. Accepted on June 29th, 2022. Published on June 30th, 2022. doi:
10.23755/rm.v41i0.755. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper is
published under the CC-BY licence agreement.

195



Shikhi M, Anil Kumar V.

1 Introduction
Vertex similarity of nodes is a well studied concept in graph theory as it is

highly significant in various fields such as in the study of molecular structure of
chemical graphs, measuring consensus rate of different individuals/organizations
in network analysis etc. The number of common neighbors shared by two nodes
in a network system can be treated as a measure of consensus among the corre-
sponding individuals. This motivates the authors to define the i-common neighbor
set and the common neighbor polynomial of a graph.

Let G(V, E) be a graph (simple graph) of order n with vertex set V and edge
set E. Let (u, v) denotes an unordered vertex pair of distinct vertices of G and let
N(u) denote the open neighborhood of the vertex u in G. The i-common neighbor
set of G is defined as N(G, i) := {(u, v) : u, v ∈ V, u ̸= v and |N(u) ∩ N(v)| =
i}, for 0 ≤ i ≤ n − 2. The polynomial N[G; x] =

∑(n−2)
i=0 |N(G, i)|x

i is defined
as the common neighbor polynomial of G. This polynomial was introduced by
the present authors in (3).

Trees are commonly used to represent hierarchical data structures involved
in network file system, possibility spaces, algorithmic routing etc. It is easy to
dissect a tree data structure to access the information about a particular part of
a huge data. Due to this reason, many researches were conducted to explore the
properties of trees. In this paper, we derive the common neighbor polynomial of
some special trees like rooted trees, caterpillars etc.

2 Main Results
A rooted tree is a tree in which one of the vertices is distinguished as the

root. According to the distance of other vertices from the root vertex, there is a
hierarchy on the vertices of a rooted tree. The distance of a vertex v from the
root is called the depth or level of the vertex. The height of a rooted tree is the
greatest depth of a vertex of the tree. Considering a path from the root to a vertex
w, if a vertex v immediately precedes w , then v is called the parent of w and w
is called the child of v. Vertices having same parent are called siblings. An m-ary
tree (m ≥ 2) is a rooted tree in which every vertex has m or fewer number of
children. A complete m-ary tree is an m-ary tree in which every internal vertices
has exactly m children and all leaves are of same distance from the root.

Theorem 1. Let T be a tree on n vertices. Let v be a vertex of T with degree k. If
T ′ is a tree obtained from T by attaching p pendent edges at the vertex v, we have
the following:

N[T ′; x] = N[T ; x] +
p

2
(2k + p − 1)x + p(n − k).

196



Common neighbor polynomial of some special trees

Proof. Let {v1, v2, . . . , vk} be the neighbors of v in T . When we attach a pendent
edge vw to v, n number of new pairs of vertices are introduced in which the pairs
(vi, w) where i ∈ {1, 2, . . . , k} have one common neighbor v and the remaining
n − k new pairs have no common neighbors. There will be no change in the
number of common neighbors of pairs of vertices of T by the introduction of the
pendent edge vw. Hence the common neighbor polynomial becomes N[T; x] +
kx+(n−k). Repeating the process p times, after attaching the p-th pendent edge
to v, the common neighbor polynomial of resulting graph becomes,

N[T ′; x] = N[T; x] + kx + (n − k) + (k + 1)x + (n − k) + . . .
+ (k + p − 1)x + (n − k)

= N[T; x] + [k + (k + 1) + (k + 2) + . . . + (k + p − 1)]x + p(n − k)

= N[T; x] +
p

2
(2k + p − 1)x + p(n − k).

This completes the proof.

Theorem 2. Let T be a complete m-ary tree with p levels where the root vertex is
considered to be in the 0-th level. Then we have the following:

N[T; x] =
m2(mp−1 − 1)

m − 1
x +

(
m

2

)
mp − 1
m − 1

x +
m[m2p−2 − mp + m − 1]

m − 1
+ m2p−1

+

p−3∑
i=0

[m2i+3 − mp+i+1
1 − m

]
+

m2[m2p − mp+1 − mp + m]
2(m2 − 1)

.

Level 1

Level 2

Level 3

Figure 1: Complete binary tree with 3 levels of vertices

Proof. Let (u, v) be any pair of vertices of T . Here we consider 4 different cases
according to the levels in which the vertices u and v lie in T .

Case(i) For i ∈ {0, 1, 2, . . . , p−2} let u be a vertex in the i-th level and v a vertex
in the (i + 1)th or (i + 2)th level.
If v is an (i+1)th level vertex, the vertex pair (u, v) have no common neigh-
bors and there are mimi+1 such pairs of vertices in T . If v is in the (i + 2)th

197



Shikhi M, Anil Kumar V.

level, then there are mimi+2 pairs of vertices (u, v) in which mi[mi+2 −m2]
pairs of vertices have no common neighbors and mim2 pairs have exactly
one common neighbor.

Case(ii) Let u be a vertex in the (p − 1)-th level and v a vertex in the p-th level.
In this case the pairs of vertices (u, v) have no common neighbors and there
are mp−1mp such pairs of vertices.

Case(iii) For i ∈ {0, 1, 2, . . . , p − 3} let u be a vertex in the i-th level and v a
vertex in the j-th level where j = i + 3, i + 4, . . . , p.
All the pairs of vertices under this case have no common neighbors and
there are mi[mi+3 + mi+4 + . . . + mp] such pairs of vertices.

Case(iv) For i ∈ {1, 2, . . . , p} let u and v be vertices of same level.
In this case 1

2
mi[mi−m] distinct pairs of vertices which are not siblings have

no common neighbors and
(
m
2

)
mi−1 pairs of vertices which are siblings

have exactly one common neighbor.

From the above cases, it follows that

N[T; x] =

p−2∑
i=0

mim2x +

(
m

2

) p∑
i=1

mi−1x +

p−2∑
i=0

mi[mi+1 + mi+2 − m2] + m2p−1

+

p−3∑
i=0

mi[mi+3 + mi+4 + . . . + mp] +

p∑
i=1

1

2
mi(mi − m).

=
m2(mp−1 − 1)

m − 1
x +

(
m

2

)
mp − 1
m − 1

x +
m[m2p−2 − mp + m − 1]

m − 1
+ m2p−1

+

p−3∑
i=0

[mp+i+1 − m2i+3
m − 1

]
+

m2[m2p − mp+1 − mp + m]
2(m2 − 1)

.

This completes the proof.

A derivative of a graph G is a graph obtained from G by deleting all the pen-
dent vertices of G. A caterpillar is a tree whose derivative is a path graph (5).
Consequently, a caterpillar Pn(m1, m2, . . . , mn) is obtained by attaching mi pen-
dent edges to the vertex vi of a path Pn where i ∈ {1, 2, . . . , n}.

Theorem 3. The common neighbor polynomial of a caterpillar tree
Pn(m1, m2, . . . , mn) is given by the following:

198



Common neighbor polynomial of some special trees

v
(1)
1 v

(1)
2

v1

v2

v3

v4

v
(2)
1

v
(2)
2 v

(2)
3

v
(3)
1

v
(4)
1 v

(4)
2 v

(4)
3

Figure 2: The caterpillar P4(2, 3, 1, 3)

N[Pn(m1, m2, . . . , mn); x] = N[Pn; x] +
n∑

j=1

N[K1,mj; x] +
∑

l,k∈{1,2,...,n}
l ̸=k

mlmk

+
[
m1 + mn + 2

n−1∑
j=2

mj

]
x + (n − 2)(m1 + mn) + (n − 3)

n−1∑
j=2

mj.

Proof. Let Pn(m1, m2, . . . , mn) be a caterpillar and let v1, v2, . . . , vn be the ver-
tices of its derived graph which is a path. Also let v(j)1 , v

(j)
2 , . . . , v

(j)
mj be the pendent

vertices of the caterpillar tree attached to the vertex vj where j ∈ {1, 2, . . . , n}.
Let (u, v) be any pair of vertices of the caterpillar. We consider the following
cases to build up its common neighbor polynomial.

Case(i) Let u, v ∈ {v1, v2, . . . , vn}. Here the number of pairs of vertices (u, v)
with i common neighbors equals |N(Pn, i)|. So the pairs of vertices under
this case contribute the term N[Pn; x] to the common neighbor polynomial
of the caterpillar.

Case(ii) Let u, v ∈ {vj, v
(j)
1 , v

(j)
2 , . . . , v

(j)
mj}. Here the vertices of the set under

consideration spans a star graph K1,mj and hence the number of pairs of
vertices (u, v) with i common neighbors equals |N(K1,mj, i)|.

Case(iii) Let u ∈ {v(l)1 , v
(l)
2 , . . . , v

(l)
ml} and v ∈ {v

(k)
1 , v

(k)
2 , . . . , v

(k)
mk} where l ̸= k

and l, k ∈ {1, 2, . . . , n}.
Here u and v are the pendent vertices attached to the vertices vl and vk
respectively where l ̸= k. No pair of vertices under this case have common
neighbors and there are

∑
l,k
l ̸=k

mlmk such pairs.

Case(iv) Let u ∈ {v1, vn}, a pendent vertex of the derived graph Pn and let v be
any vertex attached to the vertices of Pn such that uv is not an edge of the
caterpillar.

199



Shikhi M, Anil Kumar V.

In this case pairs of vertices of the form (v1, v
(2)
l ) and (vn, v

(n−1)
k ) where

l ∈ {1, 2, . . . , m2} and k ∈ {1, 2, . . . , mn−1} have exactly one common
neighbor each and there are m2+mn−1 such pairs of vertices. There remains
m1 +m2 +mn−1 +mn +2

∑n−2
j=3 mj pairs of vertices under this case which

have no common neighbors.

Case(v) Let u ∈ {v2, v3 . . . , vn−1} and let v be any vertex selected in a way same
as in Case(iv).
For i ∈ {2, 3, . . . , n − 1}, the pairs of vertices of the form (vi, v

(i−1)
l ) where

l ∈ {1, 2, . . . , mi−1} have exactly one common neighbor vi−1 and pairs of
vertices of the form (vi, v

(i+1)
k ) where k ∈ {1, 2, . . . , mi+1} have exactly

one common neighbor vi+1. There are m1 +m2 +mn−1 +mn +2
∑n−2

j=3 mj
such pairs of vertices.

The remaining pairs of vertices under this case have no common neighbors
and there are (n − 3)(m1 + mn) + (n − 4)(m2 + mn−1) + (n − 5)

∑n−2
j=3 mj

such pairs of vertices.

From the above cases, it follows that

N[Pn(m1, m2, . . . , mn); x] = N[Pn; x] +
n∑

j=1

N[K1,mj; x] +
∑
l,k
l ̸=k

mlmk

+ [m2 + mn−1]x + m1 + m2 + mn−1 + mn + 2
n−2∑
j=3

mj

+
[
m1 + m2 + mn−1 + mn + 2

n−2∑
j=3

mj

]
x + (n − 3)(m1 + mn)

+ (n − 4)(m2 + mn−1) + (n − 5)
n−2∑
j=3

mj.

Now the result follows after some rearrangement of the terms.

Corollary 4. For a caterpillar Pn(m, m, . . . , m) where m pendent edges are at-
tached to each vertex of the path Pn, we have

N[Pn(m, m, . . . , m); x] = N[Pn; x] + nN[K1,m; x] +

(
n

2

)
m2 + 2m(n − 1)x

+ m(n − 1)(n − 2).

A star like tree(2) S(n1, n2, . . . , nk) is a graph having only one vertex w of
degree greater than 2 such that deletion of w results in a disjoint union of the path

200



Common neighbor polynomial of some special trees

graphs Pn1, Pn2, . . . , Pnk . The star like tree graphs are used to represent proteins
which will have generally 20 branches where each branch indicates the presence
of one of the 20 natural amino acids. For example, the strand A of human insulin
has 21 amino acids of 11 kinds which can be modelled by a star like tree graph
with 11 branches as shown in Figure 3.

Figure 3: Strand A of human insulin

Theorem 5. The common neighbor polynomial of a star like tree S(n1, n2, . . . , nk)
with N + 1 vertices is given by

N[S(n1, n2, . . . , nk); x] =
k∑

r=1

N[Pnr+1; x] +

(
k

2

)
x +

(
N

2

)
−

k∑
r=1

(
nr
2

)
−
(
k

2

)
where N = n1 + n2 + . . . + nk.

Proof. Let S(n1, n2, . . . , nk) be a star like tree with a vertex w such that
S(n1, n2, . . . , nk)−w = Pn1 ∪Pn2 ∪. . .∪Pnk . Any pair of vertices (u, v) ∈ Pnr ∪
{w} where r ∈ {1, 2, . . . , k}, has as many common neighbors in S(n1, n2, . . . , nk)
as it has in Pnr+1.

Let (u, v) be a pair of vertices in S(n1, n2, . . . , nk) such that u ∈ Pnr and
v ∈ Pns where r ̸= s, r, s ∈ {1, 2, . . . , k}. Then the vertex pair (u, v) has a single
common neighbor w if both u and v are adjacent to w and there are no common
neighbors otherwise. Hence there are

(
k
2

)
pairs of vertices with one common

neighbor and
(
N
2

)
−
∑k

r=1

(
nr
2

)
−
(
k
2

)
pairs of vertices with no common neighbors.

Hence the result follows.

Corollary 6. The common neighbor polynomial of the graphical representation
of Strand A of human insulin is given by

N[G; x] = 65x + 166.

Proof. The proof follows from the fact that Strand A of human insulin can be
graphically represented as a star like tree graph S(1, 2, 4, 2, 2, 1, 2, 2, 1, 2, 2).

201



Shikhi M, Anil Kumar V.

The (n, k) firecracker graph(1) is obtained by identifying each vertex of a path
Pn with one of the pendent vertices of the star graph K1,k. In particular, the (n, 2)
firecracker graph is known as the centipede graph.

u2

v2

v
(2)
2 v

(2)
3v

(2)
1

Figure 4: The (4, 4)- firecracker graph

Lemma 7. (see (3)) For a complete bipartite graph Km,n, we have

N[Km,n; x] =

(
m

2

)
xn +

(
n

2

)
xm + mn.

Lemma 8. (see (3)) For a path Pn with n ≥ 2 vertices, we have

N[Pn; x] = (n − 2)x +
(
n − 1
2

)
+ 1.

Theorem 9. The common neighbor polynomial of (n, k) firecracker graph G is
given by the following:
N[G; x] =

[
n
(
k
2

)
+ 3n − 4

]
x + nk +

(
n−1
2

)
+ 1 +

(
n
2

)
k2 + (n − 1)(n − 2) + n(n −

1)(k − 1).

Proof. For j ∈ {1, 2, . . . , n}, let vj1, v
j
2, . . . , v

j
k be the pendent vertices of the j

th

star where the vertex vjk is identified with the vertex uj of the path Pn. Let vj be
the center vertex of the jth star attached to the vertex uj of Pn. Let (u, v) be any
pair of vertices of G. Here we consider 5 cases:

Case(i) Let u, v ∈ {vj, v
j
1, v

j
2, . . . , v

j
k} where j ∈ {1, 2, . . . , n}.

In this case, the pair (u, v) has as many common neighbors in G as in K1,k.

Case(ii) Let u, v ∈ {u1, u2, . . . , un}.
Here the vertex pair (u, v) has as many common neighbors in G as in Pn.

Case(iii) Let u = vj and v ∈ {u1, u2, . . . , uj−1, uj+1, . . . , un} where j ∈ {1, 2, . . . , n}
.
In this case, for each j, the pairs (vj, uj−1) and (vj, uj+1) has exactly one

202



Common neighbor polynomial of some special trees

common neighbor. Also the pairs (v1, u2) and (vn, un−1) have one common
neighbor each. Hence there are 2(n − 1) pairs of vertices (u, v) with one
common neighbor and all other (n − 1)(n − 2) pairs of vertices have no
common neighbors.

Case(iv) Let u ∈ {vr, vr1, vr2, . . . , vrk−1} and v ∈ {vs, v
s
1, v

s
2, . . . , v

s
k−1} where

r, s ∈ {1, 2, . . . , n}.
In this case, there are

(
n
2

)
k2 pairs of vertices which have no common neigh-

bors.

Case(v) Let u ∈ {vj1, v
j
2, . . . , v

j
k−1} and v ∈ {u1, u2, . . . , uj−1, uj+1, . . . , un}

where j ∈ {1, 2, . . . , n},
In this case, there are n(n − 1)(k − 1) pairs of vertices which have no com-
mon neighbors.

Using lemmas 7 and 8, it follows that,

N[G; x] = nN[K1,k; x] + N[Pn; x] + 2(n − 1)x + (n − 1)(n − 2) +
(
n

2

)
k2

+ n(n − 1)(k − 1)

= n
[(k

2

)
x + k

]
+ (n − 2)x +

(
n − 1
2

)
+ 1 + 2(n − 1)x +

(
n

2

)
k2

+ (n − 1)(n − 2) + n(n − 1)(k − 1)

=
[
n

(
k

2

)
+ 3n − 4

]
x + nk +

(
n − 1
2

)
+ 1 +

(
n

2

)
k2

+ (n − 1)(n − 2) + n(n − 1)(k − 1).

This completes the proof.

Corollary 10. The common neighbor polynomial of the centipede graph G is
given by

N[G; x] = 4(n − 1)x + 2n +
3(n − 1)(3n − 2)

2
+ 1.

Proof. The proof follows from the fact that the centipede graph is a special case
of (n, k)- firecracker graph when k = 2.

203



Shikhi M, Anil Kumar V.

References
[1] Eric W. Weisstein, Firecracker Graph, http://mathworld.wolfram.com /Fire-

crackerGraph.html

[2] M. Lepovic, I. Gutman, Some spectral properties of starlike trees, Bulletin
T.CXXII de l Academie Serbe des Sciences et des Arts - 2001.

[3] M. Shikhi and V. Anil Kumar, Common neighbor polynomial of graphs, Far
East Journal of mathematical sciences,Volume 102, Number 6, 2017, Pages
1201-1221.

[4] M. Shikhi and V. Anil Kumar, Common neighbor polynomial of graph op-
erations, Far East Journal of mathematical sciences, Volume 102, Issue 11,
2017,Pages 2629 - 2641.

[5] Sherif El- Basil, Applications of caterpillar trees in Chemistry and Physics,
Journal of Mathematical Chemistry,1987,pages 153-174.

204


	Introduction
	Main Results