3860 10567 1 PB

EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 14, No. 1, 2021, 173-191

ISSN 1307-5543 – ejpam.com
Published by New York Business Global
On the Independent Neighborhood Polynomial of the

Cartesian Product of Some Special Graphs
Normalah Abdulcarim1,∗ , Susan Dagondon2 , Emmy Chacon2
1
Department of Mathematics, College of Natural Sciences and Mathematics, Mindanao
State University Main Campus, 9700 Marawi City, Philippines
2
Department of Mathematics and Statistics, College of Science and Mathematics,
Center of Graph Theory, Algebra, and Analysis-Premier Research Institute of Science and
Mathematics, Mindanao State University-Iligan Institute of Technology, 9200 Iligan City,
Philippines
Abstract. Two vertices x, y of a graph G are adjacent, or[neighbors, if xy is an edge of G. A set

S of vertices in a graph G is a neighborhood set if G = hN [v]i where hN [v]i is the subgraph
v∈S
induced by v and all the vertices adjacent to v. If no two of the elements of S are adjacent, then
S is called an independent neighborhood set. The independent neighborhood polynomial of G of
Xm
order m is Ni (G, x) = ni (G, j)xj where ni (G, j) is the number of independent neighborhood
j=ηi (G)
set of G of size j and ηi (G) is the minimum cardinality of an independent neighborhood set of
G. This paper investigates the independent neighborhood polynomial of the Cartesian product of
some special graphs.
2020 Mathematics Subject Classifications: 05C31, 05C69, 05C76
Key Words and Phrases: Independent Neighborhood Set, Neighborhood Polynomial, Cartesian
Product
1. Introduction
The history of graph theory may be specifically traced to 1735 when the Swiss Math-
ematician Leonhard Euler solve the königberg bridge problem. There are number of
applications of graph theory that have been widely studied. A graph polynomial is one
of the algebraic reperesentations for graph. In this paper, we study a new type of graph
polynomial called the independent neighborhood polynomial [10]. Throughout this paper,
we consider only a finite, simple, undirected graphs without loops and multiple edges.
∗
Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v14i1.3860
Email addresses: n [email protected] (N. Abdulcarim),
[email protected] (S. Dagondon), [email protected] (E. Chacon)
http://www.ejpam.com 173
c 2021 EJPAM All rights reserved.
N. Abdulcarim, S. Dagondon, E. Chacon / Eur. J. Pure Appl. Math, 14 (1) (2021), 173-191 174
A graph G is a pair (V (G), E(G)) consisting of a nonempty finite set of vertices V (G)
and a set of edges E(G) of unordered pairs of elements of V (G). The cardinalities of V (G)
and E(G) are called the order and size of G, respectively. We write x = uv and say that u
and v are adjacent vertices; vertex u and edge x are incident with each other, so are v and
x. The two vertices incident with an edge are its endvertices or ends, and an edge joins
its ends. Two vertices of a graph G are said to be neighbors if they are adjacent in G.
The neighborhood of a vertex v ∈ V is the set NG (v) = {w : w ∈ V and vw ∈ E(G)}.
A vertex v is pendant if its neighborhood contains only one vertex; and edge e = uv is
pendant if one of its endvertices is a pendant vertex.
A graph H is called a subgraph of G, written H ⊆ G, if V (H) ⊆ V (G) and E(H) ⊆
E(G). If H ⊆ G and either V (H) is a proper subset of V (G) or E(H) is a proper subset of
E(G), then H is a proper subgraph of G. A subgraph F of a graph G is called an induced
subgraph of G, denoted by hF i, if whenever u and v are vertices of F and uv is an edge of
G, then uv is an edge of F as well.
A path is a nonempty graph P = (V, E) of the form
V = {v1 , · · · , vm } E = {v1 v2 , v2 v3 , · · · , vm−1 vm },
where the vi are all distinct.
In this research, we focused to determine the independent neighborhood sets of the
Cartesian product of some special graphs with path and represent them in a graph poly-
nomial called independent neighborhood polynomial. The readers may also read on the
following references: [1],[2],[3], [5],[9],[11] and [6].
2. Preliminaries
Definition 1. [7] A graph G is a bipartite graph, denoted by Km,n , if V (G) can be

partitioned into two subsets Vm and Vn of order m and n, respectively, called partite sets
such that every edge of G joins a vertex of Vn and a vertex of Vm . If G contains every
edges joining Vn and Vm , then G is called complete bipartite graph. A star is complete
bipartite K1,n , the vertex in the singleton partition class is called the apex vertex. A star
graph K1,n−1 is also called an n-star graph.
u1
u2
u
u3
u4
Figure 1: A star graph K1,4 with apex vertex u and pendant vertices u1 , u2 , u3 , u4
*
Definition 2. [6] The bistar graph B(m, n) is constructed by joining the apex vertices of
two stars K1,m and K1,n for m ≥ 1 and n ≥ 1 with disjoint vertex sets.
u1 v1
u2 u v
v2
u3
u4 v3
Figure 2: A bistar graph B(4, 3)
Definition 3. [4] The Banana tree graph Bm,n is the graph obtained by connecting one
leaf of each m copies of an n-star graph with a single root vertex that is distinct for all
the stars.
Figure 3: The Banana tree graph B3,5
Definition 4. [4] The Firecracker graph Fm,n is the graph obtained by the concatenation
of mn-stars by linking one leaf from each.
Figure 4: The Firecracker graph F3,5
Definition 5. [8] The n-centipede graph or simply Cenn is the tree on 2n vertices obtained
by joining the bottoms of n copies of the path graph P2 laid in a row with edges.
Cen4 Cen5
Figure 5: The Centipede graphs Cen4 and Cen5
Definition 6. [5] The Cartesian product of two graphs G and H, denoted GH, is the
graph where V (GH) = V (G)×V (H) and (g1 , h1 )(g2 , h2 ) ∈ E(GH) if and only if either
(i.) g1 = g2 and h1 h2 ∈ E(H) or
(ii.) h1 = h2 and g1 g2 ∈ E(G).
G H GH
Figure 6: Cartesian product of G and H
Definition 7. [11] A set S ⊆ V (G) is an independent neighborhood set of G, if S is a

neighborhood set and no two vertices in S are adjacent.
Definition 8. [11] Let G = (V, E) be a graph with m vertices. Then the independent
neighborhood polynomial of G of order m is
m
X
Ni (G, x) = ni (G, j)xj ,
j=ηi (G)
where ni (G, j) is the number of independent neighborhood set of G of size j and ηi (G) is the
minimum cardinality of an independent neighborhood set which is called the independent
neighborhood number of G.
Example 1. Consider the graph H below
v1 v2 v3
H:
v5 v4
The only independent neighborhood sets of H are {v2 , v4 } and {v1 , v3 , v5 }. Therefore,
the independent neighborhood polynomial of H is Ni (H, x) = x2 + x3 .
3. Independent Neighborhood Polynomial of the Cartesian product of

Some Special Graphs with Path Graph
In this section, the independent neighborhood sets of the Cartesian product of some
special graphs with path are determined and represented in an independent neighborhood
polynomial.
Theorem 1. For any path Pk and star K1,n ,
xb 2 cn+d 2 e + xd 2 en+b 2 c ,
( k k k k
k is odd
Ni (Pk K1,n , x) = k k
2x( 2 )n+( 2 ) , k is even
for any k, n ∈ Z+ .
(
1, apex vertex
Proof: Label V (Pk ) = {1, 2, · · · , k} and V (K1,n ) = .
2n pendant vertices
(1,2) (1,4)
(1,1) (2,2) (2,4)

(1,2n) (1,6)
(2,1) (k,2) (k,4)
(2,2n) (2,6)
· · · (1,8) (k,1)
(k,2n) (k,6)
· · · (2,8)
· · · (k,8)
Then
V (Pk K1,n ) = {(x, y) : x = 1, 2 · · · , k, y = 1, 2, 4, 6, · · · , 2n}
and
E(Pk K1,n ) = {(x, y)(w, z) : x = w and yz ∈ E(K1,n ) or xw ∈ E(Pk ) and y = z}.
Observe that for any (x, y)(w, z) ∈ E(Pk K1,n ), we have the following cases:
case 1: {(x, y), (w, z) : x = w is odd while y is even and z = 1}.
case 2: {(x, y), (w, z) : x = w is even while y is even and z = 1}.
case 3: {(x, y), (w, z) : y = z = 1 while x is even and w is odd}.
case 4: {(x, y), (w, z) : y = z is even while x is even and w is odd}.
Now, let S = {(p, q) ∈ V (Pk K1,n ) : p and q are both even or p and q are both odd}
and T = {(r, s) ∈ V (Pk K1,n ) : r is odd and s is even or r is even and s is odd}. We
claim that S and T are the independent neighborhood sets of Pk K1,n that is, we show
that
[
a. no two vertices in S are adjacent and hN [u]i = Pk K1,n ; and
u∈S
[
b. no two vertices in T are adjacent and hN [v]i = Pk K1,n .
v∈T
a. Let (x, y), (w, z) ∈ S. We consider the following cases:

Case 1: If x, y, w, z are all odd, then (x, y)(w, z) ∈/ E(Pk K1,n ). Thus, (x, y), (w, z)
are not adjacent.
Case 2: If x, y, w, z are all even, then (x, y)(w, z) ∈
/ E(Pk K1,n ). Thus, (x, y), (w, z)
are not adjacent.
Case 3: If x, y are even and w, z are odd, then (x, y)(w, z) ∈ / E(Pk K1,n ). Thus,
(x, y), (w, z) are not adjacent.
Case 4: If x, y are odd and w, z are even, then (x, y)(w, z) ∈ / E(Pk K1,n ). Thus,
(x, y), (w, z) are not adjacent.
Hence, in all above cases, none of the vertices of S are adjacent.
[ [
Next, we will show that hN [u]i = Pk K1,n . Assume to the contrary that hN [u]i =
6
u∈S u∈S !
[
Pk K1,n . Then there exists (x, y)(w, z) ∈ E(Pk K1,n ) such that (x, y)(w, z) ∈
/E hN [u]i ,
u∈S
particularly, both (x, y) and (w, z) are not in S. It follows that both x and y are not odd
or both x and y are not even. Similar case for w and z. Now, if x is odd, y is even,
w is odd and z is even, then (x, y)(w, z) ∈ / E(Pk K1,n ). This is a contradiction. If we
consider x is odd, y is even, w is even and z is odd, then (x, y)(w, z) ∈ / E(Pk K1,n ).
Similar case when x is even, y is odd, w is odd, z is even and for x is even, y is odd, w is
even, z is odd. Hence, in either[cases, (x, y)(w, z) ∈
/ E(Pk K1,n ) which is a contradiction
to the assumption. Therefore, hN [u]i = Pk K1,n . Consequently, S is an independent
u∈S
neighborhood set of Pk K1,n . Following the same argument in (a) for (b), we can show
that T is also an independent neighborhood set of Pk K1,n .
Now, if we let S1 = {(x, y) : x and y are odd}, S2 = {(x, y) : x and y are even},
T1 = {(x, y) : x is odd and y is even} and T2 = {(x, y) : x is even and y is odd}, then
S1 ∪ S2 ∪ T1 ∪ T2 = V (Pk K1,n ) and that S1 ∪ S2 = S and T = T1 ∪ T2 . Notice that when
k is odd,
k k k k
|S1 | = , |S2 | = n, |T1 | = n, |T2 | = .
2 2 2 2
Hence, |S| = k2 n + k2 and |T | = k2 n + k2 .

Thus, Ni (Pk K1,n , x) = xb 2 cn+d 2 e + xd 2 en+b 2 c when k is odd. For k is even, observe
k k k k
k k
that k = k = k . It follows that |S| = |T | and so, N (P K , x) = 2x( 2 )n+( 2 ) .

2 2 2 i k 1,n
Consequently,
xb 2 cn+d 2 e + xd 2 en+b 2 c ,
( k k k k
k is odd
Ni (Pk K1,n , x) = k k
2x( 2 )n+( 2 ) , k is even.
Theorem 2. For any path Pk and Bistar graph B(m, n),
Ni (Pk Bm,n , x) = xd 2 e(m+1)+b 2 c(n+1) + xb 2 c(m+1)+d 2 e(n+1)

k k k k
for any k, m, n ∈ Z+ .
Proof: Label the vertices of B(m, n) as iu , jv , 0u , 0v , i = 1, · · · , m, j = 1, · · · , n where
0u and 0v are the apex vertices.
1u 1v
2u 0u 0v 2v
.. ..
. .
mu nv
Then
V (Pk B(m, n)) = {(r, ia ), (r, jv ), (r, 0u ), (r, 0v ) : r = 1, · · · , k, i = 1, · · · , m, j = 1, · · · , n
and E(Pk B(m, n)) = {(w, xa )(y, zb ) : w = y, a = b and either x = 0 or z = 0, w =

y + 1, a = b and x = z, and w = y, a = u, b = v and x = 0 = z}.
Consider the following sets of vertices.
Ar = {(r, iu ) : r = 1, · · · , k, i = 1 · · · , m} ∪ {{(r, 0v )}
Bs = {(s, jv ) : s = 1, · · · , k, j = 1 · · · , n} ∪ {{(s, 0u )}.
Let
S = Ar ∪ Bs such that r is odd and s is even and

T = Ar ∪ Bs such that r is even and s is odd.
 


 (r, iu ) : r is odd, i = 1, · · · , m 

(r, iu ) : r is even, i = 1, · · · , m

(s, j ) : s is even, j = 1, · · · , n 
(s, j ) : s is odd, j = 1, · · · , n
v v
Then S = and T =


 (r, 0 v ) : r is odd 

(r, 0v ) : r is even

(s, 0 ) : s is even 
(s, 0 ) : s is odd
u u
We claim that S and T are the independent neighborhood sets of Pk B(m, n). First,
we show that no two vertices in S are adjacent. Observe that for any (r, iu ), (s, 0u ) ∈ S,
(r, iu )(s, 0u ) ∈
/ E (Pk B(m, n)) since r is odd in (r, jiu ) and s is even in (s, 0u ). Similarly,
(1, 1u ) (1, 1v )
(1, 0u ) (1, 0v )
(1, 2u ) (1, 2v )
.. ..
. .
(1, mu ) (1, nv )
(2, 1u ) (2, 1v )
(2, 0u ) (2, 0v )
(2, 2u ) (2, 2v )
.. ..
. .
(2, mu ) (2, nv )
(k, 1u ) (k, 1v )
(k, 0u ) (k, 0v )
(k, 2u ) (k, 2v )
.. ..
. .
(k, mu ) (k, nv )
(s, jv )(r, 0v ) ∈
/ E (Pk B(m, n)) for any (s, jv ), (r, 0v ) ∈ S. Hence, none of the vertices of S
are adjacent. [ [
Next, we show that hN [v]i = Pk B(m, n). Assume to the contrary that hN [v]i =
6
v∈S v∈S
! implies there exists (w, xa )(y, zb ) ∈ E(Pk B(m, n)) such that (w, xa )(y, zb ) ∈
Pk B(m, n). This /
[
E hN [v]i . Consider the following cases:
v∈S
case I. w = y, a = b and either x = 0 or y = 0

WLOG, let z = 0.
!
[
i. If (r1 , iu )(r2 , 0u ) ∈
/ E hN [v]i , then both (r1 , iu ), (r2 , 0u ) ∈
/ S. It follows
v∈S
that r2 is odd and so is r1 . But (r1 , iu ) ∈ S for r1 odd. This is a contradiction.
!
[
ii. If (s1 , jv )(s2 , 0v ) ∈
/ E hN [v]i , then both (s1 , jv ), (s2 , 0v ) ∈
/ S. It follows
v∈S
that s2 is even and so is s1 because (s1 , jv )(s2 , 0v ) ∈ E (Pk B(m, n)) when
s1 = s2 . But (s1 , jv ) ∈ S for s1 even which is a contradiction.
case II. w = y + 1, a = b and x = z
Assume that x = z 6= 0.
!
[
i. When (r1 , i1u )(r2 , i2u ) ∈
/E hN [v]i , then both (r1 , i1u ), (r2 , i2u ) ∈
/ S. This
v∈S
implies r1 and r2 are odd. But (r1 , i1u )(r2 , i2u ) ∈
/ E (Pk B(m, n)) which is a
contradiction. !
[
ii. When (s1 , j1u )(s2 , j2u ) ∈
/ E hN [v]i , we will arrive contradiction similar
v∈S
to i.
Next, we assume x = z = 0.
!
[
iii. If (r1 , 0u )(r2 , 0u ) ∈
/ E hN [v]i , then both (r1 , 0u ), (r2 , 0u ) ∈
/ S. This im-
v∈S
plies r1 is odd and r2 is even. But (r2 , 0u ) ∈ S, a contradiction.
!
[
iv. If (s1 , 0v )(s2 , 0v ) ∈
/E hN [v]i , then both (s1 , 0v ), (s2 , 0v ) ∈
/ S. Note that
v∈S
whenever s1 is odd, s2 is even. But (s, 0v ) ∈ S for s even. This is a contradic-
tion.
case III. w = y, a = u, b = v and x = 0 =!z

[
If (r, 0u )(s, 0v ) ∈
/ E hN [v]i , then (r, 0u ), (s, ov ) ∈
/ S. This implies r is odd.
v∈S
But r = s and thus, s is also odd. This is a contradiction.
! of the above cases, we arrived at a contradiction. Thus, (w, xa )(y, zb ) ∈

Hence, in either
[ [
E hN [v]i . Consequently, hN [v]i = Pk B(m, n). Hence, S is an independent
v∈S v∈S
neighborhood set of Pk B(m, n). Following the same argument in S, we can also show
that T is an independent neighborhood set of Pk B(m, n)
Now, observe that for each Ai and Br , |Ai | = m + 1 and |Br | = |n + 1|. Thus,
X X
|S| = |Ai | + |Br |
i is odd r is even

k k
= (m + 1) + (n + 1)
2 2
and
X X
|T | = |Ai | + |Br |
i is even r is odd

k k
= (m + 1) + (n + 1).
2 2
Therefore,
Ni (Pk B(m, n), x) = xd 2 e(m+1)+b 2 c(n+1) + xb 2 c(m+1)+d 2 e(n+1) .

k k k k
Theorem 3. For any path Pk and Banana graph Bm,n ,
Ni (Pk Bm,n , x) = xb 2 cm(n−1)+d 2 e(m+1) + xd 2 em(n−1)+b 2 c(m+1)

k k k k
for any k, m, n ∈ Z+ .
Proof: Label the vertices of each star in Bm,n by ij, i = 1, · · · , m, j = 1, · · · , n and 0

as the root vertex in Bm,n .
13 23 m3
1n − 1 1n 12 2n − 1 2n 22 mn − 1 mn m2
···
11 21 m1
Then V (Pk Bm,n ) = {(e, ij), (e, 0) : e = 1, · · · , k, i = 1, · · · , m, j = 1, · · · , n} as

shown in the figure below:
Observe that
a. (e1 , i1 j1 )(e2 , i2 j2 ) ∈ E(Pk Bm,n ) if
i. e1 = e2 , i1 = i2 and either j1 = n or j2 = n; or
ii. e1 = e2 + 1, i1 = i2 and j1 = j2 .
b. (e1 , i1)(e2 , 0) ∈ E(Pk Bm,n ) if e1 = e2 , and
c. (e1 , 0)(e2 , 0) ∈ E(Pk Bm,n ) if e1 = e2 + 1.
Consider the following sets:
Ap = {(e, ij) : e is odd, i = 1, · · · , m, j = 1, · · · , n − 1},

Aq = {(e, ij) : e is even, i = 1, · · · , m, j = 1, · · · , n − 1},
Bp = {(e, 0) : e is odd} ∪ {(e, in) : e is odd, i = 1, · · · , m},
Bq = {(e, 0) : e is even} ∪ {(e, in) : e is even, i = 1, · · · , m}.
Let S = Ap ∪ Bq and T = Aq ∪ Bp . We claim that S and T are the independent

neighborhood sets of Pk Bm,n . First, we show that no two vertices in S are adjacent.
Observe that for any (e1 , i1 j1 ), (e2 , i2 j2 ) ∈ S such that e1 = e2 and i1 = i2 , we have
j1 6= n and j2 6= n. For the case when either j1 = n or j2 = n, e1 6= e2 . Also, for
(e1 , i1 j1 ), (e2 , i2 j2 ) ∈ S such that e1 = e2 + 1 and i1 = i2 , j1 6= j2 . This implies (e1 , i1 j1 )
and (e2 , i2 j2 ) are non-adjacents. Note that for any (e1 , i1), (e2 , 0) ∈ S, e1 is odd while e2 is
even and so, (e1 , i1), (e2 , 0) are non-adjacents. Hence, none of the vertices in S are adjacent.
(1, 13) (1, 23) (1, m3)
(1, 1n − 1) (1, 1n) (1, 12) (1, 2n − 1) (1, 2n) (1, 22) (1, mn − 1) (1, mn) (1, m2)
···
(1, 11) (1, 21) (1, m1)
(1, 0)
(2, 13) (2, 23) (2, m3)
(2, 1n − 1) (2, 1n) (2, 12) (2, 2n − 1) (2, 2n) (2, 22) (2, mn − 1) (2, mn) (2, m2)
···
(2, 11) (2, 21) (2, m1)
(2, 0)
(k, 13) (k, 23) (k, m3)
(k, 1n − 1) (k, 1n) (k, 12) (k, 2n − 1) (k, 2n) (k, 22) (k, mn − 1) (k, mn) (k, m2)
···
(k, 11) (k, 21) (k, m1)
(k, 0)
[ [
Now, we will show that hN [v]i = Pk Bm,n . Assume to the contrary that hN [v]i =
6
v∈S v∈S
!
[
Pk Bm,n . Then there exists xy ∈ E(Pk Bm,n ) such that xy ∈
/E hN [v]i .
v∈S
case I: x = (e1 , i1 j1 ), y = (e2 , i2 j2 )
i. Consider e1 = e2 , i1 = i2 and either j1 = n or j2 = n. When e1 = e2 is even,

(e, in) ∈ Bq ⊆ S while when e1 = e2 is odd, (e, ij) ∈ Ap ⊆ S. This implies
either (e1 , i1 j1!) ∈ S or (e2 , i2 j2 ) ∈ S and follows that (e1 , i1 j1 )(e2 , i2 j2 ) ∈
[
E hN [v]i which is a contradiction.
v∈S
ii. Consider e1 = e2 + 1, i1 = i2 and j1 = j2 . Then either e1 is odd and e2 is even
or e1 is even and e2 is odd. But in either cases, ! (e, ij) ∈ S when e is odd and
[
consequently, (e1 , i1 j1 )(e2 , i2 j2 ) ∈ hN [v]i . This is a contradiction.
v∈S
case II: x = (e1 , i1 ), y = (e2 , 0)

Since (e1 , i1 )(e2 , 0) ∈ E (Pk Bm,n ) , e1 = e2 . Then e2!must be odd. But (e1 , i1 ) ∈ S
[
when e1 is odd and so, (e1 , i1 )(e2 , 0) ∈ E hN [v]i which is a contradiction.
v∈S
case III: x = (e1 , 0), y = (e2 , 0)

Clearly, when e1 is odd, e2 is even and vice versa. But (e, 0) ∈ S when e is even. !
[
This implies either (e1 , 0) ∈ S or (e2 , 0) ∈ S. So, (e1 , 0)(e2 , 0) ∈ E hN [v]i
v∈S
which is a contradiction.
!
[
In either of the above cases, we arrived at a contradiction. Thus, xy ∈ E hN [v]i .
[ v∈S
Consequently, hN [v]i = Pk Bm,n . Following same argument in S, we can easily show
v∈S
that T is also an independent neighborhood set in Pk Bm,n .
Now, observe that
|Ap | = {(e, ij) : e is odd, i = 1, · · · , m, j = 1, · · · , n − 1}

k
= m(n − 1),
2
|Aq | = {(e, ij) : e is even, i = 1, · · · , m, j = 1, · · · , n − 1}

k
= m(n − 1),
2
|Bp | = {(e, 0) : e is odd} ∪ {(e, in) : e is odd, i = 1, · · · , m}

k k
= + m
2 2

k
= (m + 1)
2
and
|Bq | = {(e, 0) : e is even} ∪ {(e, in) : e is even, i = 1, · · · , m}

k k
= + m
2 2

k
= (m + 1).
2
Thus,
k k
|S| = |Ap | + |Bq | = m(n − 1) + (m + 1)
2 2
and
k k
|T | = |Aq | + |Bp | = m(n − 1) + (m + 1).
2 2
Therefore,
Ni (Pm Bm,n , x) = xb 2 cm(n−1)+d 2 e(m+1) + xd 2 em(n−1)+b 2 c(m+1) .

k k k k
Theorem 4. For any path Pk and Firecracker graph Fm,n ,
Ni (Pk Fm,n , x) = xd 2 e(d 2 e(n−1)+b 2 c)+b 2 c(d 2 e+b 2 c(n−1))

k m m k m m
+ xb 2 c(d 2 e(n−1)+b 2 c)+d 2 e(d 2 e+b 2 c(n−1))

k m m k m m
for any k, m, n ∈ Zn .
Proof: Label the vertices of Fm,n by ij, i = 1, · · · , m, j = 1, · · · , n as shown in the

figure below:
13 23 m3
1n 2n mn
1n − 1 12 2n − 1 22 mn − 1 m2
11 21 m1
Then V (Pk Fm,n ) = {(e, ij) : e = 1, · · · , k, i = 1, · · · , m, j = 1, · · · , n} and

E(Pk Fm,n ) = {(e1 , i1 j1 )(e2 , i2 j2 ) : e1 = e2 and i1 j1 i2 j2 ∈ E(Fm,n ) or e1 e2 ∈ E(Pk ) and i1 =
i2 , j1 = j2 } as shown in the figure below:
Observe that for any (e1 , i1 j1 )(e2 , i2 j2 ) ∈ E(Pk Fm,n ), either
i.) e1 = e2 , i1 = i2 , j1 = n or j2 = n;
ii.) e1 = e2 , i1 = i2 + 1, j1 = 1 = j2 ; or
iii.) e1 = e2 + 1, i1 = i2 , j1 = j2 .
(1, 13) (1, 23) (1, m3)
(1, 1n − 1) (1, 1n) (1, 12) (1, 2n − 1) (1, 2n) (1, 22) (1, mn − 1) (1, mn) (1, m2)
···
(1, 11) (1, 21) (1, m1)

(2, 13) (2, 23) (2, m3)
(2, 1n − 1) (2, 1n) (2, 12) (2, 2n − 1) (2, 2n) (2, 22) (2, mn − 1) (2, mn) (2, m2)
···
(2, 11) (2, 21) (2, m1)

(k, 13) (k, 23) (k, m3)
(k, 1n − 1) (k, 1n) (k, 12) (k, 2n − 1) (k, 2n) (k, 22) (k, mn − 1) (k, mn) (k, m2)
···
(k, 11) (k, 21) (k, m1)
Ap = {(p, ij) : p is odd, i is odd, j = 1, · · · , n − 1}, Bp = {(p, in) : p is odd, i is odd}

Aq = {(q, ij) : q is even, i is odd, j = 1, · · · , n − 1}, Bq = {(q, in) : q is even, i is odd}
Cp = {(p, ij) : p is odd, i is even, j = 1, · · · , n − 1}, Dp = {(p, in) : p is odd, i is even}
Cq = {(q, ij) : q is even, i is even, j = 1, · · · , n − 1}, Dq = {(q, in) : q is even, i is even}
Let S = Ap ∪ Dp ∪ Bq ∪ Cq and T = Aq ∪ Dq ∪ Bp ∪ Cp . We claim that S and T are the

independent neighborhood sets of Pk Fm,n . First, we show that no two vertices in S are
adjacent. Since each Ap and Cq consist of the pendant vertices in each star, Ap and Cq
are independent sets. Also, since each Bq and Dp consist of apex vertices in each star, Bq
and Dp are independent sets. We note that elements of Ap and Dp are not adjacent since
i is odd in Ap and i is even in Dp . Similarly, elements of Bq and Cq are non-adjacent.
Hence, the set Ap ∪ Dp ∪ Bq ∪ Cq have non-adjacent vertices.
[ [
Next, we show that hN [v]i = Pk Fm,n . Assume to the contrary that hN [v]i =
6
v∈S v∈S
! there exists (e1 , i1 j1 )(e2 , i2 j2 ) ∈ E (Pk Fm,n ) such that (e1 , i1 j1 )(e2 , i2 j2 ) ∈
Pk Fm,n . Then /
[
E hN [v]i . This implies (e1 , i1 j1 ), (e2 , i2 j2 ) ∈/ S.
v∈S
case 1: e1 = e2 , i1 = i2 , either j1 = n or j2 = n.
WLOG, we may assume j1 = n. Since (e1 , i1 j1 ) ∈
/ S, either either e1 and i1 are odd
or e1 and i1 are even. Consider e1 and i1 are odd. Since e1 = e2 and i1 = i2 , e2
and i2 are odd. But (e2 , i2 j2 ) ∈ Ap ⊆ S. This is a contradiction. Similarly, if we

consider e1 and i1 to be even, then (e2 , i2 j2 ) ∈ Cq ⊆ S
case 2: e1 = e2 , i1 = i2 + 1 and j1 = 1 = j2 .
Since (e1 , i1 j1 ) ∈
/ S, either e1 is odd and i1 is even or e1 is even and i1 is odd. When
e1 is odd and i1 is even, e2 and i2 are odd. But (e2 , i2 j2 ) ∈ Ap ⊆ S. This is a
contradiction. Similarly, a contradiction will arrive when e1 is even and i1 is odd.
case 3: e1 = e2 + 1, i1 = i2 and j1 = j2 .
Since (e1 , i1 j1 ) ∈
/ S, we consider the following cases: For j = 1, · · · , n − 1, if e1 is
even, i1 is odd, then it follows that e2 and i2 are odd. But (e2 , i2 j2 ) ∈ S. This is a
contradiction. Similarly, when e1 is odd and i1 is even, then e2 and i2 are even for
which (e2 i2 j2 ) ∈ S, a contradiction. For j = n, if e1 and i1 are even, then e2 is odd
and i1 is even. So, (e2 , i2 j2 ) ∈ S, a contradiction. Also, for if e1 and i1 are odd, e2
is even and i2 is odd and that (e2 , i2 j2 ) ∈ S which is a contradiction.
Thus, in either!of the above cases, we arrived a contradiction. Hence, (e1 , i1 j1 )(e2 , i2 j2 ) ∈
[ [
E hN [v]i . Consequently, hN [v]i = Pk Fm,n . Following the same argument in S,
v∈S v∈S
we can verify that T is also an independent neighborhood set of Pk Fm,n .
Finally,
|S| = |Ap | + |Dp | + |Bq | + |Cq |

l m j k l m j k
k m k m k m k m
= (n − 1) + + + (n − 1)
2 2 2 2 2 2 2 2
l m j m k k l m m j m k
k m
= (n − 1) + + + (n − 1)
2 2 2 2 2 2
and
|T | = |Aq | + |Dq | + |Bp | + |Cp |

l m j k l m j k
k m k m k m k m
= (n − 1) + + + (n − 1)
2 2 2 2 2 2 2 2
l m
k m j m k k l m m j m k
= (n − 1) + + + (n − 1) .
2 2 2 2 2 2
Therefore,
Ni (Pk Fm,n , x) = xd 2 e(d 2 e(n−1)+b 2 c)+b 2 c(d 2 e+b 2 c(n−1))

k m m k m m
+ xb 2 c(d 2 e(n−1)+b 2 c)+d 2 e(d 2 e+b 2 c(n−1)) .

k m m k m m
Theorem 5. For any path Pk and Centipede graph Cenn , Ni (Pk Cenn , x) = 2xnk for
any k, n ∈ Z+ .
1a 2a 3a na
1b 2b 3b nb
Proof: Label the vertices of Cenn by ja , jb : j = 1, · · · , n and define its edges by

E(Cenn ) = {ja jb : j = 1, · · · , n} ∪ {jb (j + 1)b : j = 1 · · · , n − 1} as shown in the figure
below:
Then V (Pk Cenn ) = {(i, ja ), (i, jb ) : i = 1, · · · , k, j = 1, · · · , n}.
(1, 1a ) (1, 2a ) (1, 3a ) (1, na )
(1, 1b ) (1, 2b ) (1, 3b ) (1, nb )
(2, 1a ) (2, 2a ) (2, 3a ) (2, na )
(2, 1b ) (2, 2b ) (2, 3b ) (2, nb )
(k, 1a ) (k, 2a ) (k, 3a ) (k, na )
(k, 1b ) (k, 2b ) (k, 3b ) (k, nb )

Observe that
• (i1 , j1a )(i2 , j2b ) ∈ E(Pk Cenn ) if i1 = i2 and j1 = j2 ,
• (i1 , j1a )(i2 , j2a ) ∈ E(Pk Cenn ) if i1 = i2 + 1 and j1 = j2 and
• (i1 , j1b )(i2 , j2b ) ∈ E(Pk Cenn ) if either
i.) i1 = i2 , j1 = j2 + 1 or
ii.) i1 = i2 + 1, j1 = j2 .
Ap = {(i, ja ) : i and j are odd}, Bp = {(i, ja ) : i is odd and j is even}

Aq = {(i, ja ) : i is even and j is odd}, Bq = {(i, ja ) : i and j are even}
cp = {(i, jb ) : i and j are odd}, Dp = {(i, jb ) : i is odd and j is even}
Cq = {(i, jb ) : i is even and j is odd}, Dq = {(i, jb ) : i and j are even}.
 S = Ap ∪ Dp ∪ Bq ∪ Cq and T = Aq ∪ Dq∪ Bp ∪ Cp , that is,

Let


 (i, ja ) : i and j are odd 

 (i, ja ) : i is even and j is odd

(i, j ) : i and j are even 
(i, j ) : i is odd and j is even
a a
S= and T =


 (i, jb ) : i is even and j is odd 

 (i, jb ) : i and j are odd

(i, j ) : i is odd and j is even 
(i, j ) : i and j are even .
b b
We claim that S and T are the independent neighborhood sets of Pk Cenn . First,
we show that no two vertices in S are adjacent. Observe that for any (i1 , j1a ), (i2 , j2a ) ∈
S, (i1 , j1a )(i2 , j2a ) ∈
/ E(Pk Cenn ) since j1 6= j2 . Also, for any (i1 , j1a ), (i2 , j2b ) ∈ S,
(i1 , j1a )(i2 , j2b ) ∈
/ E(Pk Cenn ) since when i1 = i2 , j1 6= j2 and when j1 = j2 , i1 6= i2 .
Furthermore, any (i1 , j1b ), (i2 , j2b ) ∈ S, (i1 , j1b )(i2 , j2b ) ∈/ E(Pk Cenn ) since both i1 6= i2
and j1 6= j2 . Hence, no two[ vertices in S are adjacent. [
Next, we will show that hN [v]i = Pk Cenn . Assume to the contrary that hN [v]i =
6
v∈S ! v∈S
[
Pk Cenn . Then there exists xy ∈ E(Pk Cn ) such that xy ∈ /E hN [v]i . This implies
v∈S
both x, y ∈
/ S.
case 1: x = (i1 , j1a ) and y = (i2 , j2b )

Since (i1 , j1a ) ∈
/ S, either i1 is even and j1 is odd or i1 is odd and j1 is even.
If i1 is even, j1 is odd, then i2 is even and j2 is odd. But (i2 , j2b ) ∈ S. This is a
contradiction. For i1 odd and j1 even, i2 is odd and j2 is even. Similarly, (i2 , j2b ) ∈ S
which is a contradiction.
case 2: x = (i1 , j1a ) and y = (i2 , j2a )

When (i1 , j1a ) ∈/ S, it follows that either i1 is even and j1 is odd or i1 is odd and j1 is
even. Consider i1 to be even and j1 to be odd. Since (i1 , j1a )(i2 , j2a ) ∈ E(Pk Cenn )
if i1 = i2 + 1 and j1 = j2 , it follows that i2 and j2 are odd and this is a contradiction

for (i2 , j2a ) ∈ S. Similarly, when i1 is odd and j1 is even, i2 and j2 are even and this
is a contradiction since (i2 , j2a ) ∈ S.
case 3: x = (i1 , j1b ) and y = (i2 , j2b )

Since (i1 , j1b ) ∈
/ S, either i1 and j1 are odd or even. Similarly, (i2 , j2b ) ∈ / S implies i2
and j2 are odd or even. But if i1 , j1 , i2 , j2 are all odd, (i1 , j1b )(i2 , j2b ) ∈
/ E(Pk Cenn ).
Also, when i1 , i2 , j1 , j2 are all even, (i1 , j1b )(i2 , j2b ) ∈
/ E(Pk Cenn ). If we consider
i1 , j1 to be odd and i2 , j2 to be even, clearly, (i1 , j1b )(i2 , j2b ) ∈
/ E(Pk Cenn ). Hence,
all possibilities yield a contradiction.
!
[ [
Thus, xy ∈ E hN [v]i . Consequently, hN [v]i = Pk Cenn . Thus, S is an in-
v∈S v∈S
dependent neighborhood set of Pk Cenn . We can also verify that T is an independent
neighborhood set of Pk Cenn by following thesame
argumentinS.
Lastly, observe that |Ap | = k2 n2 , |Dp | = k2 n2 , |Bq | = k2 n2 , |Cq | = k2 n2 , |Aq | =

k n k n k n k n
2 2 , |Dq | = 2 2 , |Bp | = 2 2 and |Cp | = 2 2 . Hence,
|S| = |Ap | + |Dp | + |Bq | + |Cq |

l m j k j k l m
k n k n k n k n
= + + +
2 2 2 2 2 2 2 2
l m j k l m j k
k n n k n n
= + + +
2 2 2 2 2 2
l n m j n k k k
= + +
2 2 2 2
= nk
and
|T | = |Aq | + |Dq | + |Bp | + |Cp |

l m j k j k l m
k n k n k n k n
= + + +
2 2 2 2 2 2 2 2
l n m j n k k k
= + +
2 2 2 2
= nk.
Therefore, Ni (Pk Cn , x) = 2xnk .
Remark 1. When m = 2 in Theorem 3.4,
Ni (Pk F2,n , x) = xd 2 e(d 2 e(n−1)+b 2 c)+b 2 c(d 2 e+b 2 c(n−1)) + xb 2 c(d 2 e(n−1)+b 2 c)+d 2 e(d 2 e+b 2 c(n−1))
k 2 2 k 2 2 k 2 2 k 2 2
= xd 2 en+b 2 cn + xb 2 cn+d 2 en
k k k k
REFERENCES 191
= 2xn(d 2 c+b 2 c)
k k
= 2xnk
= Ni (Pk Cenn , x).
Acknowledgements
This research is funded by the Department of Science and Technology (DOST), Min-
danao State University IIT, Department of Research, Office of the Vice Chancellor for
Research and Extension(OVCRE), and Mindanao State University Main Campus (MSU
Main).
References
[1] A. Alwardi and P.M. Shivaswamy. On the neighbourhood polynomial of graphs.

Bulletin of the Society of Mathematicians Banja Luka, 6:13–24.
[2] F. Buckley and F. Harary. Distance in Graphs. Addison-Wesley Series in Mathemat-

ics, 1990.
[3] R. Diestel. Graph Theory. Springer Nature, 2017.
[4] M.S. Sardar et.al. Computing topological indices of the line graphs of banana tree
graph and firecracker graph. Applied Mathematics and Nonlinear Sciences, 2:83–92,
2017.
[5] R. Hammack et.al. Handbook of Product of Graphs. CRC Press Taylor and Francis
Group, London and New York, 2011.
[6] S. Ganesh and R. Revathi. Analysis of some bistar related mmd graphs. International
Journal of Pure and Applied Mathematics, 118(10):407–413, 2018.
[7] F. Harary. Graph Theory. Addison-Wesley Publishing Company, 1969.
[8] M. Khasif. Chromatic polynomials and chromaticity of some linear h-hypergraphs.

1969.
[9] V.R. Kulli. The neighborhood graph of a graph. International Journal of Fuzzy
Mathematical Archive, 8(2):93–99, 2015.
[10] V. E. Levit and E. Mandrescui. The independence polynomial of a graph-a survey.

In Proceedings of the 1st International Conference on Algebraic Informatics, pages
233–254, 2005.
[11] K.B. Murthy and Puttaswamy. On the independent neighbourhood polynomial of

graphs. Indian Streams Research Journal, 5(12):1–7, 2015.

3860 10567 1 PB

Uploaded by

Copyright:

Available Formats

3860 10567 1 PB

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

3860 10567 1 PB

Uploaded by

Copyright:

Available Formats

EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS

Vol. 14, No. 1, 2021, 173-191

On the Independent Neighborhood Polynomial of the

Abstract. Two vertices x, y of a graph G are adjacent, or[neighbors, if xy is an edge of G. A set

Definition 1. [7] A graph G is a bipartite graph, denoted by Km,n , if V (G) can be

Figure 3: The Banana tree graph B3,5

Figure 4: The Firecracker graph F3,5

Definition 7. [11] A set S ⊆ V (G) is an independent neighborhood set of G, if S is a

3. Independent Neighborhood Polynomial of the Cartesian product of

(1,1) (2,2) (2,4)

E(Pk K1,n ) = {(x, y)(w, z) : x = w and yz ∈ E(K1,n ) or xw ∈ E(Pk ) and y = z}.

a. Let (x, y), (w, z) ∈ S. We consider the following cases:

Theorem 2. For any path Pk and Bistar graph B(m, n),

Ni (Pk Bm,n , x) = xd 2 e(m+1)+b 2 c(n+1) + xb 2 c(m+1)+d 2 e(n+1)

V (Pk B(m, n)) = {(r, ia ), (r, jv ), (r, 0u ), (r, 0v ) : r = 1, · · · , k, i = 1, · · · , m, j = 1, · · · , n

and E(Pk B(m, n)) = {(w, xa )(y, zb ) : w = y, a = b and either x = 0 or z = 0, w =

S = Ar ∪ Bs such that r is odd and s is even and

case I. w = y, a = b and either x = 0 or y = 0

case III. w = y, a = u, b = v and x = 0 =!z

! of the above cases, we arrived at a contradiction. Thus, (w, xa )(y, zb ) ∈

Ni (Pk B(m, n), x) = xd 2 e(m+1)+b 2 c(n+1) + xb 2 c(m+1)+d 2 e(n+1) .

Theorem 3. For any path Pk and Banana graph Bm,n ,

Ni (Pk Bm,n , x) = xb 2 cm(n−1)+d 2 e(m+1) + xd 2 em(n−1)+b 2 c(m+1)

Proof: Label the vertices of each star in Bm,n by ij, i = 1, · · · , m, j = 1, · · · , n and 0

Then V (Pk Bm,n ) = {(e, ij), (e, 0) : e = 1, · · · , k, i = 1, · · · , m, j = 1, · · · , n} as

a. (e1 , i1 j1 )(e2 , i2 j2 ) ∈ E(Pk Bm,n ) if

b. (e1 , i1)(e2 , 0) ∈ E(Pk Bm,n ) if e1 = e2 , and

c. (e1 , 0)(e2 , 0) ∈ E(Pk Bm,n ) if e1 = e2 + 1.

Consider the following sets:

Ap = {(e, ij) : e is odd, i = 1, · · · , m, j = 1, · · · , n − 1},

Let S = Ap ∪ Bq and T = Aq ∪ Bp . We claim that S and T are the independent

(1, 13) (1, 23) (1, m3)

(1, 11) (1, 21) (1, m1)

(2, 11) (2, 21) (2, m1)

(k, 11) (k, 21) (k, m1)

case I: x = (e1 , i1 j1 ), y = (e2 , i2 j2 )

i. Consider e1 = e2 , i1 = i2 and either j1 = n or j2 = n. When e1 = e2 is even,

case II: x = (e1 , i1 ), y = (e2 , 0)

case III: x = (e1 , 0), y = (e2 , 0)

Now, observe that

|Ap | = {(e, ij) : e is odd, i = 1, · · · , m, j = 1, · · · , n − 1}

|Bq | = {(e, 0) : e is even} ∪ {(e, in) : e is even, i = 1, · · · , m}

Ni (Pm Bm,n , x) = xb 2 cm(n−1)+d 2 e(m+1) + xd 2 em(n−1)+b 2 c(m+1) .

Theorem 4. For any path Pk and Firecracker graph Fm,n ,

Ni (Pk Fm,n , x) = xd 2 e(d 2 e(n−1)+b 2 c)+b 2 c(d 2 e+b 2 c(n−1))

+ xb 2 c(d 2 e(n−1)+b 2 c)+d 2 e(d 2 e+b 2 c(n−1))

Proof: Label the vertices of Fm,n by ij, i = 1, · · · , m, j = 1, · · · , n as shown in the

Then V (Pk Fm,n ) = {(e, ij) : e = 1, · · · , k, i = 1, · · · , m, j = 1, · · · , n} and

(1, 13) (1, 23) (1, m3)

(1, 11) (1, 21) (1, m1)

(2, 11) (2, 21) (2, m1)

(k, 11) (k, 21) (k, m1)

Consider the following sets:

Ap = {(p, ij) : p is odd, i is odd, j = 1, · · · , n − 1}, Bp = {(p, in) : p is odd, i is odd}

Let S = Ap ∪ Dp ∪ Bq ∪ Cq and T = Aq ∪ Dq ∪ Bp ∪ Cp . We claim that S and T are the

and i2 are odd. But (e2 , i2 j2 ) ∈ Ap ⊆ S. This is a contradiction. Similarly, if we

|S| = |Ap | + |Dp | + |Bq | + |Cq |

|T | = |Aq | + |Dq | + |Bp | + |Cp |