Menu
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.
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 \ \text{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.
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 \vee K\) is the graph with vertex set \(V(H) \cup V(K)\) and the edge set \(E(H)\cup E(K) \cup \{uv: 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 \vee K;x]=x^k N_{e}[H;x]+x^h N_{e}[K;x]+\displaystyle \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 \vee 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:
Then \(u\) has \((i+k)\) neighbors in \(H \vee 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 \vee K\) and there are \(|N_{e}(H,i)|\) such pairs.
Then \(u\) has \((i+h)\) neighbors in \(H \vee 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 \vee K\) and there are \(|N_{e}(K,i)|\) such pairs.
Then \(u\) and \(v\) have \((i+h)\) neighbors in \(H \vee K.\) Hence the pair \((u, v)\) has \((i+k)\)-equi neighbors in \(H \vee K\) and there are \(n(H, i) n(K, i+k-h)\) such pairs.
Thus we have,
\[\begin{aligned} N_e[H \vee K;x]&=\sum_{i=0}^{h-1}|N_e(H,i)|x^{i+k}+\sum_{i=0}^{k-1}\left| N_e(K,i)\right|x^{i+h}\\ &\quad+\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]=xN_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 \vee K_1,\) where \(K_1\) is the complete graph on a single vertex with \(V(K_1)=\lbrace w \rbrace.\) ◻
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]= {n \choose 2}x^2 , n\ge3.\]
Corollary 2. If \(W_n, n>3\) is a wheel graph with \(n\) vertices, then \[\begin{aligned} N_e[W_n;x]=& \begin{cases} {n-1 \choose 2}x^3, &\text{if} \ \ n\neq 4,\\ 6x^3, &\text{if}\ \ n=4.\end{cases} \end{aligned}\]
Proof. Observe that \(W_n\) is isomorphic to \(C_n-1 \vee 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
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+{n-2 \choose 2}x^2; n \geq 2.\]
Corollary 3. For a shell graph \(S_n;\) \(n\ge 3\), we have \[N_e[S_n;x]=\begin{cases} {n-3 \choose 2}x^3+x^2,&\text{if} \ n \neq 3,4,\\ 3x^2, & \text{if} \ n=3,\\ x^3+x^2,&\text{if} \ n=4.\end{cases}\]
The corona of two graphs \(K\) and \(H\) is formed from one copy of \(K\) and \(|V(K)|\) copies of \(H\) where the \(i^{th}\) vertex of \(K\) is adjacent to every vertex in the \(i^{th}\) 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]+kxN_e[H;x]+{k \choose 2}\sum_{i=0}^{h-1}[n(H,i)]^2x^{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;
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.
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.\)
Then the pair \((u, v)\) has \((i+1)\)-equi neighbors in \(K \circ H\) and there are \({k \choose 2}[n(H,i)]^2\)such pairs.
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}\left| N_e(H,i)\right|x^{i+1} +{k \choose 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]+kxN_e[H;x]+{k \choose 2}\sum_{i=0}^{h-1}[n(H,i)]^2x^{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]=\{{m \choose 2}(n-1)^{2}+m{n-1 \choose 2}\}x^{n-1}+{m \choose 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\square 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 \(vy \in E(H)\) or \(ux \in E(G)\) and \(v=y.\)
Theorem 3. If \(K\) is a graph with vertex set \(V(K)=\{u_1,u_2,…,u_k\}\) and \(H\) is a graph with vertex set \(V(H)=\{v_1,v_2,…,v_h\},\) then the equi neighbor polynomial of cartesian product of \(K\) and \(H\) is given by, \[\begin{aligned} N_e[K\square 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}\\ & \quad + \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, …, k,\) \(d_r^{1}=|N(v_r)|, r=1, 2, …, h\), \(I=\{0, 1, 2,…, 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\square H\) be denoted by \(u_iv_j\) where \(i\in \lbrace1,2,\ldots,k\rbrace\) and \(j\in \lbrace1,2,\ldots,h\rbrace\). Observe that from the definition of \(K\square H\) the number of neighbors of a vertex \(u_iv_j\) in \(K\square 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 \lbrace1,2,\ldots,k\rbrace\), \(j\in \lbrace1,2,\ldots,h\rbrace\). Therefore it is enough to consider the following four cases;
\[\begin{aligned} N_e[K \square 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}\\ &\quad + \sum_{m=1}^{k+h-2}\left\{\sum_{i, j \in I;i \neq j}n(K, i)n(K, j)n(H, m-i)n(H, m-j)x^{m}\right\} \\ &=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}\\ & \quad + \sum_{m=1}^{k+h-2}\left\{\sum_{i, j \in I;i \neq j}n(K, i)n(K, j)n(H, m-i)n(H, m-j)x^{m}\right\}. \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)(2n-5)x^3+6x^{2}; n \geq 2.\]
Proof. Since \(L_n\) is isomorphic to \(P_n \square P_2\), \(N[L_n;x]=N[P_n \square P_2;x]\). Note that \(N_e[P_n;x]={n-2 \choose 2}x^{2}+x\). So we obtain, \[\begin{aligned} N_e[L_n;x]&=x\big[2x+(n-2)x^{2}\big]+\Big[x+{n-2 \choose 2}x^{2}\Big] 2x+2\Big[x^{2}+{n-2 \choose 2}x^{3}\Big]\\ &=(n-2)(2n-5)x^3+6x^{2}. \end{aligned}\] This completes the proof. ◻
A Circular ladder graph \(CL_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 \(CL_n,\) we have \[N_e[CL_n;x]=n(2n-1)x^3;n \geq 3.\]
Proof. Using the Lemma 1, Theorem 3 and using the fact that \(CL_n\) is isomorphic to \(C_n \square P_2\), it follows that, \[\begin{aligned} N_e[CL_n;x]&=x \times nx^{2}+{n \choose 2}x^{2} \times 2x+2{n \choose 2} \times 1 \times x^{3}\\ &=n(2n-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(2m-1)x^2, &\text{if} \ \ m> 1,\\ 6x^2, &\text{if}\ \ m=1.\end{cases} \end{aligned}\]
Proof. Since \(B_m\) is isomorphic to \(K_{1, m} \square P_2,\) \(N_e[B_m;x]=N_e[K_{1, m} \square P_2; x]\). Note that \[N_{e}[K_{1,m};x]= \begin {cases}{m \choose 2} x, &\ m\geq 1, \\ x, &\ m=1. \end{cases}.\] Thus we obtain,
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^{th}\) 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\prime\) is the rooted product of \(G\) and \(H\), then,
\[\begin{aligned} N_e[G\prime;x]&=x^{d}N_e[G;x]+n^{2}N_e[H;x] +{n \choose 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} \\ &\quad-\frac{(n+1)}{2}n(H,d)+ n(G, 0)n(H,d)+\frac{(n+1)}{2} – n(G,0)nx^{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)=\lbrace u_1,u_2,\ldots, u_n\rbrace\) and let \(V(H)=\lbrace v_1,v_2,\ldots,v_m \rbrace\) where \(v_1\) is the root vertex. Then a vertex of \(G'\) can be represented by \(u_rv_s\) where \(r\in\{1,2, \ldots,n\}\) and \(s\in\{1,2,\ldots, m \}\). Observe that, from the definition of the rooted product of \(G\) and \(H\),
the number of neighbors of vertices of \(G \prime\) of the form \(u_rv_1,\) \(r\in\{1,2, \ldots,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 \prime\) of the form \(u_rv_s,\) \(r\in\{1,2, \ldots,n\}\); \(s\in\{2,3, \ldots,m\}\) is equal to the number of neighbors of \(v_s\) in \(H.\)
Therefore it is enough to consider the following seven cases;
\[\begin{aligned} N_e[G \prime;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} \\ &\quad +n(G, 0)\{n(H,d)-1\}x^{d}+ \sum_{i=1}^{n-1}n(G,i)n(H,i+d)x^{i+d}\\ &\quad+ (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}\\ &\quad+{n \choose 2} \sum_{i=0; i \neq d}^{m-1} \{2|N_e(H,i)|+n(H,i)\} x^{i} + {n \choose 2}\{2|N_e(H,d)|-n(H,d)+1\} x^{d} \\ &=x^{d}N_e[G;x]+n^{2}N_e[H;x] +{n \choose 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}\\ &\quad-\frac{(n+1)}{2}n(H,d) + n(G, 0)n(H,d)+\frac{(n+1)}{2} – n(G,0)\}nx^{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 \(ux \in E(K)\) and \(vy\in E(H).\)
Theorem 5. If \(K\) is a graph with vertex set \(V(K)=\{u_1,u_2,…,u_k\}\) and \(H\) is a graph with vertex set \(V(H)=\{v_1,v_2,…,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^{ij}\\ & +\sum_{i, j \in I_1;i \neq j}\left\{ \sum_{( m, n) \in I_2 \times I_2;im=jn} n(K, i)n(K, j)n(H, m)n(H, n)x^{im}\right\} \\&+ 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,…, k-1 \}\), \(I_2=\{0, 1, 2,…, h-1 \},\) \(d_r=|N(u_r)|,r \in \{1, 2, …,k\}\), \(d_r^{1}=|N(v_r)|,\) \(r \in \{1, 2, …, 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_iv_j,\) where \(i\in \lbrace1,2,\ldots,k\rbrace\) and \(j\in \lbrace1,2,\ldots,h\rbrace.\) Observe that from the definition of \(K\times H\) the number of neighbors of a vertex \(u_iv_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 \lbrace1,2,\ldots,k\rbrace\), \(j\in \lbrace1,2,\ldots,h\rbrace\). Therefore it is enough to consider the following five cases;
This completes the proof. ◻
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.
We thank the anonymous referees for their helpful comments.