EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2025, Vol. 18, Issue 2, Article Number 5978 ISSN 1307-5543 – ejpam.com Published by New York Business Global Convex Independent Neighborhood Polynomial of Some Special Graphs Edison John B. Aguilon1, Susan C. Dagondon2, Rosalio G. Artes, Jr.3 1 Department of Mathematics and Statistics, College of Science and Mathematics, Mindanao State University-Iligan Institute of Technology, 9200 Iligan 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 3 Mathematics and Sciences Department, College of Arts and Sciences, Mindanao State University Tawi-Tawi College of Technology and Oceanography, Sanga-Sanga, 7500 Bongao, Philippines Abstract. In this paper, we introduced the notion of convex independent neighborhood poly- nomial for a graph. We further explored the convex independent neighborhood polynomial for some special graphs such as paths, cycles, complete graphs, and star graphs. We generated these polynomials by counting the number of convex subsets of a graph with corresponding maximum independent set in the neighborhood system. 2020 Mathematics Subject Classifications: 05C31, 05C69 Key Words and Phrases: Convex sets, Convex subgraph, Independent neighborhood system, Independent set, Convex independent neighborhood polynomial 1. Introduction Graph theory offers a broad foundation for studying various mathematical structures, such as graph polynomials and convexity in graphs. Graph polynomials have been the focus of interest in recent developments in graph theory. The use of polynomials to represent graphs has recently become a significant area of study, driven by its practical applications in various scientific fields [1]. As a result, several graph polynomials have been formulated, and substantial results have been obtained such as neighborhood polynomial which was introduced in 2008 by Brown and Nowakowski [2] and independent neighborhood polynomial which was studied by Abdulcarim et al. in 2021 [3]. On the other DOI: https://doi.org/10.29020/nybg.ejpam.v18i2.5978 Email addresses: edisonjohn.aguilon@g.msuiit.edu.ph (E.J. Aguilon), susan.dagondon@g.msuiit.edu.ph (S. Dagondon), rosalioartes@msutawi-tawi.edu.ph (R. Artes, Jr.) https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0) E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 2 of 18 hand, convexity in a graph is defined based on specific path-based properties. A set of vertices is considered convex if, for any two vertices within the set, all shortest paths between them remain entirely within the set. Further, convexity is gaining its resurgence due to its various current applications. Several authors studied graph convexity in vari- ous perspectives and some explored convexity in Rn [4]. In particular, studies in [5] [6] [7] considered applying the concept of convexity to graphs and to its polynomials. Furthermore, in the studies of R. Artes Jr. et al., they integrated the concept of convexity with graph polynomial which involve counting the number of substructures with corresponding neighborhood system cardinality of some property [8][9]. With this development in the study of convex subsets and polynomials in graph, this paper aims to investigate another type of graph polynomial called the convex independent neighborhood polynomial and considers applying it to some special graphs. 2. Terminologies and Notations A graph G is a finite nonempty set V (G) of objects called vertices together with a possibly empty set E(G) of 2-element subsets of V (G) called edges. Vertices are sometimes called points or nodes, while edges are sometimes called lines or links. Given a graph G = ⟨V (G), E(G)⟩ , where V (G) is the vertex-set of G and E(G) is the edge-set of G, the number of vertices in a graph G is the order of G and the number of edges is the size of G. A subset S of V (G) is said to be independent in G if no two vertices in the set are adjacent in G. In other words, for any two vertices u, v ∈ S, uv /∈ E(G). The cardinality of a maximum independent set is called independence number of G. A path consists of a sequence of edges, one following another in which no vertex appears more than once. A path of order n with vertices v1, v2, . . . , vn (in order) is denoted by Pn. A graph G is connected if every pair of vertices in the vertex-set of G is connected by a path. A cycle is a closed path of order n and is denoted by Cn. A graph G is called bipartite if V (G) can be partitioned into two nonempty independent subsets A and B of V (G) (called partite sets). A complete bipartite graph is a bipartite graph in which each vertex in A is joined to each vertex in B and is denoted by Km,n where m and n are the order of A and B, respectively. The complete bipartite graph K1,n of order n + 1 is called a star graph. A graph in which each pair of distinct vertices are adjacent is called a complete graph and denoted by Kn where n is the number of vertices. If v ∈ V (G), the open neighborhood or simply neighborhood of v in G is the set NG(v) = {u ∈ V (G) : uv ∈ E(G)}. For the subset S of V (G), the neighborhood system of S in G is the set NG(S) = (⋃ s∈S NG(s) ) \S. The independent neighborhood system of a subset S of V (G) is a subset of the neighborhood system of S in V (G) which is independent. If the independent neighborhood system of a subset S of V (G) is maximum, then we say that it is the maximum independent neighborhood system of S, denoted by Γin-sets. Given a connected graph G and vertices u, v ∈ V (G), the distance dG(u, v) from a vertex u to vertex v is the smallest length of a u−v path in G. A u− v path of length dG(u, v) is called a u− v geodesic. The geodesic closure of {u, v} is the set consists of all vertices lies in any u−v geodesic including u and v and is E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 3 of 18 denoted by IG[u, v]. In other words, IG[u, v] = {u, v} ∪ {x : x lies in u− v geodesic in G}. The geodesic closure of a subset S of V (G) is the set IG[S] = ⋃ u,v∈S IG[u, v]. A subset S of V (G) is convex if for every u, v ∈ S, the vertex-set of every u− v geodesic is contained entirely in S. A convex subset of cardinality i is called i − convex. A subgraph H of G induced by a convex subset of V (G) is called a convex subgraph. The convex independent neighborhood polynomial of a graph G of order n, denoted by Γcin(G;x, y) in x and y indeterminates, is given by Γcin(G;x, y) = n−i∑ j=0 n∑ i=1 cij(G)xiyj , where cij(G) is the number of i-convex subsets of G with maximum independent neighborhood system of cardinality equal to j. The degree of an algebraic polynomial is equal to the degree of the term that has the highest exponent. If, in additon, the poly- nomial is defined by several variables then two or more variables are in a term as factors, wherein the degree of the term is the sum of the exponents of the variables; and the degree of the polynomial will be determined by the highest degree in their terms [10]. 3. Preliminary Results This section illustrates the definition of convex independent neighborhood polynomial of a graph. This illustration form the basis for the more comprehensive analyses and conclusions for the following sections. Consider the graph G in Figure 1. v1 v2 v3 v5 v4 Figure 1: A graph G of order 5 and size 5 The convex subsets of V (G) with corresponding maximum independent neighborhood systems (Γin-sets) are enumerated in the following Tables 1, 2 and 3: 1-convex Γin-sets {v1} {v2} {v2} {v1, v3} and {v1, v4} {v3} {v2, v5} and {v4, v5} {v4} {v2} and {v3} {v5} {v3} Table 1: 1-convex subsets of V (G) and its corresponding Γin-sets. From Table 1, observe that there are 3 1-convex subset of V (G) with maximum E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 4 of 18 independent neighborhood systems (Γin-sets) cardinality equal to 1, and 2 1-convex subsets of V (G) with maximum independent neighborhood systems (Γin-sets) cardinality equal to 2. This contributes to the convex independent neighborhood polynomial of G as 3xy + 2xy2. 2-convex Γin-sets {v1, v2} {v3}, {v4} {v2, v3} {v1, v4, v5} {v2, v4} {v1, v3} {v3, v4} {v2, v5} {v3, v5} {v2}, {v4} Table 2: 2-convex subsets of V (G) and its corresponding Γin-sets. From Table 2, observe that there are 2 2-convex subsets of V (G) with maximum independent neighborhood systems (Γin-sets) cardinality equal to 1, 2 2-convex subsets of V (G) with maximum independent neighborhood systems (Γin-sets) cardinality equal to 2, and 1 2-convex subset of V (G) with maximum independent neighborhood systems (Γin-sets) cardinality equal to 3. This contributes to the convex independent neighborhood polynomial of G as 2x2y + 2x2y2 + x2y3. 3-convex Γin-sets {v1, v2, v3} {v4, v5} {v1, v2, v4} {v3} {v2, v3, v4} {v1, v5} {v2, v3, v5} {v1, v4} {v4, v3, v5} {v2} Table 3: 3-convex subsets of V (G) and its corresponding Γin-sets. From Table 3, observe that there are 2 3-convex subsets of V (G) that has maximum independent neighborhood systems (Γin-sets) cardinality equal to 1, and 3 3-convex subsets of V (G) that has maximum independent neighborhood systems (Γin-sets) cardinality equal to 2. This contributes to the convex independent neighborhood polynomial of G as 2x3y + 3x3y2. For 4-convex subsets of V (G), it can be verified that there are 3 4-convex subset with maximum independent neighborhood systems (Γin)-sets cardinality equal to 1. This contributes to convex independent neighborhood polynomial of G as 3x4y. For 5-convex subsets of V (G), it can be verified that there is only 1 5-convex subset with empty (zero cardinality) maximum independent neighborhood systems (Γin)-set. This contributes to convex independent neighborhood polynomial of G as x5. E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 5 of 18 Therefore, by combining all the terms, we have Γcin(G;x, y) = x5 + 3x4y + 2x3y + 3x3y2 + 2x2y + 2x2y2 + x2y3 + 3xy + 2xy2. Remark 3.1. The following properties of the convex independent neighborhood polynomial of a graph G are noted: i) The degree of the convex independent neighborhood polynomial of a connected graph is n. Moreover, it is a monic polynomial. ii) The convex independent neighborhood polynomial of a disconnected graph with isolated n vertices is nx. 4. Paths and Cycles This section discusses the convex independent neighborhood polynomial of paths (Pn) and cycles (Cn). Theorem 4.1. Let Pn be a path of order n. Then, for n ≥ 2, the convex independent neighborhood polynomial of Pn is given by Γcin(Pn;x, y) = xn + n−1∑ i=1 2xiy + n−2∑ i=1 (n− 1− i)xiy2. Proof. Let V (Pn) = {v1, v2, . . . , vn} be the vertex set of Pn. Note that for n-convex subset of V (Pn) there is only one set that is {v1, v2, . . . , vn} with empty (zero cardinality) Γin-set. This contributes to the term xn of the polynomial. Next, for i-convex subset of V (Pn), i = 1, 2, ..., n− 1. We consider two cases in choosing the i-convex subset of V (Pn), the first case is choosing set of vertices which include exactly one of the end vertices and for the second case choosing set of vertices which does not include the end vertices. For the first case, for 1-convex subset of subset of V (Pn), consider the vertex sets {v1} and {vn}, both of these convex vertex sets contains only one Γin-sets namely {v2} and {vn−1}, respectively. For 2-convex subset of V (Pn), consider the vertex set {v1, v2} and {vn−1, vn}, both of these convex vertex sets contains only one Γin-sets namely {v3} and {vn−2}, respectively. Since V (Pn) is finite, it follows that i-convex subsets of V (Pn) is also finite. This means that we may continue this process up to (n − 1)-convex subsets of Pn. All of these i-convex subsets has Γin-sets cardinality equal to one. Thus, by combining all of these i-convex subsets with Γin-sets cardinality equal to one. We have 2xy + 2x2y + 2x3y + · · ·+ 2xn−1y = n−1∑ i=1 2xiy. For the second case, choosing i-convex subset of V (Pn) which does not include the end vertices. For 1-convex subsets of V (Pn), consider the vertices {v2}, {v3}, . . . , {vn−1}. Then E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 6 of 18 there are (n−2) 1-convex subsets of V (Pn) whose Γin-sets contains two elements. Next, for 2-convex subsets of V (Pn), consider the sets {v2, v3}, {v3, v4}, {v4, v5}, . . . , {vn−2, vn−1}. This means that there are (n − 3) 2-convex subsets of V (Pn) with Γin-sets equal to two. Since V (Pn) is finite, similarly we can continue this process till we choose the set {v2, v3, ..., vn−1}. All of these i-convex subsets have Γin-sets with cardinality equal to two. Thus, by combining all of these i-convex subsets of V (Pn) with Γin-sets cardinality equal to two, we have (n− 2)x1y2 + (n− 3)x2y2 + (n− 4)x3y2 + · · ·+ xn−2y2 = n−2∑ i=1 (n− 1− i)xiy2. Therefore, by combining all the above scenarios, the convex independent neighborhood polynomial of Pn is Γcin(Pn;x, y) = xn + n−1∑ i=1 2xiy + n−2∑ i=1 (n− 1− i)xiy2. ■ Let V (Pn) = {v1, . . . , vn} be vertex set of Pn. Note that when i = n, there is only 1 n-convex subset of V (Pn) with empty (zero cardinality) maximum independent neighborhood system (Γin). Now, for i = 1, 2, ..., (n−1), there are (n−1) i-convex subsets of V (Pn) with maximum independent neighborhood system (Γin)-set cardinality equal to 1. Moreover, there are (n − 2) i-convex subsets of V (Pn) with maximum independent neighborhood system (Γin)-sets. Thus, by combining all the vertices, we have 1 + (n− 1) + (n− 2) = 2n− 2 number of terms of the convex independent neighborhood polynomial of Pn. Thus, we have this corollary Corollary 4.2. For n ≥ 2, the number of terms for the convex independent neighborhood polynomial of Pn is given by 2n− 2. Illustration 4.3. Consider P5 be a path of order 5. v1 v2 v3 v4 v5 Figure 2: A path P5 of order 5 Then, by using Theorem 4.1, Γcin(P5;x, y) = x5 + 5−1∑ i=1 2xiy + 5−2∑ i=1 (5− 1− i)xiy2 = x5 + 4∑ i=1 2xiy + 3∑ i=1 (4− i)xiy2 E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 7 of 18 = x5 + (2xy + 2x2y + 2x3y + 2x4y) + (3xy2 + 2x2y2 + x3y2) = x5 + 2x4y + 2x3y + x3y2 + 2x2y + 2x2y2 + 2xy + 3xy2. And by Corollary 4.2, there are [2(5)− 2] = 8 terms in convex independent neighborhood polynomial of P5. To see the convex subsets of V (P5) and its corresponding Γin-sets of P5, refer to the Tables 4, 5, and 6: 1-convex Γin-sets {v1} {v2} {v2} {v1, v3} {v3} {v2, v4} {v4} {v3, v5} {v5} {v4} Table 4: 1-convex subsets of V (P5) and its corresponding Γin-sets. Table 4 shows that there are 2 1-convex subsets of V (P5) with Γin-sets cardinality equal to 1, and 3 1-convex subsets of V (P5) with Γin-sets cardinality equal to 2. This contributes to the convex independent neighborhood polynomial of P5 as 2xy + 3xy2. 2-convex Γin-sets {v1, v2} {v3} {v2, v3} {v1, v4} {v3, v4} {v2, v5} {v4, v5} {v3} Table 5: 2-convex subsets of V (P5) and its corresponding Γin-sets. Table 5 shows that there are 2 2-convex subsets of V (P5) with Γin-sets cardinality equal to 1, and 2 2-convex subsets of V (P5) with Γin-sets cardinality equal to 2. This contributes to the convex independent neighborhood polynomial of P5 as 2x2y + 2x2y2. 3-convex Γin-sets {v1, v2, v3} {v4} {v2, v3, v4} {v1, v5} {v3, v4, v5} {v2} Table 6: 3-convex subsets of V (P5) and its corresponding Γin-sets. Table 6 shows that there are 2 3-convex subsets of V (P5) with Γin-sets cardinality equal to 1, and 1 3-convex subsets of V (P5) with Γin-sets cardinality equal to 2. This contributes E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 8 of 18 to the convex independent neighborhood polynomial of P5 as 2x3y + x3y2. For 4-convex subsets of V (P5), it can be verified that there are 2 4-convex subset with Γin-sets cardinality equal to one. This contributes to the convex independent neighborhood polynomial of P5 as 2x4y. For 5-convex subsets of V (P5), it can be verified that there is only 1 5-convex subset with empty (zero cardinality) Γin-set. This contributes to the convex independent neighborhood polynomial of P5 as x5. Theorem 4.4. Let Cn be a cycle of order n. Then, for n ≥ 6, the convex independent neighborhood polynomial of Cn is Γcin(Cn;x, y) = xn + n ∑n+1 2 i=1 xiy2, if n is odd xn + n ∑n 2 i=1 x iy2, if n is even. Proof. Let V (Cn) = {v1, v2, . . . , vn} be the vertex set of Cn. We consider the following cases: Case 1: Let n be odd. First, there is only one n-convex subset of V (Cn) with empty (zero cardinality) Γin-sets and this contributes to the term xn of the polynomial. Next, we consider the i-convex subsets of V (Cn) for i = 1, 2, ..., n+1 2 . We only consider subsets less than or equal to n+1 2 because these are the only convex subsets of V (Cn). Subsets more than n+1 2 are no longer convex subsets. Now, for i-convex subsets of Cn such that i = 1, 2, ..., n+1 2 , all of these contains Γin-sets equal to two and each of these i-convex subsets has n choices. Thus, we have the following polynomial nxy2 + nx2y2 + · · ·+ nx n+1 2 y2 = n n+1 2∑ i=1 xiy2. Hence, the convex independent neighborhood polynomial of Cn if n is odd is given by Γcin(Cn;x, y) = xn + n n+1 2∑ i=1 xiy2. Case 2: Let n be even. By similar argument as case 1 and integer i = 1, 2, ..., n2 , we will obtain the convex neighborhood polynomial of Cn, i.e., Γcin(Cn;x, y) = xn + n n 2∑ i=1 xiy2. E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 9 of 18 This complete the proof. ■ Let V (Cn) = {v1, v2, ..., vn} be vertex set of Cn. Note that the vertices {v1, v2, ..., vn} convex subset of V (Cn) is the only subset that has empty (zero cardinality) Γin-set which is the leading term of the convex independent neighborhood polynomial of Cn. Now, consider the following cases, if n is odd, then there are n+1 2 terms with Γin-set cardinality equal to two. This means that, for n ≥ 6 when n is odd, there are 1 + n+ 1 2 = n+ 3 2 terms for the convex independent neighborhood polynomial of Cn. On the other hand, if n is even, then there are n 2 terms with Γin-set cardinality equal to two. This means that, for n ≥ 6 when n is even, there are 1 + n 2 = n+ 2 2 terms for the convex independent neighborhood polynomial of Cn. Thus, we have the following corollary Corollary 4.5. For n ≥ 6, the number of terms of the convex independent neighborhood polynomial of Cn in terms of n is given by,{ n+3 2 , if n is odd n+2 2 , if n is even. Illustration 4.6. Consider the cycle C6. v1 v2 v3 v6 v5 v4 Figure 3: A cycle C6 of order 6 Then, by using Theorem 4.4 when n is even, Γcin(C6;x, y) = x6 + 6 6 2∑ i=1 xiy2 = x6 + 6 3∑ i=1 xiy2 = x6 + 6(xy2 + x2y2 + x3y2) E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 10 of 18 = x6 + 6x3y2 + 6x2y2 + 6xy2. And by Corollary 4.5, there are 6+2 2 = 4 terms in the convex independent neighborhood polynomial of C6. To see the convex subsets of V (C6) and its corresponding Γin-sets, refer to the Tables 7, 8, and 9: 1-convex Γin-sets {v1} {v6, v2} {v2} {v1, v3} {v3} {v2, v4} {v4} {v3, v5} {v5} {v4, v6} {v6} {v5, v1} Table 7: 1-convex subsets of V (C6) and its corresponding Γin-sets. Table 7 shows that there are 6 1-convex subsets of V (C6) with Γin-sets cardinality equal to 2. This contributes to the convex independent neighborhood polynomial of C6 as 6xy2. 2-convex Γin-sets {v1, v2} {v6, v3} {v2, v3} {v1, v4} {v3, v4} {v2, v5} {v4, v5} {v3, v6} {v5, v6} {v4, v1} {v6, v1} {v5, v2} Table 8: 2-convex subsets of V (C6) and its corresponding Γin-sets. Table 8 shows that there are 6 2-convex subsets of V (C6) with Γin-sets cardinality equal to 2. This contributes to the convex independent neighborhood polynomial of C6 as 6x2y2. E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 11 of 18 3-convex Γin-sets {v1, v2, v3} {v6, v4} {v2, v3, v4} {v1, v5} {v3, v4, v5} {v2, v6} {v4, v5, v6} {v3, v1} {v5, v6, v1} {v4, v2} {v6, v1, v2} {v5, v3} Table 9: 3-convex subsets of V (C6) and its corresponding Γin-sets. Table 9 shows that there are 6 3-convex subsets of V (C6) with Γin-sets cardinality equal to 2. This contributes to the convex independent neighborhood polynomial of C6 as 6x 3y2. For both 4-convex and 5-convex subsets of V (C6), it can be verified that there are no 4-convex and 5-convex subsets of V (C6) since any subsets of C6 that contains four or more elements is no longer convex sets. For 6-convex subsets of V (C6), it can be verified that there is only 1 6-convex subset of V (C6) with empty (zero cardinality) Γin-set. This contributes to the convex independent neighborhood polynomial of C6 as x6. 5. Complete Graph and Star Graph This section discusses the convex independent neighborhood polynomial of complete graph (Kn) and star graph (K1,n). Theorem 5.1. Let Kn be a complete graph of order n. Then, the convex independent neighborhood polynomial of Kn is Γcin(Kn;x, y) = xn + n−1∑ i=1 ( n i ) xiy where n ≥ 3, ( n i ) is the number of i-convex subsets of V (Kn) with maximum independent neighborhood system cardinality equal to 1 which is the combination of n vertices taken i at a time. Proof. Let V (Kn) = {v1, v2, . . . , vn} be vertex set of Kn. First, note that there is only one n-convex subset of V (Kn) which has empty (zero cardinality) Γin-sets. This contributes to xn. Now, for integer i = 1, 2, ..., n − 1, there always exist an i-convex subsets of V (Kn). This means that the Γin-sets of i-convex subsets of V (Kn) contains exactly one element, for all i = 1, 2, ..., n − 1 since every vertices are connected to each other. Moreover, there are ( n i ) i-convex subsets of V (Kn) whose Γin-sets contain exactly one element. E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 12 of 18 Therefore, the convex independent neighborhood polynomial of Kn is Γcin(Kn;x, y) = xn + n−1∑ i=1 ( n i ) xiy. ■ Let V (Kn) = {v1, v2, ..., vn} be vertex set of complete graph Kn. Note that the vertices {v1, v2, ..., vn} is the n-convex subset of V (Kn) which contributes to the leading term of the convex independent neighborhood polynomial of Kn. Now, for i = 1, ..., n − 1, the i-convex subsets of V (Kn) has Γin-sets cardinality equal to one. This means that for n ≥ 3, there are 1 + (n− 1) = n terms for the convex independent neighborhood polynomial of Kn. Thus, we have the following corollary Corollary 5.2. For n ≥ 3, the number of terms of the convex independent neighborhood polynomial of Kn is n. Illustration 5.3. Consider K4 be a complete graph of order 4. v1 v2 v3v4 Figure 4: A complete graph K4 of order 4 Then, by using Theorem 5.1, Γcin(K4;x, y) = x4 + 4−1∑ i=1 ( 4 i ) xiy = x4 + 3∑ i=1 ( 4 i ) xiy = x4 + [( 4 1 ) xy + ( 4 2 ) x2y + ( 4 3 ) x3y ] = x4 + 4x3y + 6x2y + 4x3y. And by Corollary 5.2, there are n = 4 terms in the convex independent neighborhood polynomial of K4. E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 13 of 18 To see the convex subsets of V (K4) and its corresponding Γin-sets, refer to the Tables 10, 11, and 12: 1-convex Γin-sets {v1} {v2}, {v3}, {v4} {v2} {v1}, {v3}, {v4} {v3} {v1}, {v2}, {v4} {v4} {v1}, {v2}, {v3} Table 10: 1-convex subsets of V (K4) and its corresponding Γin-sets. Table 10 shows that there are 4 1-convex subsets of V (K4) with Γin-sets cardinality equal to 1. This contributes to the convex independent neighborhood polynomial of K4 as 4xy. 2-convex Γin-sets {v1, v2} {v3}, {v4} {v2, v3} {v1}, {v4} {v3, v4} {v1}, {v2} {v4, v1} {v2}, {v3} {v1, v3} {v2}, {v4} {v2, v4} {v1}, {v3} Table 11: 2-convex subsets of V (K4) and its corresponding Γin-sets. Table 11 shows that there are 6 2-convex subsets of V (K4) with Γin-sets cardinality equal to 1. This contributes to the convex independent neighborhood polynomial of K4 as 6x2y. 3-convex Γin-sets {v1, v2, v3} {v4} {v2, v3, v4} {v1} {v1, v2, v4} {v3} {v1, v3, v4} {v2} Table 12: 3-convex subsets of V (K4) and its corresponding Γin-sets. Table 12 shows that there are 4 3-convex subsets of V (K4) with Γin-sets cardinality equal to 1. This contributes to the convex independent neighborhood polynomial of K4 as 4x3y. For the 4-convex subsets of V (K4), it can be verified that there is only 1 4-convex subset of V (K4) with empty (zero cardinality) Γin-set. This contributes to the convex independent neighborhood polynomial of K4 as x4. E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 14 of 18 Theorem 5.4. Let K1,n be a star graph of order n + 1. Then, the convex independent neighborhood polynomial of K1,n is Γcin(K1,n;x, y) = xn+1 + n∑ i=2 ( n i− 1 ) xiy[n−(i−1)] + xyn + nxy, where n ≥ 3, ( n i−1 ) is the number of i-convex subsets of V (K1,n) with maximum independent neighborhood system cardinality equal to [n− (i−1)] which is the combination of n vertices taken (i− 1) at a time. Proof. Let V (K1,n) = {u1, v1, v2, ..., vn} be a vertex set of star graph of order K1,n and let u1 be the center vertex. First, note that every n vertices are all adjacent only to the center vertex, namely, u1. This means that there are exactly n 1-convex subset of V (K1,n) with Γin-set contain only one element, namely u1. This contribute to the convex independent neighborhood polynomial of K1,n as nxy. Also, there is only 1 1-convex subset of V (K1,n) with Γin-set contain n elements, namely u1, the center vertex. This contribute to the polynomial as xyn. Now, for (n + 1)-convex subset of V (K1,n), there is exactly one (n + 1)-convex with empty (zero cardinality) Γin-set which contributes as xn+1 to the polynomial. Now, for i-convex subsets of V (K1,n) where i = 2, ..., n, there are( n i−1 ) i-convex subsets of V (K1,n) with Γin-sets contain [n − (i − 1)] elements. Thus, by combining all i-convex with Γin-sets cardinality equal to [n− (i− 1)] we have( n 1 ) x2yn−1 + ( n 2 ) x3yn−2 + · · ·+ ( n n− 1 ) xny = n∑ i=2 ( n i− 1 ) xiyn−(i−1) Therefore, the convex independent neighborhood polynomial of K1,n is Γcin(K1,n;x, y) = xn+1 + n∑ i=2 ( n i− 1 ) xiy[n−(i−1)] + xyn + nxy. ■ Let V (K1,n) = {u1, v1, v2, ..., vn} be a vertex-set of star graph of order K1,n and let u1 be the center vertex. Note that every n vertices are all adjacent only to the center vertex, namely, u1. This means that the n 1-convex subsets of V (K1,n) with Γin-sets cardinality equal to one contribute as the nxy term in the polynomial. Moreover, there is only 1 1-convex subset of V (K1,n) with Γin-sets cardinality equal to n, i.e., u1 which contribute to the polynomial as xyn. Now, the vertices {u1, v1, ..., vn} is the (n+1)-convex subset of V (K1,n) which contributes to the leading term of the convex independent neighborhood polynomial of K1,n, i.e., xn+1. Now, for i = 2, ..., n, the i-convex subsets of V (K1,n) contains Γin-sets [n− (i− 1)] elements. This means that for n ≥ 3, there are 1 + 1 + 1 + (n− 1) = n+ 2 terms for the convex independent neighborhood polynomial of K1,n. Thus, we have the following corollary E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 15 of 18 Corollary 5.5. For n ≥ 3, the number of terms of the convex independent neighborhood polynomial of K1,n is (n+ 2). Illustration 5.6. Consider K1,4 be a star graph of order 5. u1 v1 v2 v4 v3 Figure 5: A star graph K1,4 of order 5 Then, by using Theorem 5.4, Γcin(K1,4;x, y) = x4+1 + 4∑ i=2 ( 4 i− 1 ) xiy[4−(i−1)] + xy4 + 4xy = x5 + [( 4 1 ) x2y3 + ( 4 2 ) x3y2 + ( 4 3 ) x4y ] +xy4 + 4xy = x5 + 4x2y3 + 6x3y2 + 4x4y + xy4 + 4xy = x5 + 4x4y + 6x3y2 + 4x2y3 + xy4 + 4xy. And by Corollary 5.5, there are 4 + 2 = 6 terms in the convex independent neighborhood polynomial of K1,4. To see the convex subsets of V (K1,4)and its corresponding Γin-sets, refer to the following Tables 13, 14, and 15: E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 16 of 18 1-convex Γin-sets {u1} {v1, v2, v3, v4} {v1} {u1} {v2} {u1} {v3} {u1} {v4} {u1} Table 13: 1-convex subsets of V (K1,4) and its corresponding Γin-sets. Table 13 shows that there are 4 1-convex subsets of V (K1,4) with Γin-set cardinality equal to 1 and exactly 1 1-convex subset of V (K1,4) with Γin-set cardinality equal to 4. This contributes to the convex independent neighborhood polynomial of K1,4 as xy4 + 4xy. 2-convex Γin-sets {v1, u1} {v2, v3, v4} {v2, u1} {v1, v3, v4} {v3, u1} {v1, v2, v4} {v4, u1} {v1, v2, v3} Table 14: 2-convex subsets of V (K1,4) and its corresponding Γin-sets. Table 14 shows that there are 4 2-convex subsets of V (K1,4) with Γin-set cardinality equal to 3. This contributes to the convex independent neighborhood polynomial of K1,4 as 4x2y3. 3-convex Γin-sets {v1, v2, u1} {v3, v4} {v1, v3, u1} {v2, v4} {v1, v4, u1} {v2, v3} {v2, v3, u1} {v1, v4} {v2, v4, u1} {v1, v3} {v3, v4, u1} {v1, v2} Table 15: 3-convex subsets of V (K1,4) and its corresponding Γin-sets. Table 15 shows that there are 6 3-convex subsets of V (K1,4) with Γin-set cardinality equal to 2. This contributes to the convex independent neighborhood polynomial of K1,4 as 6x3y2. For 4-convex subsets of V (K1,4), it can be verified that there are 4 4-convex subsets of V (K1,4) with Γin-set cardinality equal to 1. This contributes to the convex independent neighborhood polynomial of K1,4 as 4x4y. E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 17 of 18 For 5-convex subset of V (K1,4), there is only 1 5-convex subset of V (K1,4) with empty (zero cardinality) Γin-set. This contributes to the convex independent neighborhood polynomial of K1,4 as x5. 6. Conclusion The study of graph polynomials and convexity in graphs continues to be a significant area of research in graph theory, offering valuable insights and applications across various scientific fields. Researchers have investigated new approaches to count and describe substructures based on their neighborhood system by combining the ideas of convexity with graph polynomials. In this paper, we have extended this line of study by considering independent neighborhood systems of convex subgraphs, which leads to the introduction of the convex independent neighborhood polynomial for paths, cycles, complete and star graph. This new polynomial provides a new way to look at how convexity and neighborhood structures work together, creating a foundation for future graph theory researches. Acknowledgements The authors would like to thank Department of Science and Technology - Accelerated Science and Technology Human Resource Development Program (DOST-ASTHRDP), Philippines and MSU-Iligan Institute of Technology (Iligan City, Philippines) for funding this research. References [1] J.A. Ellis-Monaghan and C. Merino. Graph polynomials and their applications ii: Interrelations and interpretations. Structural analysis of complex networks, pages 257–292, 2011. [2] J. Brown and R. Nowakowski. The neighbourhood polynomial of a graph. Australas. J Comb., 42:55–68, 2008. [3] S. Dagondon N.S Abdulcarim and E. Chacon. On the independent neighborhood polynomial of the cartesian product of some special graphs. European Journal of Pure and Applied Mathematics, 14(1):173–191, 2021. [4] M. Berger. Convexity. The American Mathematical Monthly, 97(8):650–678, 1990. [5] F. Harary Frank and J. Nieminen. Convexity in graphs. Journal of Differential Geometry, 16(2):185–190, 1981. [6] L. Laja and R. Artes Jr. Zeros of convex subgraph polynomials. Appl. Math. Sci, 8(59):2917–2923, 2014. [7] L. Laja and R. Artes Jr. Convex subgraph polynomials of the join and the composition of graphs. International Journal of Mathematical Analysis, 10(11):515–529, 2016. E.J. Aguilon, S. Dagondon, R. Artes / Eur. J. Pure Appl. Math, 18 (2) (2025), 5978 18 of 18 [8] A. Arriesgado and R. Artes Jr. Convex independent common neighborhood polyno- mial of a graph. Advances and Applications in Discrete Mathematics, 38:145–158, 04 2023. [9] J.I. Salim S. Abdurasid, B. Amiruddin and R. Artes Jr. Convex neighborhood poly- nomial of graphs. Advances & Applications in Discrete Mathematics, 40(1), 2023. [10] A. Fuentes. ALGEBRA. A Mathematical Analysis Preliminary to Calculus. Lulu. com, 2016.