Equi Neighbor Polynomial of Some Binary Graph Operations

P., Dhanya; V., Anil

doi:10.61091/jcmcc119-04

Abstract

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 119
Pages: 35-43

Research article

Equi Neighbor Polynomial of Some Binary Graph Operations

^¹, ^²

¹Department of Mathematics, CKGM Govt. College, Perambra P. O. Kozhikode, Kerala, India 673 525

²Department of Mathematics, University of Calicut, Malappuram, Kerala, India 673 635

Received: 16/01/2024
Accepted: 15/03/2024
Published: 31/03/2024

Copyright Link
License

Abstract

Let $G (V, E)$ be a simple graph of order $n$ with vertex set $V$ and edge set $E$ . Let $(u, v)$ denote an unordered vertex pair of distinct vertices of $G$ . For a vertex $u \in G,$ let $N (u)$ be the set of all vertices of $G$ which are adjacent to $u$ in $G .$ Then for $0 \leq i \leq n - 1$ , the $i$ -equi neighbor set of $G$ is defined as: $N_{e} (G, i) = {(u, v) : u, v \in V, u \neq v$ and $| N (u) | = | N (v) | = i} .$ The equi-neighbor polynomial $N_{e} [G; x]$ of $G$ is defined as $N_{e} [G; x] = \sum_{i = 0}^{(n - 1)} | N_{e} (G, i) | x^{i} .$ In this paper we discuss the equi-neighbor polynomial of graphs obtained by some binary graph operations.

Keywords:

i -

Equi neighbor set, Equi neighbor polynomial

1. Introduction

Let $G (V, E)$ be a simple graph of order $n$ with vertex set $V$ and edge set $E$ . Let $(u, v)$ denote an unordered vertex pair of distinct vertices of $G$ . For a vertex $u \in G,$ let $N (u)$ be the set of all vertices of $G$ which are adjacent to $u$ in $G .$ Then for $0 \leq i \leq n - 1$ , the $i$ -equi neighbor set of $G$ is defined as: $N_{e} (G, i) = {(u, v) : u, v \in V, u \neq v and | N (u) | = | N (v) | = i} .$ The equi-neighbor polynomial $N_{e} [G; x]$ of $G$ is defined as $N_{e} [G; x] = \sum_{i = 0}^{(n - 1)} | N_{e} (G, i) | x^{i}$ [1].

Binary graph operations are used to model the action between two network systems. Binary graph operations are usually known as graph products in which two initial graphs are acted together according to some specific rules to produce a new graph.

In this paper we discuss the equi-neighbor polynomial of graphs obtained by some binary graph operations.

2. Main Results

In this section, we discuss the equi-neighbor polynomial of graphs obtained by some binary graph operations.

If $H$ and $K$ are two graphs, then the join, $H \lor K$ is the graph with vertex set $V (H) \cup V (K)$ and the edge set $E (H) \cup E (K) \cup {u v : u \in V (H), v \in V (K)} .$

Theorem 1. If $H$ and $K$ are any two graphs with $h$ and $k$ vertices respectively, then the equi neighbor polynomial of the join of $H$ and $K$ is given by $N_{e} [H \lor K; x] = x^{k} N_{e} [H; x] + x^{h} N_{e} [K; x] + \sum_{i = 0}^{h - 1} (H, i) n (K, i + k - h) x^{i + k},$ where $n (H, i)$ denotes the number of vertices of $H$ with $i$ neighbors and $n (K, i + k - h)$ denotes the number of vertices of $K$ with $i + k - h$ neighbors.

Proof. Observe that from the definition of $H \lor K,$ each vertex of $K$ has $k$ more than the number of neighbors as in $H$ and each vertex $K$ has $h$ more than the number of neighbors as in $K .$ Therefore it is enough to consider the following three cases:

Case (i) Let $u, v \in V (H);$ $| N (u) | = | N (v) | = i$ in $H .$ Then $u$ has $(i + k)$ neighbors in $H \lor K,$ which are the $i$ neighbors in $H$ and the $k$ vertices in $K .$ The same is true for $v .$ Hence the pair $(u, v)$ has $(i + k)$ -equi neighbors in $H \lor K$ and there are $| N_{e} (H, i) |$ such pairs.
Case (ii) Let $u, v \in V (K);$ $| N (u) | = | N (v) | = i$ in $K .$ Then $u$ has $(i + h)$ neighbors in $H \lor K,$ which are the $i$ neighbors in $K$ and the $h$ vertices in $H .$ The same is true for $v .$ Hence the pair $(u, v)$ has $(i + h)$ -equi neighbors in $H \lor K$ and there are $| N_{e} (K, i) |$ such pairs.
Case (iii) Let $u \in V (H), v \in V (K);$ $| N (u) | = i$ in $H,$ $| N (v) | = i + k - h$ in $H .$ Then $u$ and $v$ have $(i + h)$ neighbors in $H \lor K .$ Hence the pair $(u, v)$ has $(i + k)$ -equi neighbors in $H \lor K$ and there are $n (H, i) n (K, i + k - h)$ such pairs. Thus we have,

