EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 15, No. 1, 2022, 64-81 ISSN 1307-5543 – ejpam.com Published by New York Business Global On the Independent Neighborhood Polynomial of the Rooted Product of Two Trees Normalah S. Abdulcarim1,∗, Susan C. Dagondon2 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. Let G be a connected graph. We say that a given graph is a tree if every pair of vertices is connected by a unique path. The rooted product of two trees is relevant to tree, as the obtained product is another tree. In this paper, we establish the independent neighborhood sets of a tree and obtain its corresponding independent neighborhood polynomial. Furthermore, the independent neighborhood polynomial of the rooted product of two trees were determine using their independent neighborhood sets. 2020 Mathematics Subject Classifications: 05C05, 05C76, 05C31 Key Words and Phrases: Rooted Graph, Rooted Product of Graphs, Independent Neighbor- hood Polynomial 1. Introduction 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 end vertices 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 (G) is the set N(v) = {w : w ∈ V (G) 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 end vertices is a pendant vertex. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v15i1.4220 Email addresses: normalah.abdulcarim@msumain.edu.ph (N. S. Abdulcarim), susan.dagondon@g.msuiit.edu.ph (S. C. Dagondon) http://www.ejpam.com 64 © 2022 EJPAM All rights reserved. N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 65 A path is a nonempty graph P = (V (P ), E(P )) of the form V (P ) = {v1, · · · , vm}, E(P ) = {v1v2, v2v3, · · · , vm−1vm}, where the vi are all distinct. If E = {v1v2, v2v3, · · · , vm−1vm, vmv1}, then the graph is called a cycle. In this study, we consider the graph polynomial. Some familiar examples include chromatic polynomial by George David Birkhoff [1], matching polynomial by Farrel [4], independence polynomial by Gutman and Harary [7], and by Levit and Mandrescu [10]. Recently, another type of graph polynomial, the neighborhood polynomial were studied by some researchers. Some of these are the articles “Neighborhood Polynomial of Graphs” by J. Brown and R. Nowakowski [9] and “On the Independent Neighborhood Polynomial of Graphs” by K.B. Murthy and Puttaswamy[11]. The main interest of this study is to establish results on the independent neighborhood polynomial of tree and the rooted product of two trees. 2. Preliminaries This section presents some basic concepts in graph theory and known results needed in this study. Definition 1. [2] The open neighborhood of a vertex x, denoted byN(x), is a set containing all vertices y which are adjacent to x, that is, N(x) = {y ∈ V (G) : xy ∈ E(G)}. In case N(x) is a singleton, x is an end-vertex. The closed neighborhood of a vertex x of G is the set N [x] = N(x) ∪ {x}. Definition 2. [11] A set S of vertices in a graph G is a neighborhood set if G = ⋃ u∈S ⟨N [u]⟩ where ⟨N [u]⟩ is the subgraph of G induced by u and all the vertices adjacent to u. The neighborhood number of G is the minimum cardinality of neighborhood sets, denoted by ηi(G). Example 1. Consider the graph H in Figure 1. v1 v2 v3 v4 Figure 1: A graph H N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 66 The neighborhood sets of H are {v1, v3}, {v2}, {v4}, {v1, v2}, {v2, v3}, {v2, v4}{v1, v4}, {v3, v4}, {v1, v2, v3}, {v1, v2, v4}, {v1, v3, v4}, {v2, v3, v4} and {v1, v2, v3, v4}. Here, ηi(H) = 1. Definition 3. [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 4. [11] Let G = (V (G), E(G)) be a graph with m vertices. Then the indepen- dent neighborhood polynomial of G of order m is Ni(G, x) = m∑ j=ηi(G) ni(G, j)xj , where ni(G, j) is the number of independent neighborhood set ofG 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 2. In Figure 1 above, the only independent neighborhood sets ofH are {v2}, {v4} and {v1, v3}. Therefore, the independent neighborhood polynomial of H is Ni(H,x) = 2x+ x2. Definition 5. [6]A graph is acyclic if it has no cycles. A graph is said to be connected if every pair of vertices are joined by a path. A graph that is not connected is called disconnected. A tree is a connected acyclic graph. Theorem 1. [8] For a simple graph G (with n vertices, n ≥ 1), the following statements are equivalent (i) G is a tree (ii) G is connected and has no cycles (iii) G is connected and has n− 1 edges (iv) G has n− 1 edges and has no cycles (v) Every two vertices of G are joined by a unique path Corollary 1. [8] Every nontrivial tree has at least two end vertices. Definition 6. [3] Let G be a graph. The distance between two vertices x and y in a graph G, denoted by dG(x, y) or simply d(x, y), is the length of the shortest path joining them, otherwise, d(x, y) = ∞. Remark 1. [6] In a connected graph G, the distance is a metric, that is, for all x, y, z ∈ V (G), N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 67 (i) d(x, y) ≥ 0, with d(x, y) = 0 if and only if x = y. (ii) d(x, y) = d(y, x) (iii) d(x, y) + d(y, z) ≥ d(x, z). Remark 2. For any tree T , d(x, y) + d(y, z) = d(x, z). Example 3. Consider the tree below u a v b G Figure 2: A tree In Figure 2, the distance between vertices u and v is d(u, v) = 4 and the distance between a and b is d(a, b) = 3. Definition 7. [6] A graph in which one vertex is fixed as a root vertex to distinguish it from the other is called a rooted graph. The rooted product of a graph G and a rooted graph H is defined as follows: Let V (G) = {g1, g2, · · · , gn}, V (H) = {h1, h2, · · · , hm} and that root vertex of H is h1, we define G • H = (V,E) where V = {(gi, hj) : 1 ≤ i ≤ n, 1 ≤ j ≤ m} and E = {(gi, h1)(gk, h1) : gigk ∈ E(G)} ∪ n⋃ i=1 {(gi, hj)(gi, hk) : hjhk ∈ E(H)}. Example 4. Let G be a graph and H be a rooted graph with h1 as its root vertex. Then the rooted product of G and H is shown in Figure 3. N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 68 g1 g2 g4 g3 G h1 h2 h3 h4 h5 H (g1, h1) (g1, h2) (g1, h3) (g1, h4) (g1, h5) (g2, h1) (g2, h2) (g2, h3) (g2, h4) (g2, h5) (g4, h1) (g4, h2) (g4, h3) (g4, h4) (g4, h5) (g3, h1) (g3, h2) (g3, h3) (g3, h4) (g3, h5) G •H Figure 3: The rooted product G •H of graph G and rooted graph H Definition 8. [5] Let S and T be sets. A function f : S −→ T is one-to-one (injective) if for all s1, s2 ∈ S, f(s1) = f(s2) ⇐⇒ s1 = s2. Definition 9. [5] Let S and T be sets. A function f : S −→ T is onto (surjective) if for all t ∈ T , there exists s ∈ S such that f(s) = t. Definition 10. [5] Let S and T be sets. A function f : S −→ T is bijective if f is both injective and surjective. Definition 11. [5] Graphs G and H are isomorphic, denoted by G ∼= H, if there exists a bijective mapping f : V (G) −→ V (H) such that uv ∈ E(G) if and only if f(u)f(v) ∈ E(H). 3. Independent Neighborhood Polynomial Trees In this section, we generalize the independent neighborhood set of any tree and repre- sent it in an independent neighborhood polynomial of a graph. Proposition 1. Let G be a connected graph, and S ⊆ V (G). Then S is an independent neighborhood set of G if and only if the following hold: (i) S is an independent set (ii) For each uv ∈ E(G), there exists w ∈ S such that u, v ∈ N [w]. N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 69 Proof. Assume that S is an independent neighborhood set of G. Then S is an inde- pendent set and (i) holds. Let uv ∈ E(G). Since G = ⋃ w∈S ⟨N [w]⟩, there exists w ∈ S for with uv ∈ E(⟨N [w]⟩). This means that u, v ∈ N [w], and (ii) holds. Suppose that (i) and (ii) hold for S. Let v ∈ V (G) and let u ∈ V (S) \ {v} for which uv ∈ E(G). By (ii), there exists w ∈ S such that u, v ∈ N [w]. Thus, v ∈ V (⟨N [w]⟩). Since v is arbitrary, V (G) = V (⋃ w∈S ⟨N [w]⟩ ) . Let uv ∈ E(G). By (ii) again, there exists w ∈ S for which u, v ∈ N [w]. Hence, uv ∈ E (⟨N [w]⟩). Thus, uv ∈ E (⋃ w∈S ⟨N [w]⟩ ) . Hence, E(G) = E (⋃ w∈S ⟨N [w]⟩ ) . Therefore, S is an independent neighborhood set of G. ■ Proposition 2. Let G be any IN-graph. If Ω is an independent neighborhood set of G, then there is no proper subset of Ω, say ∆, such that ⋃ v∈∆ ⟨N [v]⟩ = G. Proof. Let G be any IN -graph. Let Ω be an independent neighborhood set of G. Assume to the contrary that there exists a proper subset ∆ of Ω such that ⋃ v∈∆ ⟨N [v]⟩ = G. Let u ∈ Ω\∆. Since Ω is an independent neighborhood set, every vertices in Ω are not adjacent. This implies u ∈ Ω\∆ is not a neighborhood of ∆. It follows that u is not in⋃ v∈∆ ⟨N [v]⟩. This is a contradiction for ⋃ v∈∆ ⟨N [v]⟩ = G. Hence, there is no proper subset of Ω that is also an independent neighborhood set of G. ■ Corollary 2. Let G be an IN-graph. If Ω is an independent neighborhood set of G, then there is no independent neighborhood set of G that contains Ω. Proof. Let Ω be an independent neighborhood set of an IN -graph G. Assume that there exists an independent neighborhood set of G that contains Ω, say ∆. Let ∆ = Ω ∪ {x1, x2, · · · , xn} for some xi ∈ V (G). Since ∆ is an independent neighborhood set of G, for all vj ∈ Ω and xi, vj′s and xi′s are non adjacent. This implies xi /∈ N [vj ] for all vj ∈ Ω, i = 1, · · · , n. It follows that xi is not in ⋃ v∈Ω ⟨N [v]⟩. Hence, ⋃ v∈Ω ⟨N [v]⟩ ≠ G. This is a contradiction to our assumption that Ω is an independent neighborhood set of G. Therefore, there is no independent neighborhood set of G that contains Ω. ■ For the succeeding results, we let N∗ = N ∪ {0}. N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 70 Theorem 2. Let G be any tree. Then for any u ∈ V (G), the set Ω = {v ∈ V (G) : d(u, v) = 2n, n ∈ N∗} is an independent neighborhood set of G. Proof. Let u ∈ V (G). Let Ω = {v ∈ V (G) : d(u, v) = 2n, n ∈ N∗}. Clearly, for any v1, v2 ∈ Ω, v1 and v2 are not adjacent. We are left to show that ⋃ ω∈Ω ⟨N [ω]⟩ = G. Assume to the contrary that ⋃ ω∈Ω ⟨N [ω]⟩ ̸= G. Then there exists xy ∈ E(G) such that xy /∈ E (⋃ ω∈Ω ⟨N [ω]⟩ ) . It follows that both x, y /∈ Ω. Observe that for any ω ∈ Ω, d(ω, x) = 2m+ 1,m ∈ N∗. Now, dG(ω, y) = dG(ω, x) + dG(x, y) = (2m+ 1) + 1 = 2m+ 2 = 2(m+ 1). Let n = m+ 1. Then n ∈ N∗ and d(ω, y) = 2n which implies y ∈ Ω, a contradiction since y /∈ Ω. Hence, ⋃ ω∈Ω ⟨N [ω]⟩ = G. Therefore, Ω is an independent neighborhood set of G. ■ Corollary 3. Let F be the set of nonpendant vertices in a tree G and f ∈ F . Let A = {a ∈ F : dG(a, f) = 2n, n ∈ N∗} and B = F \A. Then the sets Ω = {v : v is a pendant neighbor of a, for some a ∈ A} ∪B and ∆ = {u : u is a pendant neighbor of b, for some b ∈ B} ∪A are the only independent neighborhood sets of G. Proof. Let F be the set of nonpendant vertices in G and f ∈ F . Let A = {a ∈ F : dG(a, f) = 2n, n ∈ N∗} and B = F \A. N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 71 Then for every a ∈ A and b ∈ B, dG(a, b) = 2m + 1,m ∈ N∗. We note that for any u ∈ N(g), dG(u, g) = 1 for every g ∈ G. Let v be a pendant neighbor of a ∈ A. Now, for any b ∈ B, we have dG(v, b) =dG(v, a) + dG(a, b) =1 + 2m+ 1 =2(m+ 1). Let n = m + 1. Then n ∈ N∗ and dG(v, b) = 2n which is even. By Theorem 2, Ω is an independent neighborhood set of G. Similarly, we can show that ∆ is also an independent neighborhood set of G. We are left to show that Ω and ∆ are the only independent neighborhood sets of G. Clearly, from the definition of Ω and ∆, Ωc = ∆. Assume that there is another independent neighborhood set of G, say Λ. Define Λ = Ω1 ∪ ∆1 where Ω1 ⊂ Ω and ∆1 ⊂ ∆. Let x ∈ Ω \Ω1 and y ∈ ∆ \∆1. Suppose that xw, yz ∈ E(G) for some w, z ∈ Λ. Since Ω and ∆ are independent neighborhood sets of G, w must be in ∆1 and z must be in Ω1. Observe that dG(w, z) = 2r for some r ∈ N∗ and dG(y, z) = 1 since Λ is an independent neighborhood set of G and yz ∈ E(G). Now, dG(w, y) =dG(w, z) + dG(y, z) =2n+ 1. This means dG(w, y) is odd which is a contradiction since ∆ is an independent neighbor- hood set of G. Hence, Λ cannot be an independent neighborhood set of G. Therefore, S and T are the only independent neighborhood set of G. ■ Corollary 4. Let F be the set of nonpendant vertices in a tree G and f ∈ F . Let A = {a ∈ F : d⟨F ⟩(a, f) = 2n, n ∈ N∗} and B = F \A. Suppose that Ω = {v : v is a pendant neighbor of a ∈ A} ∪B and ∆ = {u : u is a pendant neighbor of b ∈ A} ∪A. Then Ni(G, x) = x|Ω| + x|∆|. Example 5. Consider u = 5 ∈ V (G) in the graph in Figure 4. N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 72 1 2 3 45 6 7 8 9 10 11 12 13 14 15 16 17 18 1920 G : Figure 4: A tree G Observe that for every u in the set Ω = {3, 5, 6, 7, 10, 11, 13, 15}, dG(u, 5) = 2n, n ∈ N∗. By Theorem 2, Ω is an independent neighborhood set of G. Also, if we consider u = 1 ∈ V (G), for each v in the set ∆ = {1, 2, 4, 8, 9, 12, 14, 16, 17, 18, 19, 20}, dG(v, 1) = 2m,m ∈ N∗. By Theorem 3.2.4, ∆ is also an independent neighborhood set of G. We note that |Ω| = 8 and |∆| = 12. Therefore, Ni(G, x) = x8 + x12. Other Solution: From Figure 4, we can see that the set of nonpendant vertices in G is given by F = {3, 4, 7, 9, 11, 13, 14, 15}. Consider f = 3 ∈ F . Then A = {3, 7, 11, 13, 15} and B = F \ A = {4, 9, 14}. Applying Corollary 3, the independent neighborhood sets of G are Ω = {v : v is a pendant neighbor of a, for some a ∈ A} ∪B = {1, 2, 8, 12, 16, 17, 18, 19, 20} ∪ {4, 9, 14} = {1, 2, 4, 8, 9, 12, 14, 16, 17, 18, 19, 20} and ∆ = {v : v is a pendant neighbor of b, for some b ∈ B} ∪A = {5, 6, 10} ∪ {3, 7, 11, 13, 15} = {3, 5, 6, 7, 10, 11, 13, 15}. Therefore, by Corollary 4, Ni(G, x) = x8 + x12. Corollary 5. For any tree T , if Ω and ∆ are the independent neighborhood sets of T , then Ω ∪∆ = V (T ). Proof. Let Ω and ∆ be the independent neighborhood sets of a tree T . Assume to the contrary that Ω∪∆ ̸= V (T ). Then there exists v ∈ V (T ) such that v /∈ Ω∪∆. This implies v /∈ Ω and v /∈ ∆. Since Ω and ∆ are both independent neighborhood sets of T , there N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 73 exists g ∈ Ω and h ∈ ∆ such that v ∈ N [g] and v ∈ N [h]. This shows that d(v, g) = 1 and d(v, h) = 1 and follows that d(g, h) = d(v, g) + d(v, h) = 2. Thus, Ω ∪ {h} and ∆ ∪ {g} are independent neighborhood sets of T which is a contradiction by Corollary 3. Hence, Ω ∪∆ = V (T ). ■ Corollary 6. For any tree T , if Ω and ∆ are the independent neighborhood sets of T , then Ω ∩∆ = ∅. Proof. Let Ω and ∆ be the independent neighborhood sets of a tree T . Assume to the contrary that Ω ∩∆ ̸= ∅. This implies there exists u ∈ Ω ∩∆. It follows that u ∈ Ω and u ∈ ∆. Since Ω and ∆ are both independent neighborhood sets of T , d(u, g) = 2n, ∀g ∈ Ω and d(u, h) = 2m,∀h ∈ ∆ for some n,m ∈ N∗. Consequently, d(g, h) = d(g, u) + d(u, h) = 2n+ 2m = 2(n+m). This shows that Ω∪∆ is an independent neighborhood set of T . But Ω∪∆ = V (T ) which is clearly not an independent neighborhood set of T . Hence, Ω ∩∆ = ∅. ■ Corollary 7. For any tree T with independent neighborhood sets Ω and ∆, if uv ∈ E(T ), then u ∈ Ω and v ∈ ∆. Proof. Let T be a tree with independent neighborhood sets Ω and ∆. Let uv ∈ E(T ). Suppose that u /∈ Ω or v /∈ ∆. Consider the following cases. case 1: u /∈ Ω and v ∈ ∆ Since uv ∈ E(T ) and Ω is an independent neighborhood set of T , by Proposition 1, there exists w ∈ Ω such that u, v ∈ N [w]. But the set of edges {uw, vw, uv} forms a cycle which is a contradiction since T is a tree. case 2: v /∈ ∆ and u ∈ Ω By Proposition 1, being ∆ an independent neighborhood set of T implies there exists z ∈ ∆ such that u, v ∈ N [z]. Observe that the edges uz, vz, uv form a cycle which is a contradiction since T is acylic. case 3: u /∈ Ω and v /∈ ∆ Since Ω and ∆ are independent neighborhood sets of T , there exist x ∈ Ω and y ∈ ∆ such that u, v ∈ N [x] and u, v ∈ N [y] by Proposition 1. The set of edges {ux, vx, uv} and {uy, vy, uv} are all cycle which is a contradiction since T is acyclic. Thus, in either of the cases, we arrived at a contradiction. Therefore, u ∈ Ω and v ∈ ∆. ■ 4. Independent Neighborhood Polynomial of the Rooted Product of Two Trees In this section, we establish the independent neighborhood sets of the rooted product of a tree and a rooted tree using the independent neighborhood sets of each tree and represent it in an independent neighborhood polynomial of a graph. N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 74 Theorem 3. Let G be any tree and H be a rooted tree with root vertex u. Then the distance d((x, y), (w, z)) between two vertices (x, y), (w, z) of the rooted product graph G•H is given by: 1. d((x, y), (w, z)) = d(y, z) if x = w, 2. d((x, y), (w, z)) = d(x,w) if y = u = z, otherwise, 3. d((x, y), (w, z)) = d((x, y), (x, u)) + d((x, u), (w, u)) + d((w, u), (w, z)). Proof. 1. Let S = {(x, y), (w, z) ∈ V (G • H) : x = w}. We claim that ⟨S⟩ ∼= H. First, we define the map function β : S → V (H) given by (x, y) 7→ y for y ∈ H. For (x, y1), (x, y2) ∈ S such that β((x, y1)) = β((x, y2)), we have y1 = β((x, y1)) = β((x, y2)) = y2. This shows that β is one-to-one. Since S = {(x, y) ∈ V (G•H) : x ∈ V (G), y ∈ V (H)}, for every h ∈ V (H), there exists g ∈ V (G) such that (g, h) ∈ V (G • H). Observe that h = β((g, h)). Hence, β is onto. Lastly, we show that β preserves adjacency. Let (g, h1), (g, h2) ∈ S ⊆ V (G • H) such that (g, h1)(g, h2) ∈ E(G • H). By Definition 7, h1h2 ∈ E(H). Thus, (g, h1)(g, h2) ∈ E(G • H) ⇔ β((g, h1))β((g, h2)) = h1h2 ∈ E(H). Hence, β preserves adjacency. Therefore, ⟨S⟩ ∼= H. Consequently, d((x, y), (w, z)) = d(y, z) for x = w. 2. Let T = {(x, y), (w, z) ∈ V (G • H) : y = u = z}. We claim that ⟨T ⟩ ∼= G. First, we define the map function γ : T → V (G) given by (x, y) 7→ x. Let (x1, u), (x2, u) ∈ T . If γ((x1, u)) = γ((x2, u)), then x1 = γ((x1, u)) = γ((x2, u)) = x2. This implies γ is one- to-one. Since for every g1 ∈ V (G), γ((g, u)) = g, γ is onto. Lastly, let (g1, u), (g2, u) ∈ V (G • H) such that (g1, u)(g2, u) ∈ E(G • H). By Definition 7, g1g2 ∈ E(G). Now, (g1, u)(g2, u) ∈ E(G •H) ⇔ γ((g1, u))γ((g2, u)) = g1g2 ∈ E(G). Hence, γ preserves adja- cency. Thus, ⟨T ⟩ ∼= G. Therefore, d((x, y), (w, z)) = d(x,w) for y = u = z. 3. Since G • H is a tree, every vertices of G • H is connected by a unique path. By definition of rooted product, for vertices (x, y), (w, z) where x ̸= w and y ̸= z, the vertices (x, y) and (w, z) is connected by the paths (x, y)-(x, u) path, (x, u)-(w, u) path and (w, u)-(w, z) path where u is the root vertex of graph H. Hence, by Remark 2, d((x, y), (w, z)) = d((x, y), (x, u)) + d((x, u), (w, u)) + d((w, u), (w, z)). ■ Remark 3. Let G be a tree graph, H be a rooted tree and u be its rooted vertex. If y = u and z ̸= u, then d((x, y), (w, z)) = d((x, y), (x, u)) + d((x, u), (w, u)) + d((w, u), (w, z)) = 0 + d((x, u), (w, u)) + d((w, u), (w, z)) = d((x, u), (w, u)) + d((w, u), (w, z)) = d(x,w) + d(u, z). N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 75 Theorem 4. Let G and rooted H be trees with independent neighborhood sets Ω1,∆1 and Ω2,∆2, respectively. Then the independent neighborhood sets of G •H are {(x, y) : x ∈ Ω1, y ∈ Ω2} ∪ {(w, z) : w ∈ ∆1, z ∈ ∆2} and {(w, y) : w ∈ ∆1, y ∈ Ω2} ∪ {(x, z) : x ∈ Ω1, z ∈ ∆2}. Proof. Let G and rooted H be trees with independent neighborhood sets Ω1,∆1 and Ω2,∆2, respectively. Let u be the root vertex of H and that without loss of generality, let u ∈ Ω2. We will show that the sets {(x, y) : x ∈ Ω1, y ∈ Ω2} ∪ {(w, z) : w ∈ ∆1, z ∈ ∆2} and {(w, y) : w ∈ ∆1, y ∈ Ω2} ∪ {(x, z) : x ∈ Ω1, z ∈ ∆2} are the independent neighborhood sets of G •H. Now, for any x ∈ Ω1, y ∈ Ω2, w ∈ ∆1 and z ∈ ∆2, d((x, y), (w, z)) = d((x, y), (x, u)) + d((x, u), (w, u)) + d((w, u), (w, z)). Since Ω2 is an independent neighborhood set of H, by Theorem 2, d((x, y), (x, u)) = d(y, u) = 2m,m ∈ N∗. Observe that d((x, u), (w, u)) = d(x,w) = 2n + 1, n ∈ N∗ for x ∈ Ω1, w ∈ ∆1 and d((w, u), (w, z)) = d(u, z) = 2r + 1, r ∈ N∗ for u ∈ Ω2, z ∈ ∆2. It follows that d((x, y), (w, z)) = 2m+(2n+1)+ (2r+1) = 2(m+n+1), which is even and by Theorem 2, the set {(x, y) : x ∈ Ω1, y ∈ Ω2} ∪ {(w, z) : w ∈ ∆1, z ∈ ∆2} is an independent neighborhood set of G •H. Following same argument for the set {(w, y) : w ∈ ∆1, y ∈ Ω2} ∪ {(x, z) : x ∈ Ω1, z ∈ ∆2} shows that it is also an independent neighborhood set of G •H. ■ Corollary 8. Let Ω1,∆1 and Ω2,∆2 be the independent neighborhood sets of trees G and H ,respectively. Then Ni(G •H,x) = x|Ω1||Ω2|+|∆1||∆2| + x|∆1||Ω2|+|Ω1||∆2|. N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 76 Example 6. Consider the graph G and graph H in Figure 5. a b c d e G : 1 2 3 45 6 78 H : Figure 5: Trees G and H Let the vertex 2 be a rooted vertex and label the rooted tree as H1. Then the rooted product of G and H1 is given in Figure 6. (a, 1) (a, 2) (a, 3) (a, 4)(a, 5) (a, 6) (a, 7)(a, 8) (b, 1) (b, 2) (b, 3) (b, 4)(b, 5) (b, 6) (b, 7)(b, 8) (d, 1) (d, 2) (d, 3) (d, 4)(d, 5) (d, 6) (d, 7)(d, 8) (c, 1) (c, 2) (c, 3) (c, 4)(c, 5) (c, 6) (c, 7)(c, 8) (e, 1) (e, 2) (e, 3) (e, 4)(e, 5) (e, 6) (e, 7)(e, 8) Figure 6: Rooted product of graph G and rooted graph H1 We note that the independent neighborhood sets of G are Ω1 = {a, d, c}, ∆1 = {b, e} and the independent neighborhood sets of H1 are Ω2 = {2, 4, 5, 7, 8}, ∆2 = {1, 3, 6}. By Theorem 4, the independent neighborhood sets of G •H1 are {(x, y) : x ∈ Ω1, y ∈ Ω2} ∪ {(w, z) : w ∈ ∆1, z ∈ ∆2} = {(a, 2), (a, 4), (a, 5), (a, 7), (a, 8), (d, 2), (d, 4), (d, 5), (d, 7), (d, 8), (c, 2), (c, 4), (c, 5), (c, 7), (c, 8)} ∪ {(b, 1), (b, 3), (b, 6), (e, 1), (e, 3), (e, 6)} = {(a, 2), (a, 4), (a, 5), (a, 7), (a, 8), (d, 2), (d, 4), (d, 5), (d, 7), (d, 8), (c, 2), (c, 4), (c, 5), (c, 7), (c, 8), (b, 1), (b, 3), (b, 6), (e, 1), (e, 3), (e, 6)} N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 77 and {(w, y) : w ∈ ∆1, y ∈ Ω2} ∪ {(x, z) : x ∈ Ω1, z ∈ ∆2} = {(b, 2), (b, 4), (b, 5), (b, 7), (b, 8), (e, 2), (e, 4), (e, 5), (e, 7), (e, 8)} ∪ {(a, 1), (a, 3), (a, 6), (d, 1), (d, 3), (d, 6), (c, 1), (c, 3), (c, 6)} = {(b, 2), (b, 4), (b, 5), (b, 7), (b, 8), (e, 2), (e, 4), (e, 5), (e, 7), (e, 8), (a, 1), (a, 3), (a, 6), (d, 1), (d, 3), (d, 6), (c, 1), (c, 3), (c, 6)}. Furthermore, |Ω1| = 3, |∆1| = 2, |Ω2| = 5 and |∆2| = 3. Therefore, by Corollary 8, Ni(G •H1, x) = x3(5)+2(3) + x2(5)+3(3) = x21 + x19. Theorem 5. Let G be any tree and H be another tree. Suppose H1 is a rooted tree from H with rooted vertex u1 and H2 is also a rooted tree from H with rooted vertex u2 where H1 ∼= H2. Then the independent neighborhood polynomial of the rooted product of G and H2 is the same as the independent neighborhood polynomial of the rooted product of G and H1, that is, Ni(G •H2, x) = Ni(G •H1, x). Proof. Let G and H be trees with independent neighborhood sets Ω1,∆1 and Ω2,∆2, respectively. Suppose H1 is a rooted tree from H with rooted vertex u1 and that u1 ∈ Ω2. By Theorem 4, the sets {(x, y) : x ∈ Ω1, y ∈ Ω2} ∪ {(w, z) : w ∈ ∆1, z ∈ ∆2} and {(w, y) : w ∈ ∆1, y ∈ Ω2} ∪ {(x, z) : x ∈ Ω1, z ∈ ∆2} are the independent neighborhood sets of G •H1. Suppose H2 is another rooted tree with rooted vertex u2 different from u1 whose graph is the same with H1. Without loss of generality, let u2 ∈ ∆2. We can see that the sets {(x, y) : x ∈ Ω1, y ∈ Ω2} ∪ {(w, z) : w ∈ ∆1, z ∈ ∆2} and {(w, y) : w ∈ ∆1, y ∈ Ω2} ∪ {(x, z) : x ∈ Ω1, z ∈ ∆2} are also the independent neighborhood sets of G •H2. Thus, Ni(G •H2, x) = x|Ω1||Ω2|+|∆1||∆2| + x|∆1||Ω2|+|Ω1||∆2|. Therefore, Ni(G •H2, x) = Ni(G •H1, x). ■ N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 78 Example 7. Consider the graphs G and H in Figure 5. Let H2 be a rooted graph with rooted vertex 1 whose graph is the same with H. (a, 1) (a, 2) (a, 3) (a, 4)(a, 5) (a, 6) (a, 7)(a, 8) (b, 1) (b, 2) (b, 3) (b, 4)(b, 5) (b, 6) (b, 7)(b, 8) (c, 1) (c, 2) (c, 3) (c, 4)(c, 5) (c, 6) (c, 7)(c, 8) (d, 1) (d, 2) (d, 3) (d, 4)(d, 5) (d, 6) (d, 7)(d, 8) (e, 1) (e, 2) (e, 3) (e, 4)(e, 5) (e, 6) (e, 7)(e, 8) Figure 7: Rooted product of tree G and rooted tree H2 We can verify that the independent neighborhood sets of G •H2 are {(a, 2), (a, 4), (a, 5), (a, 7), (a, 8), (d, 2), (d, 4), (d, 5), (d, 7), (d, 8), (c, 2), (c, 4), (c, 5), (c, 7), (c, 8), (b, 1), (b, 3), (b, 6), (e, 1), (e, 3), (e, 6)} and {(b, 2), (b, 4), (b, 5), (b, 7), (b, 8), (e, 2), (e, 4), (e, 5), (e, 7), (e, 8), (a, 1), (a, 3)(a, 6), (d, 1), (d, 3), (d, 6), (c, 1), (c, 3), (c, 6)}. Therefore, Ni(G •H2, x) = Ni(G •H1, x). Theorem 6. Suppose G is the rooted tree with independent neighborhood sets Ω1,∆1 and H be any tree with independent neighborhood sets Ω2,∆2. Then the independent neighborhood sets of H •G are {(x, y) : x ∈ Ω2, y ∈ Ω1} ∪ {(w, z) : w ∈ ∆2, z ∈ ∆1} and {(w, y) : w ∈ ∆2, y ∈ Ω1} ∪ {(x, z) : x ∈ Ω2, z ∈ ∆1}. Proof. The proof can be shown similar to Theorem 4 by just interchanging the first and second coordinates of the ordered pairs of vertices. ■ Theorem 7. Let Ω1,∆1 and Ω2,∆2 be the independent neighborhood sets of trees G and H, respectively. Then Ni(H •G, x) = Ni(G •H,x). Proof. Let G and H be trees with independent neighborhood sets Ω1,∆1 and Ω2,∆2, respectively. Notice that |{(x1, y1) : x1 ∈ Ω1, y1 ∈ Ω2}| = |{(x2, y2) : x2 ∈ Ω2, y2 ∈ Ω1}| N. S. Abdulcarim, S. C. Dagondon / Eur. J. Pure Appl. Math, 15 (1) (2022), 64-81 79 |{(x3, y3) : x3 ∈ ∆1, y3 ∈ ∆2}| = |{(x4, y4) : x4 ∈ ∆2, y4 ∈ ∆1}| |{(x5, y5) : x5 ∈ ∆1, y5 ∈ Ω2}| = |{(x6, y6) : x5 ∈ Ω2, y6 ∈ ∆1}| |{(x7, y7) : x7 ∈ Ω1, y7 ∈ ∆2}| = |{(x8, y8) : x8 ∈ ∆2, y8 ∈ Ω1}|. Therefore, Ni(H •G, x) = Ni(G •H,x). ■ Example 8. Consider the graphs G and H in Figure 5. Suppose that G is the rooted graph and wihtout loss of generality, let a be its rooted vertex shown in Figure 8. (1, a) (1, b) (1, c) (1, d) (1, e) (2, a) (2, b) (2, c) (2, d) (2, e) (3, a) (3, b) (3, c) (3, d) (3, e) (4, a) (4, b) (4, c) (4, d) (4, e) (5, a) (5, b) (5, c) (5, d) (5, e) (6, a) (6, b) (6, c) (6, d) (6, e) (7, a) (7, b) (7, c) (7, d) (7, e) (8, a) (8, b) (8, c) (8, d) (8, e) Figure 8: Rooted product of tree H and rooted tree G By Theorem 6, the independent neighborhood sets of H •G are {(x, y) : x ∈ Ω2, y ∈ Ω1} ∪ {(w, z) : w ∈ ∆2, z ∈ ∆1} = {(2, a), (2, d), (2, c), (4, a), (4, d), (4, c), (5, a), (5, d), (5, c), (7, a), (7, d), (7, c), (8, a), (8, d), (8, c)} ∪ {(1, b), (1, e), (3, b), (3, e), (6, b), (6, e)} = {(2, a), (2, d), (2, c), (4, a), (4, d), (4, c), (5, a), (5, d), (5, c), (7, a), (7, d), (7, c), (8, a), (8, d), (8, c), (1, b), (1, e), (3, b), (3, e), (6, b), (6, e)} and {(x, y) : x ∈ ∆2, y ∈ Ω1} ∪ {(w, z) : w ∈ Ω2, z ∈ ∆1} = {(1, a), (1, d), (1, c), (3, a), (3, d), (3, c), (6, a), (6, d), (6, c)} ∪ {(2, b), (2, e), (4, b), (4, e), (5, b), (5, e), (7, b), (7, e), (8, b), (8, e)} REFERENCES 80 = {(1, a), (1, d), (1, c), (3, a), (3, d), (3, c), (6, a), (6, d), (6, c), (2, b), (2, e), (4, b), (4, e), (5, b), (5, e), (7, b), (7, e), (8, b), (8, e)}. Furthermore, |{(x, y) : x ∈ Ω2, y ∈ Ω1} ∪ {(w, z) : w ∈ ∆2, z ∈ ∆1}| = 21 and |{(x, y) : x ∈ ∆2, y ∈ Ω1} ∪ {(w, z) : w ∈ Ω2, z ∈ ∆1}| = 19. Therefore, Ni(H •G, x) = x19 + x21 = Ni(G •H,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] G.D Birkhoff. A determinant formula for the number of ways of coloring a map. Ann. of Math. (2), 14:42–46, 1912. [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] E.J. Farrel. Introduction to matching polynomials. J. Combinatorial Thoery B, 27:75–86, 1979. [5] P. Zhang G. Chartrand. A First Course in Graph Theory. Dover Publications, Inc, Mineola, New York, 2012. [6] F. Harary. Graph Theory. Addison-Wesley Publishing Company, 1969. [7] F. Harary I. Gutman. Generalizations of the matching polynomial. Util. Math, 24:97– 106, 1983. [8] U.S.R. Murthy J.A. Bondy. Graph Theory, Graduate Texts in Mathematics. Springer, 2007. [9] R.J. Nowakowski J.I. Brown. The neighbourhood polynomial of a graph. Astralasian Journal of Combinatorics, 42:55–68, 2008. REFERENCES 81 [10] V. E. Levit and E. Mandrescu. 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.