$\begin{aligned} N_{e} [H \lor K; x] & = \sum_{i = 0}^{h - 1} | N_{e} (H, i) | x^{i + k} + \sum_{i = 0}^{k - 1} | N_{e} (K, i) | x^{i + h} \\ + \sum_{i = 0}^{h - 1} n (H, i) n (K, i + k - h) x^{i + k} \\ = x^{k} N_{e} [H; x] + x^{h} N_{e} [K; x] + \sum_{i = 0}^{h - 1} n (H, i) n (K, i + h - k) x^{i + k} . \end{aligned}$ This completes the proof.

Consider the graph $G (V, E)$ and let $w \notin V .$ Then the graph $G + w$ is a graph obtained from $G$ including the vertex $w$ in $G$ and joining it to all other vertices of $G .$

Corollary 1. $N_{e} [G + w; x] = x N_{e} [G; x] + n (G, n - 1) x^{n}$ , where $n (G, n - 1)$ represents the number of vertices of $G$ with $(n - 1)$ neighbors.

Proof. The result follows from the fact that $G + w$ is isomorphic to $G \lor K_{1},$ where $K_{1}$ is the complete graph on a single vertex with $V (K_{1}) = {w} .$

A Wheel graph $W_{n}, n > 3$ is obtained by taking the join of the cycle graph $C_{n - 1}$ and the complete graph $K_{1}$ .

Lemma 1.

For a cycle graph $C_{n},$ $N_{e} [C_{n}; x] = (\binom{n}{2}) x^{2}, n \geq 3.$

Corollary 2. If $W_{n}, n > 3$ is a wheel graph with $n$ vertices, then $\begin{aligned} N_{e} [W_{n}; x] = & {\begin{cases} (\binom{n - 1}{2}) x^{3}, & if n \neq 4, \\ 6 x^{3}, & if n = 4. \end{cases} \end{aligned}$

Proof. Observe that $W_{n}$ is isomorphic to $C_{n} - 1 \lor K_{1};$ where $C_{n} - 1$ is the cycle graph on $n$ vertices and $K_{1}$ is the complete graph on a single vertex. Therefore, using lemma 1 and Theorem 1, it follows that

Case (i) Let $n \neq 4$ . Then, $\begin{aligned} N_{e} [C_{n - 1} \lor K_{1}; x] & = x (\binom{n - 1}{2}) x^{2} + x \times 0 = (\binom{n - 1}{2}) x^{3} . \end{aligned}$
Case (ii) Let $n = 4$ . Then, $\begin{aligned} N_{e} [C_{n - 1} \lor K_{1}; x] & = x \times 3 x^{2} + x^{3} \times 0 + 3 \times 1 \times x^{3} = 6 x^{3} . \end{aligned}$

This completes the proof.

A Shell graph $S_{n},$ where $n \geq 3$ is obtained from the cycle graph $C_{n}$ by adding the edges corresponding to the $(n - 3)$ concurrent chords of the cycle.

Lemma 2. If $P_{n}$ is a path graph of length $n;$ $n \geq 2$ , we have $N_{e} [P_{n}; x] = x + (\binom{n - 2}{2}) x^{2}; n \geq 2.$

Corollary 3. For a shell graph $S_{n};$ $n \geq 3$ , we have $N_{e} [S_{n}; x] = {\begin{cases} (\binom{n - 3}{2}) x^{3} + x^{2}, & if n \neq 3, 4, \\ 3 x^{2}, & if n = 3, \\ x^{3} + x^{2}, & if n = 4. \end{cases}$

Proof. Note that $S_{n} = P_{n - 1} \lor K_{1}$ . Then the result follows from Lemma 2 and Theorem 1.

The corona of two graphs $K$ and $H$ is formed from one copy of $K$ and $| V (K) |$ copies of $H$ where the $i^{t h}$ vertex of $K$ is adjacent to every vertex in the $i^{t h}$ copy of $H$ [2]. It is denoted by $K \circ H .$

Theorem 2. If $K$ is a graph having $k$ vertices and $H$ is a graph having $h$ vertices, then the equi neighbor polynomial of corona of $K$ and $H$ is given by $\begin{aligned} N_{e} [K \circ H; x] & = x^{h} N_{e} [K; x] + k x N_{e} [H; x] + (\binom{k}{2}) \sum_{i = 0}^{h - 1} [n (H, i)]^{2} x^{i + 1} + n (K, 0) n (H, h - 1) x^{h}, \end{aligned}$ where $n (H, i)$ represents the number of vertices of $H$ with $i$ neighbors and $n (K, 0)$ represents the number of isolated vertices of $K .$

Proof. Observe that, from the definition of $K \circ H$ ,

each vertex of $K$ has $h$ more than the number of neighbors as in $K$ ,
each vertex in a copy of $H$ has one more than the number of neighbors as in $H$ and there are $k$ copies of $H$ .

Therefore it is enough to consider the following four cases;

Case (i) Let $u, v \in V (K);$ $| N (u) | = | N (v) | = i$ in $K .$ Then $u$ has $(i + h)$ neighbors in $K \circ H,$ which are the $i$ neighbors in $K$ and the $h$ vertices in a copy of $H$ corresponding to the vertex $u .$ $v$ also has $(i + h)$ neighbors in $K \circ H,$ which are the $i$ neighbors in $K$ and the $h$ vertices in the copy of $H$ corresponding to the vertex $v .$ Hence the pair $(u, v)$ has $(i + h)$ -equi neighbors in $K \circ H$ and there are $| N_{e} (K, i) |$ such pairs.
Case (ii) Let $u, v \in V (H_{j});$ where $H_{j}$ denotes the $j^{t h}$ copy of $H; j = 1, 2, \dots k;$ $| N (u) | = | N (v) | = i$ in $H_{j} .$ Then $u$ has $(i + 1)$ neighbors in $K \circ H,$ which are the $i$ neighbors in $H$ and the vertex in $K$ corresponding to $H_{j} .$ The same is true for $v .$ Hence the pair $(u, v)$ has $(i + 1)$ -equi neighbors in $K \circ H$ and there are $| N_{e} (H, i) |$ such pairs corresponding to the copy $H_{j}$ of $H .$ Note that there are $k$ such copies of $H .$
Case (iii) Let $u \in V (H_{j}),$ $v \in V (H_{k}),$ where $H_{j}$ anf $H_{k}$ denote the $j^{t h}$ and $k^{t h}$ copy of $H$ respectively; $j, k \in {1, 2, \dots, k};$ $j \neq k;$ $| N (u) | = | N (v) | = i$ in $H .$ Then the pair $(u, v)$ has $(i + 1)$ -equi neighbors in $K \circ H$ and there are $(\binom{k}{2}) [n (H, i)]^{2}$ such pairs.
Case (iv) Let $u \in V (K)$ and $v \in V (H_{j}),$ where $H_{j}$ denote the $j^{t h}$ copy of $H;$ $j \in {1, 2, \dots, k};$ $| N (u) | = 0$ in $K;$ $| N (v) | = h - 1$ in $H .$ Then $u$ and $v$ have $h$ neighbors in $K \circ H .$ Hence the pair $(u, v)$ has $h$ -equi neighbors in $K \circ H$ and there are $n (K, 0) n (H, h - 1)$ such pairs. Thus,

$\begin{aligned} N_{e} [K \circ H; x] & = \sum_{i = 0}^{k - 1} | N_{e} (K, i) | x^{i + h} + k \sum_{i = 0}^{h - 1} | N_{e} (H, i) | x^{i + 1} + (\binom{k}{2}) \sum_{i = 0}^{h - 1} [n (H, i)]^{2} x^{i + 1} + n (K, 0) n (H, h - 1) x^{h} \\ = x^{h} N_{e} [K; x] + k x N_{e} [H; x] + (\binom{k}{2}) \sum_{i = 0}^{h - 1} [n (H, i)]^{2} x^{i + 1} + n (K, 0) n (H, h - 1) x^{h} . \end{aligned}$ This completes the proof.

The graph $Q (m, n)$ $; m \geq 1, n > 1$ is obtained by identifying each vertex of the complete graph $K_{m}$ with a vertex of a unique $K_{n}$ where there are $m$ copies of $K_{n}$ [3].

Corollary 4. For $m \geq 1, n > 1,$ we have $N_{e} [Q (m, n); x] = {(\binom{m}{2}) (n - 1)^{2} + m (\binom{n - 1}{2})} x^{n - 1} + (\binom{m}{2}) x^{m + n - 2} .$

Proof. The result follows from the fact that $Q (m, n)$ and $K_{m} \circ K_{n - 1}$ are isomorphic.

The Cartesian product of two graphs $K$ and $H$ is the graph $K H$ with vertex set $V (K) \times V (H)$ and the vertices $(u, v)$ and $(x, y)$ are adjacent if and only if $u = x$ and $v y \in E (H)$ or $u x \in E (G)$ and $v = y .$

Theorem 3. If $K$ is a graph with vertex set $V (K) = {u_{1}, u_{2}, \dots, u_{k}}$ and $H$ is a graph with vertex set $V (H) = {v_{1}, v_{2}, \dots, v_{h}},$ then the equi neighbor polynomial of cartesian product of $K$ and $H$ is given by, $\begin{aligned} N_{e} [K H; x] & = N_{e} [K; x] \sum_{r = 1}^{h} x^{d_{r}^{1}} + N_{e} [H; x] \sum_{r = 1}^{k} x^{d_{r}} + 2 \sum_{(i, j) \in I \times I} | N_{e} (K, i) | | N_{e} (H, j) | x^{i + j} \\ + \sum_{m = 1}^{k + h - 2} {\sum_{i, j \in I; i \neq j} n (K, i) n (K, j) n (H, m - i) n (H, m - j) x^{m}}, \end{aligned}$ where $d_{r} = | N (u_{r}) |, r = 1, 2, \dots, k,$ $d_{r}^{1} = | N (v_{r}) |, r = 1, 2, \dots, h$ , $I = {0, 1, 2, \dots, k - 1},$ $n (K, i)$ and $n (H, i)$ represent the number of vertices in $K$ and $H$ respectively with $i$ neighbors.

Proof. Let the vertices of $K H$ be denoted by $u_{i} v_{j}$ where $i \in {1, 2, \dots, k}$ and $j \in {1, 2, \dots, h}$ . Observe that from the definition of $K H$ the number of neighbors of a vertex $u_{i} v_{j}$ in $K H$ is equal to the sum of the number of neighbors of $u_{i}$ in $K$ and the number of neighbors of $v_{j}$ in $H;$ $i \in {1, 2, \dots, k}$ , $j \in {1, 2, \dots, h}$ . Therefore it is enough to consider the following four cases;

Case (i) Consider the vertex pairs of $K H$ of the form $(u_{r} v_{s}, u_{r} v_{t}),$ $r \in {1, 2, \dots, k},$ $s, t \in {1, 2, \dots, h},$ $s \neq t;$ with $| N (u_{r}) | = d_{r}$ in $K$ and $| N (v_{s}) | = | N (v_{t}) | = i$ in $H .$ Then the pair $(u_{r} v_{s}, u_{r} v_{t})$ has $(i + d_{r})$ -equi neighbors in $K H$ and there are $| N_{e} (H, i) |$ such pairs, for each $r \in {1, 2, \dots, k} .$
Case (ii) Consider the vertex pairs of $K H$ of the form $(u_{s} v_{r}, u_{t} v_{r}),$ where $s, t \in {1, 2, \dots, k},$ $r \in {1, 2, \dots, h},$ $s \neq t,$ with $| N (u_{s}) | = | N (u_{t}) | = i$ in $K$ and $| N (v_{r}) | = d_{r}^{1}$ in $H .$ Then the pair $(u_{s} v_{r}, u_{t} v_{r})$ has $(i + d_{r}^{1})$ -equi neighbors in $K H$ and there are $| N_{e} (K, i) |$ such pairs, for each $r \in {1, 2, \dots, h} .$
Case (iii) Consider the vertex pairs of $K H$ of the form $(u_{s} v_{r}, u_{t} v_{l})$ , where $s, t \in {1, 2, \dots, k},$ $r, l \in {1, 2, \dots, h},$ $s \neq t,$ $r \neq l,$ with $| N (u_{s}) | = | N (u_{t}) | = i$ in $K$ and $| N (v_{r}) | = | N (v_{l}) | = j$ in $H .$ Then the pair $(u_{s} v_{r}, u_{t} v_{l})$ has $(i + j)$ -equi neighbors in $K H$ and there are $2 | N_{e} (K, i) | | N_{e} (H, j) |$ such pairs.
Case (iv) Consider the vertex pairs of $K H$ of the form $(u_{s} v_{r}, u_{t} v_{l})$ , $s, t \in {1, 2, \dots, k},$ $r, l \in {1, 2, \dots, h}$ with $| N (u_{s}) | = i,$ $| N (u_{t}) | = j$ in $K,$ where $i \neq j .$ Then the pair $(u_{s} v_{r}, u_{t} v_{l})$ has $m$ -equi neighbors in $K H$ and there are $n (K, i) n (K, j) n (H, m - i) n (H, m - j)$ such pairs for each $m \in {1, 2, \dots, h + k - 2} .$ Thus,

$\begin{aligned} N_{e} [K H; x] & = \sum_{i = 0}^{h - 1} | N_{e} (H, i) | x^{i} \times \sum_{r = 1}^{k} x^{d_{r}} + \sum_{i = 0}^{k - 1} | N_{e} (K, i) | x^{i} \times \sum_{r = 1}^{h} x^{d_{r}^{1}} + \sum_{(i, j) \in I \times I} 2 | N_{e} (K, i) | | N_{e} (H, j) | x^{i + j} \\ + \sum_{m = 1}^{k + h - 2} {\sum_{i, j \in I; i \neq j} n (K, i) n (K, j) n (H, m - i) n (H, m - j) x^{m}} \\ = N_{e} [K; x] \sum_{r = 1}^{h} x^{d_{r}^{1}} + N_{e} [H; x] \sum_{r = 1}^{k} x^{d_{r}} + 2 \sum_{(i, j) \in I \times I} | N_{e} (H, i) | | N_{e} (H, j) | x^{i + j} \\ + \sum_{m = 1}^{k + h - 2} {\sum_{i, j \in I; i \neq j} n (K, i) n (K, j) n (H, m - i) n (H, m - j) x^{m}} . \end{aligned}$ This completes the proof.

A Ladder graph $L_{n}; n \geq 2$ is obtained as the cartesian product of two paths one of which has only one edge.

Corollary 5. For a Ladder graph $L_{n},$ we have $N_{e} [L_{n}; x] = (n - 2) (2 n - 5) x^{3} + 6 x^{2}; n \geq 2.$

Proof. Since $L_{n}$ is isomorphic to $P_{n} P_{2}$ , $N [L_{n}; x] = N [P_{n} P_{2}; x]$ . Note that $N_{e} [P_{n}; x] = (\binom{n - 2}{2}) x^{2} + x$ . So we obtain, $\begin{aligned} N_{e} [L_{n}; x] & = x [2 x + (n - 2) x^{2}] + [x + (\binom{n - 2}{2}) x^{2}] 2 x + 2 [x^{2} + (\binom{n - 2}{2}) x^{3}] \\ = (n - 2) (2 n - 5) x^{3} + 6 x^{2} . \end{aligned}$ This completes the proof.

A Circular ladder graph $C L_{n}; n \geq 3$ is obtained as the cartesian product of the cycle graph $C_{n}$ and the path $P_{2}$ .

Corollary 6. For a Circular ladder graph $C L_{n},$ we have $N_{e} [C L_{n}; x] = n (2 n - 1) x^{3}; n \geq 3.$

Proof. Using the Lemma 1, Theorem 3 and using the fact that $C L_{n}$ is isomorphic to $C_{n} P_{2}$ , it follows that, $\begin{aligned} N_{e} [C L_{n}; x] & = x \times n x^{2} + (\binom{n}{2}) x^{2} \times 2 x + 2 (\binom{n}{2}) \times 1 \times x^{3} \\ = n (2 n - 1) x^{3} . \end{aligned}$ This completes the proof.

A $m -$ book graph is obtained as the cartesian product of the star graph $K_{1, m}$ and the path graph $P_{2} .$

Corollary 7. If $B_{m}$ is a $m -$ book graph, then we have $\begin{aligned} N_{e} [B_{m}; x] = & {\begin{cases} x^{m + 1} + m (2 m - 1) x^{2}, & if m > 1, \\ 6 x^{2}, & if m = 1. \end{cases} \end{aligned}$

Proof. Since $B_{m}$ is isomorphic to $K_{1, m} P_{2},$ $N_{e} [B_{m}; x] = N_{e} [K_{1, m} P_{2}; x]$ . Note that $N_{e} [K_{1, m}; x] = {\begin{cases} (\binom{m}{2}) x, & m \geq 1, \\ x, & m = 1. \end{cases} .$ Thus we obtain,

Case (i) Let $m > 1$ . Then, $\begin{aligned} N_{e} [K_{1, m} P_{2}; x] & = x [x^{m} + m x] + (\binom{m}{2}) x \times 2 x + 2 (\binom{m}{2}) \times 1 \times x^{2} = x^{m + 1} + m (2 m - 1) x^{2} . \end{aligned}$
Case (ii) Let $m = 1$ . Then, $\begin{aligned} N_{e} [K_{1, m} P_{2}; x] & = x \times 2 x + x \times 2 x + 2 \times 1 \times 1 \times x^{2} = 6 x^{2} . \end{aligned}$

This completes the proof.

A rooted graph is a graph in which one vertex is distinguished as a root. The Rooted product of a graph $G$ and a rooted graph $H$ is obtained as follows;

Take $| V (G) |$ copies of $H$ and for each vertex $v_{i}$ of $G,$ identify $v_{i}$ with the root vertex of the $i^{t h}$ copy of $H$ [4].

Theorem 4. Let $G$ be a graph with $n$ vertices. Let $H$ be a rooted graph with $m$ vertices, having a root vertex $v_{1}$ with degree $d$ . If $G'$ is the rooted product of $G$ and $H$ , then,

$\begin{aligned} N_{e} [G'; x] & = x^{d} N_{e} [G; x] + n^{2} N_{e} [H; x] + (\binom{n}{2}) \sum_{i = 0, i \neq d}^{m - 1} n (H, i) x^{i} + \sum_{i = 0}^{n - 1} n (G, i) n (H, i + d) x^{i} \\ - \frac{(n + 1)}{2} n (H, d) + n (G, 0) n (H, d) + \frac{(n + 1)}{2} - n (G, 0) n x^{d}, \end{aligned}$ where $n (G, i)$ and $n (H, i)$ represent the number of vertices of $G$ and $H$ respectively with $i$ neighbors.

Proof. Let $V (G) = {u_{1}, u_{2}, \dots, u_{n}}$ and let $V (H) = {v_{1}, v_{2}, \dots, v_{m}}$ where $v_{1}$ is the root vertex. Then a vertex of $G^{'}$ can be represented by $u_{r} v_{s}$ where $r \in {1, 2, \dots, n}$ and $s \in {1, 2, \dots, m}$ . Observe that, from the definition of the rooted product of $G$ and $H$ ,

the number of neighbors of vertices of $G'$ of the form $u_{r} v_{1},$ $r \in {1, 2, \dots, n}$ is equal to the sum of the number of neighbors of $u_{r}$ in $G$ and the number of neighbors of $v_{1}$ in $H .$
the number of neighbors of vertices of $G'$ of the form $u_{r} v_{s},$ $r \in {1, 2, \dots, n}$ ; $s \in {2, 3, \dots, m}$ is equal to the number of neighbors of $v_{s}$ in $H .$

Therefore it is enough to consider the following seven cases;

Case (i) Consider the vertex pairs of $G'$ of the form $(u_{r} v_{1}, u_{s} v_{1}),$ where $r, s \in {1, 2, \dots, n};$ $r \neq s$ ; with $| N (u_{r}) | = | N (u_{s}) | = i$ in $G .$ Then $u_{r} v_{1}$ has $(i + d)$ neighbors in $G' .$ The same is true for $u_{s} v_{1} .$ Hence the pair $(u_{r} v_{1}, u_{s} v_{1})$ has $(i + d)$ -equi neighbors in $G'$ and there are $| N_{e} (G, i) |$ such pairs.
Case (ii) Consider the vertex pairs of $G'$ of the form $(u_{r} v_{s}, u_{r} v_{t})$ , where $r \in {1, 2, \dots, n}$ , $s, t \in {2, 3, \dots, m}$ , $s \neq t,$ with $| N (v_{s}) | = | N (v_{t}) | = i \neq d$ in $H .$ Then the pair $(u_{r} v_{s}, u_{r} v_{t})$ has $i$ -equi neighbors in $G'$ and there are $| N_{e} (H, i) |$ such pairs, corresponding to each $r \in {1, 2, \dots, n} .$
Case (iii) Consider the vertex pairs of $G'$ of the form $(u_{r} v_{s}, u_{r} v_{t})$ , where $r \in {1, 2, \dots, n}$ , $s, t \in {2, 3, \dots, m}$ , $s \neq t$ , with $| N (v_{s}) | = | N (v_{t}) | = d$ in $H .$ Then the pair $(u_{r} v_{s}, u_{r} v_{t})$ has $d$ -equi neighbors in $G'$ and there are $| N_{e} (H, d) | - n (H, d) + 1$ such pairs, corresponding to each $r \in {1, 2, \dots, n} .$
Case (iv) Consider the vertex pairs of $G'$ of the form $(u_{r} v_{1}, u_{r} v_{s})$ , where $r \in {1, 2, \dots, n}$ , $s \in {2, 3, \dots, m}$ , with $| N (u_{r}) | = i$ in $G$ and $| N (v_{s}) | = i + d$ in $H .$
Subcase (i) Let $i = 0.$ Then the pair $(u_{r} v_{1}, u_{r} v_{s})$ has $d$ -equi neighbors in $G'$ and there are $n (G, 0) {n (H, d) - 1}$ such pairs.
Subcase (ii) Let $i \neq 0.$ Then the pair $(u_{r} v_{1}, u_{r} v_{s})$ has $(i + d)$ -equi neighbors in $G'$ and there are $n (G, i) n (H, i + d)$ such pairs.
Case (v) Consider the vertex pairs of $G'$ of the form $(u_{r} v_{1}, u_{s} v_{t})$ , where $r, s \in {1, 2, \dots, n}$ , $t \in {2, 3, \dots, m}$ , $r \neq s$ , with $| N (u_{r}) | = i$ in $G$ and $| N (v_{t}) | = i + d$ in $H .$
Subcase (i) Let $i = 0.$ Then the pair $(u_{r} v_{1}, u_{s} v_{t})$ has $d$ -equi neighbors in $G'$ and there are $(n - 1) n (G, 0) {n (H, d) - 1}$ such pairs.
Subcase (ii) Let $i \neq 0.$ Then the pair $(u_{r} v_{1}, u_{s} v_{t})$ has $(i + d)$ -equi neighbors in $G'$ and there are $(n - 1) n (G, i) n (H, i + d)$ such pairs.
Case (vi) Consider the vertex pairs of $G'$ of the form $(u_{r} v_{s}, u_{t} v_{l})$ , where $r, t \in {1, 2, \dots, n}$ , $s, l \in {2, 3, \dots, m}$ , $r \neq t$ , with $| N (v_{s}) | = | N (v_{l}) | = i \neq d$ in $H .$ Then the pair $(u_{r} v_{s}, u_{t} v_{l})$ has $i$ -equi neighbors in $G'$ and there are $(\binom{n}{2}) [2 | N_{e} (H, i) | + n (H, i)]$ such pairs.
Case (vii) Consider the vertex pairs of $G'$ of the form $(u_{r} v_{s}, u_{t} v_{l})$ , where $r, t \in {1, 2, \dots, n}$ , $s, l \in {2, 3, \dots, m}$ , $r \neq t,$ with $| N (v_{s}) | = | N (v_{l}) | = d$ in $H .$ Then the pair $(u_{r} v_{s}, u_{t} v_{l})$ has $d$ -equi neighbors in $G'$ and there are $(\binom{n}{2}) [2 | N_{e} (H, d) | - n (H, d) + 1]$ such pairs. Thus,

$\begin{aligned} N_{e} [G'; x] & = x^{d} N_{e} [G; x] + n \sum_{i = 0; i \neq d}^{m - 1} | N_{e} (H, i) | x^{i} + n {| N_{e} (H, d) | - n (H, d) + 1} x^{d} \\ + n (G, 0) {n (H, d) - 1} x^{d} + \sum_{i = 1}^{n - 1} n (G, i) n (H, i + d) x^{i + d} \\ + (n - 1) n (G, 0) {n (H, d) - 1} x^{d} + (n - 1) \sum_{i = 1}^{n - 1} n (G, i) n (H, i + d) x^{i + d} \\ + (\binom{n}{2}) \sum_{i = 0; i \neq d}^{m - 1} {2 | N_{e} (H, i) | + n (H, i)} x^{i} + (\binom{n}{2}) {2 | N_{e} (H, d) | - n (H, d) + 1} x^{d} \\ = x^{d} N_{e} [G; x] + n^{2} N_{e} [H; x] + (\binom{n}{2}) \sum_{i = 0, i \neq d}^{m - 1} n (H, i) x^{i} + \sum_{i = 1}^{n - 1} n (G, i) n (H, i + d) x^{i} \\ - \frac{(n + 1)}{2} n (H, d) + n (G, 0) n (H, d) + \frac{(n + 1)}{2} - n (G, 0)} n x^{d} . \end{aligned}$ This completes the proof.

The Tensor product of two graphs $K$ and $H$ is the graph $K \times H$ with vertex set $V (K) \times V (H)$ and the vertices $(u, v)$ and $(x, y)$ are adjacent if and only if $u x \in E (K)$ and $v y \in E (H) .$

Theorem 5. If $K$ is a graph with vertex set $V (K) = {u_{1}, u_{2}, \dots, u_{k}}$ and $H$ is a graph with vertex set $V (H) = {v_{1}, v_{2}, \dots, v_{h}},$ then the equi neighbor polynomial of Tensor product of $K$ and $H$ is given by $\begin{aligned} N_{e} [K \times H; x] = & \sum_{r = 1}^{k} N_{e} [K; x^{d_{r}^{1}}] + \sum_{r = 1}^{h} N_{e} [H; x^{d_{r}}] + 2 \sum_{(i, j) \in I_{1} \times I_{2}} | N_{e} (H, i) | | N_{e} (H, j) | x^{i j} \\ + \sum_{i, j \in I_{1}; i \neq j} {\sum_{(m, n) \in I_{2} \times I_{2}; i m = j n} n (K, i) n (K, j) n (H, m) n (H, n) x^{i m}} \\ + n (K, 0) \sum_{m, n \in I_{2}; m \neq n} n (H, m) n (H, n), \end{aligned}$ where $I_{1} = {0, 1, 2, \dots, k - 1}$ , $I_{2} = {0, 1, 2, \dots, h - 1},$ $d_{r} = | N (u_{r}) |, r \in {1, 2, \dots, k}$ , $d_{r}^{1} = | N (v_{r}) |,$ $r \in {1, 2, \dots, h},$ $n (K, i)$ and $n (H, i)$ represent the number of vertices in $K$ and $H$ with $i -$ neighbors respectively.

Proof. Let the vertices of $K \times H$ be denoted by $u_{i} v_{j},$ where $i \in {1, 2, \dots, k}$ and $j \in {1, 2, \dots, h} .$ Observe that from the definition of $K \times H$ the number of neighbors of a vertex $u_{i} v_{j}$ in $K \times H$ is equal to the product of the number of neighbors of $u_{i}$ in $K$ and the number of neighbors of $v_{j}$ in $H;$ $i \in {1, 2, \dots, k}$ , $j \in {1, 2, \dots, h}$ . Therefore it is enough to consider the following five cases;

Case (i) Consider the vertex pairs of $K \times H$ of the form $(u_{r} v_{s}, u_{r} v_{t}),$ where $r \in {1, 2, \dots, k},$ $s, t \in {1, 2, \dots, h},$ $s \neq t,$ with $| N (u_{r}) | = d_{r}$ in $K$ and $| N (v_{s}) | = | N (v_{t}) | = i$ in $H .$ Then the pair $(u_{r} v_{s}, u_{r} v_{t})$ has $(i \times d_{r})$ – equi neighbors in $K \times H$ and there are $| N_{e} (H, i) |$ such pairs, corresponding to each $r \in {1, 2, \dots, k} .$
Case (ii) Consider the vertex pairs of $K \times H$ of the form $(u_{s} v_{r}, u_{t} v_{r})$ where $s, t \in {1, 2, \dots, k},$ $r \in {1, 2, \dots, h},$ $s \neq t,$ with $| N (u_{s}) | = | N (u_{t}) | = i$ in $K$ and $| N (v_{r}) | = d_{r}^{1}$ in $H .$ Then the pair $(u_{s} v_{r}, u_{t} v_{r})$ has $(i \times d_{r}^{1})$ – equi neighbors in $K \times H$ and there are $| N_{e} (K, i) |$ such pairs, corresponding to each $r \in {1, 2, \dots, h} .$
Case (iii) Consider the vertex pairs of $K \times H$ of the form $(u_{s} v_{r}, u_{t} v_{l}),$ where $s, t \in {1, 2, \dots, k},$ $r, l \in {1, 2, \dots, h},$ $s \neq t,$ $r \neq l,$ with $| N (u_{s}) | = | N (u_{t}) | = i$ in $K$ and $| N (v_{r}) | = | N (v_{l}) | = j$ in $H .$ Then the pair $(u_{s} v_{r}, u_{t} v_{l})$ has $(i \times j)$ – equi neighbors in $K \times H$ and there are $2 | N_{e} (K, i) | | N_{e} (H, j) |$ such pairs.
Case (iv) Consider the vertex pairs of $K \times H$ of the form $(u_{s} v_{r}, u_{t} v_{l}),$ where $s, t \in {1, 2, \dots, h},$ $r, l \in {1, 2, \dots, k}$ with $| N (u_{s}) | = i,$ $| N (u_{t}) | = j$ in $K,$ where $i \neq j,$ and $| N (v_{r}) | = m,$ $| N (v_{l}) | = n$ satisfying $i m = j n .$ Then for any set of values for $i$ and $j$ satisfying $i \neq j,$ we get $\sum_{(m, n) \in I_{2} \times I_{2}; i m = j n} n (K, i) n (K, j) n (H, m) n (H, n)$ pairs of vertices with $i m$ -equi neighbors.
Case (v) Consider the vertex pairs of $K \times H$ of the form $(u_{r} v_{s}, u_{r} v_{t}),$ where $r \in {1, 2, \dots, k},$ $s, t \in {1, 2, \dots, h},$ with $| N (u_{r}) | = 0,$ $| N (v_{s}) | = m,$ $| N (v_{t}) | = n,$ $m \neq n .$ Then the pair $(u_{r} v_{s}, u_{r} v_{t})$ has zero-equi neighbors and there are $n (K, 0) \sum_{m, n \in I_{2}; m \neq n} n (H, m) n (H, n)$ such pairs.

This completes the proof.

3. Conclusion

In this paper, we discussed the equi neighbor polynomial of graphs obtained by some graph binary operations. The paper has provided explicit formulae to find the equi neighbor polynomial of some well-known graph products such as join, corona, cartesian product, rooted product, and tensor product of two graphs in terms of the equi neighbor polynomial of the parent graphs.

Acknowledgments

We thank the anonymous referees for their helpful comments.

References:

Dhanya, P., and Kumar, A. V., 2004. The number of equi neighbor sets graphs. Advances and Applications in Discrete Mathematics
Frucht, R., and Harary, F., 1970. On the corona of two graphs. Aequationes Mathematicae, 4, pp.322-325.
Shyama, M. P., and Anilkumar, V., 2016. On the roots of Hosoya polynomials. Journal of Discrete Mathematical Sciences and Cryptography, 19, pp.199-219.
Godsil, C. D., and McKay, B. D., 1978. A new graph product and its spectrum. Bulletin of Australian Mathematical Society, 18, pp.21-28.

[1] Dhanya, P., and Kumar, A. V., 2004. The number of equi neighbor sets graphs. Advances and Applications in Discrete Mathematics

[2] Frucht, R., and Harary, F., 1970. On the corona of two graphs. Aequationes Mathematicae, 4, pp.322-325.

[3] Shyama, M. P., and Anilkumar, V., 2016. On the roots of Hosoya polynomials. Journal of Discrete Mathematical Sciences and Cryptography, 19, pp.199-219.

[4] Godsil, C. D., and McKay, B. D., 1978. A new graph product and its spectrum. Bulletin of Australian Mathematical Society, 18, pp.21-28.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

Equi Neighbor Polynomial of Some Binary Graph Operations

Abstract

1. Introduction

2. Main Results

3. Conclusion

Acknowledgments

References:

Information

Guidelines

CP Initiatives

Follow CP