EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 17, No. 3, 2024, 1779-1803 ISSN 1307-5543 – ejpam.com Published by New York Business Global On the k-restricted Intersection Graph Mariane Eliz D. Pelagio1∗, Kathlen C. Mendoza1, Neil M. Mame1 1 College of Arts and Sciences, Batangas State University - The National Engineering University, Batangas City, Batangas, Philippines Abstract. The problem of intersection graphs was introduced by Szpilrajn-Marczewski in 1945. This study introduces a new variant of the intersection graph, called the k-restricted intersection graph. Let Sn be a nonempty n-element set, for some positive integer n, and let S(n,k) be the set of all the k-element subsets of Sn where 0 ≤ k ≤ n. A k-restricted intersection graph, denoted by GS(n,k) , is a graph with vertex set S(n,k) such that two vertices A,B ∈ S(n,k) are adjacent whenever A ∩ B ̸= ∅ and A ̸= B. Here, we determined the order and size of GS(n,k) . Moreover, some parameters such as independence number, domination number, and isolate domination number of the k-restricted intersection graph were established. Finally, necessary and sufficient conditions for a GS(n,k) to be isomorphic to the cycle graph and complete graph were determined. 2020 Mathematics Subject Classifications: 05C62, 05C69 Key Words and Phrases: Intersection Graph, k-restricted Intersection Graph, k-element Subsets 1. Introduction Graph theory has been linked to some areas of mathematics such as set theory. Specif- ically, the utilization of family sets as vertices of graphs was one of the examples of as- sociating set theory with graph theory as stated by Golumbic, M. (1980) in his study “Algorithmic Graph Theory and Perfect Graphs” [5]. For instance, some of the special types of graphs like the Hamming graph by Richard Hamming and the Johnson graph by Selmer M. John were both derived from the system of sets and were being used in coding theory–which was also a field of mathematics [1]. Connecting the concept of a set to graph theory paved the way for the introduction of intersection graphs. An intersection graph contained a family of sets as its vertices and each vertices were connected by an edge whenever the sets had a nonempty intersection. This graph was introduced by Szpilrajn-Marczewski (1945) in their paper entitled “On Two Properties of Set Classes”[14], wherein they also asserted that all graphs may be ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v17i3.5240 Email addresses: marianeeliz.pelagio@g.batstate-u.edu.ph (M.E. Pelagio), kathlen.mendoza@g.batstate-u.edu.ph (K. Mendoza), neil.mame@g.batstate-u.edu.ph (N. Mame) https://www.ejpam.com 1779 © 2024 EJPAM All rights reserved. M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1780 represented as an intersection graph. This was proven and supported by Erdős, Goodman, and Pósa in 1966 in their study “The Representation of a Graph by Set Intersections”[10]. In this study, they provided a more efficient construction of an intersection graph and defined the total number of set elements which required a smaller number of vertices. Furthermore, variations on intersection graphs was also introduced as most of these were derived from sets on some kind of geometric configuration which was specified in [11]. Some of these were the circle graph (or the intersection graph from the chords of a circle), string graph (the intersection graph of curves on a plane), and circular arc graph (intersection graph derived from the arcs of the circle)[15], to name a few. The assertion that all graphs can be represented as an intersection graph is an interest- ing concept. Since the majority of the intersection graphs that are discovered employ the usage of sets in the field of geometry, this gives the motivation to introduce and explore a related study adopting the area of set theory. Specifically, finding an intersection graph which is restricted to all the k-element subsets of an n-element set, where n is a positive integer and k is a nonnegative integer such that k ≤ n. Hence, by using the concepts of k-element subsets and intersection graphs, this paper introduces a k-restricted intersection graph, which is an additional variation of an intersection graph. To determine this graph, its vertex set contains all the k-element subsets of an n-element set and two vertices are adjacent if they have a nonempty intersection. With these notions, it can be gleaned that the difference between an intersection graph and a k-restricted intersection graph is their vertex set wherein the first graph contains nonempty family of sets while the second one involves the collection of all k-element subsets of a set. This study introduces a new variant of the intersection graph which is the k-restricted intersection graph. The formal definition of this graph is presented in Chapter 3. Also, this study provides the conditions when a k-restricted intersection graph is isomorphic to some special classes of graph. Lastly, some of the graph parameters are determined such as the order, size, independence number, domination number, and isolate domination number. 2. Preliminaries Some necessary definitions of sets, combinations and subsets, and graph theory are presented in this section. Also, the discussion includes known theorems from combinatorics and graph theory and is presented without proof. 2.1. Combination and Subsets This section contains the concept of applying the method of combination in enumerat- ing subsets. Also, the notions of sets and subsets discussed were employed. The references used are found in [3], [4], and [8]. A set S is a collection of distinct well-defined objects where an ‘object’ is a generic term that refers to elements (or members) of the set. The cardinality of S, denoted by |S|, refers to the number of elements of S. If x is an element of S, then we write x ∈ S, M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1781 otherwise, x /∈ S. Also, if S has no elements, then S is called an empty set and is written as S = ∅. Now, If S is an n-element set, then we can rewrite this as Sn. In the succeeding discussions, sets with indicated cardinality shall be denoted as Sn. Definition 1. Let S and T be sets. Then T is a subset of S, written T ⊆ S, if for all x ∈ T , then x ∈ S. A power set of S, denoted by P(S), is the set containing all the subsets of S. Note that a set is also a subset of itself. Now, let S and T be nonempty sets. The difference between S and T , written S \T and read as “S minus T”, is the set containing all elements of S that are not in T . There is no defined cardinality for a generalized difference between two sets. However, if we get the difference between a set and its subset, then we can easily tell the cardinality of their difference. Remark 1. Let S and T be nonempty sets. If T ⊆ S, then |S \ T | = |S| − |T |. Consider the nonempty sets S and T . The intersection of S and T , denoted by S∩T , is defined as the set containing all the elements that belong to both S and T . If two sets do not have any element(s) in common, then we call this as an empty intersection, denoted by S ∩ T = ∅. Otherwise, we write as S ∩ T ̸= ∅ and refer this as a nonempty intersection. We now introduce the notion of binomial coefficient. For the integers n, k ≥ 0, and 0 ≤ k ≤ n, the binomial coefficient is given by( n k ) = n! k!(n− k)! . Note that the number ( n k ) , read as “n choose k”and also called as a combination or combinatorial formula, is the number of ways choosing k unordered outcomes from n possibilities. We will utilize this formula to count how many k-element subsets can be formed from Sn. Remark 2. The binomial coefficient ( 0 0 ) is equal to 1. Remark 2 discusses the trivial case for the binomial coefficient. Now, consider the 0-element set S0 = ∅. Observe that the only subset that every S0 has empty subset. By this, we will also consider the 0-element set S0 as a trivial case. Remark 3. The only subset of S0 is ∅. Given Remark 3, Sn with n = 0 will be regarded as a trivial case for the set Sn. With this, the proceeding discussions shall now be focused on the n-element set Sn where n is a positive integer. Theorem 1. For any positive integer n, ( n k ) = 1 if and only if k = 0 or k = n. Theorem 1 is the boundary values for the recursive formula of the binomial coefficient. The readers may refer to [2] for the proof of Theorem 1. M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1782 Definition 2. Let Sn be an n-element set where n is a positive integer and let k be a nonnegative integer such that k ≤ n. Then the set containing all k-element subsets of Sn, written as S(n,k), is the set containing all the subsets of Sn having k-elements. Since this study does not consider multiset, it follows that S(n,k) contains the distinct k-subsets of Sn. Moreover, by utilizing the binomial coefficient, we define the cardinality of the set S(n,k) be equal to the number ( n k ) where n is a positive integer and k is a nonnegative integer. Given that |S(n,k)| = ( n k ) , it can be observed that we cannot form a k-element subset from Sn when n < k. Thus S(n,k) = ∅ which implies that |S(n,k)| = ( n k ) = 0. Equivalently, we have Remark 4. Remark 4. If n < k, then ( n k ) = 0. 2.2. Graph Theory This section discusses some basic concepts in graph theory. We adapt the definitions in [9] for the concepts used here. Also, the references [6], [7], [12], and [13] are utilized. A graph, denoted by G, is an ordered pair G = (V (G), E(G)) where the vertex set V (G) is a nonempty set of elements called vertices and the edge set E(G) is a set of unordered pairs of vertices called edges. We write the edges of a graph G as [x, y] for x, y ∈ V (G). The edges of G are said to be unordered pairs so we also say that [x, y] = [y, x]. Moreover, the number |V (G)| is called the order of G while the number |E(G)| is referred to as the size of G. A graph of order n ≥ 1 having no edges is called an empty graph, denoted as Kn. Furthermore, a graph with only one vertex is referred to as a trivial graph. It was taken into consideration that a graph with an empty edge set is still considered as a graph. However, note that if V (G) = ∅, then G here is undefined since we cannot form a graph with no vertices. The degree of vertex x ∈ V (G), denoted by deg(x), is the number of edges adjacent to the vertex x. If the vertex x has deg(x) = 0, then x is called an isolated vertex. Meaning to say, an isolated vertex is a vertex that is not adjacent to any other vertex of G. There are times when the degrees of every vertex help determine the size of a graph specifically if the degrees are the same in number. In this regard, we say that a graph with the same number of degrees for every vertex is a regular graph. A graph G is regular if every vertex has the same degree. Moreover, G is said to be regular of degree r (or r-regular) if deg(x) = r for all vertices x in G. The size of an r-regular graph can be determined as follows:∑ x∈V (G) deg(x) = 2m nr = 2m m = nr 2 (1) M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1783 provided that nr is even. Let W : x1, x2, ..., xk, xk+1 be a walk of length k > 0. This walk is closed if x1 = xk+1. Moreover, a closed walk is called a cycle if the vertices x1, x2, ..., xk are distinct. A graph G of order n ≥ 3 is called a cycle graph of order n, denoted by Cn, if the vertices of G are labeled x1, x2, ..., xn so that the edges [x1, x2], [x2, x3], ..., [xn−1, xn], [xn, x1] form a cycle. It is noted that the order and size of a Cn is n. A graph of order n is said to be a complete graph of order n, denoted by Kn, if every vertex is adjacent to every other vertex. Since every vertex of Kn is adjacent to every vertex of this graph it follows that the degrees of every vertex are equal to n − 1, since we consider a simple graph Kn having no loops and multiple edges. This implies that Kn is an (n−1)-regular graph. Now, to determine the size of Kn, by utilizing Equation(1), we have m = nr 2 m = n(n− 1) 2 . Observe that m is always defined since the product of the consecutive integers n and n−1 is even. Any cycle graph, in particular, C3 whose order and size are equal to 3, is a 2-regular graph. Furthermore, a complete graph of order 3, which is a (3−1) = 2-regular graph, has size equal to 3. Now, it can be observed that C3 and K3 have the same number of order, size, and degree of every vertex. Through the notion of graph isomorphism, denoted by ≃, it can be seen that there exists an isomorphism regarding the two graphs. Remark 5. Let C3 and K3 be a cycle and complete graphs of order 3, respectively. Then C3 ≃ K3. Definition 3. Let T = {T1, T2, ..., Tm} be a nonempty collection of sets. A graph G is called an intersection graph whose V (G) = T and [Ti, Tj ] ∈ E(G) for 1 ≤ i, j ≤ m, where i ̸= j is an edge in G if they have a nonempty intersection. For every intersection graph G, we have |V (G)| = |T |, where T is a nonempty family of sets. To date, there is no defined size for a generalized intersection graph. Example 1. Consider the intersection graph G over the set T = {{1, 2, 3}, {2, 4}, {1, 3}}. It can be observed that the order of G is 3. Also, since {1, 2, 3} ∩ {2, 4} = {2} and {1, 2, 3}∩{1, 3} = {1, 3} both contain nonempty intersection it follows that [{1, 2, 3}, {2, 4}] and [{1, 2, 3}, {1, 3}] are edges of G. Moreover, {2, 4} and {1, 3} has no intersection, so [{2, 4}, {1, 3}] is not in E(G). By these, then E(G) = { [{1, 2, 3}, {2, 4}], [{1, 2, 3}, {1, 3}] } . Shown in Figure 1 is a pictorial illustration of the intersection graph over the set T = {{1, 2, 3}, {2, 4}, {1, 3}}. M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1784 {2, 4} {1, 3}{1, 2, 3} Figure 1: An Illustration of the Intersection Graph of the Set T . Consider a graph G. The complement of G, denoted by G, is the graph whose vertex set is V (G) and such that for every pair x, y ∈ V (G), [x, y] is an edge of G if and only if [x, y] is not an edge of G. Recall that the degree of every vertex in a regular graph is equal in number. This can infer that the vertices in a complement graph of a regular graph yield also a degree that is equal in number. In sum, the complement graph of a regular graph is considered a regular graph. Definition 4. Let G be a graph. The nonempty set T ⊆ V (G) is called an independent set in a graph G if for every x, y ∈ T , then [x, y] /∈ E(G). The independence number of a graph, denoted by α(G), is the cardinality of the largest independent set of G. In a graph G, if there exists an independent set T ⊆ V (G), it follows that α(G) ≥ |T |. The next theorem determines the independence number of a complete graph of order n. Definition 5. Let G = (V (G), E(G)) be a graph. A nonempty subset T of V (G) is called the dominating set of G if every element of V (G) \ T is adjacent to some element of T . Moreover, the domination number, written as γ(G), of a graph G is the minimum cardinality among all the dominating sets of G. The vertex set V (G) of a graph G is a dominating set since V (G) \ V (G) = ∅ which implies that there are no other vertices that are needed to be considered. A graph H is called a subgraph of a graph G, written H ⊆ G, if V (H) ⊆ V (G) and E(H) ⊆ E(G). Moreover, a subgraph H of a graph G is called an induced-subgraph (also called a “vertex-induced subgraph”), written as < H >, if whenever x, y ∈ H and [x, y] ∈ E(G), then [x, y] is an edge of < H >. Definition 6. A dominating set T is called an isolate dominating set if the subgraph induced by T on graph G has at least one isolated vertex. An isolate domination num- ber, denoted by γ0, has the minimal cardinality among all the isolate dominating sets of G. Note that the domination number must be the smallest among the cardinality of the domination sets of V (G). By this, the isolate domination number is always equal to or greater than the domination number. Also, note that if there exists an isolate dominating set in G, say T ⊆ V (G), then γ(G) ≤ γ0(G) ≤ |T |. 3. The k-restricted Intersection Graph Recall that S(n,k) is the collection of all k-element subsets of Sn. From Remark 3, it was regarded that S0 is a trivial case such that S(0,0) = {∅}. Then, S(0,0) is considered a trivial case for a k-restricted intersection graph. As a result, the 0-restricted intersection graph of S0 is a trivial graph containing the vertex ∅. M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1785 Throughout the succeeding discussion, we shall consider n as a positive integer for Sn and a nonnegative integer k such that k ≤ n. Definition 7. Let Sn be an n-element set where n is a positive integer, let k ≤ n be a nonnegative integer, and let S(n,k) be the collection of all k-element subsets of Sn. A k-restricted intersection graph, denoted by GS(n,k) , is the graph whose vertex set is S(n,k) and two vertices A and B are adjacent whenever A ∩B ̸= ∅ and A ̸= B. The elements of V (GS(n,k) ) are the k-subsets of Sn so for every A ∈ V (GS(n,k) ), |A| = k. Moreover, an unordered pair of vertex [A,B] ∈ E(GS(n,k) ) if A and B have a nonempty intersection and A andB are distinct. Although for every nonempty subset A ∈ V (GS(n,k) ), A ∩ A = A, it can be observed that every edge in GS(n,k) should contain distinct vertices so GS(n,k) does not contain any loops. Now, given in Example 2 is an example for GS(n,k) of a 4-element set S4 where k = 2. Example 2. Let S4 = {x1, x2, x3, x4} and let k = 2. Then GS(4,2) has the vertex set V (GS(4,2) ) = { {x1, x2}, {x1, x3}, {x1, x4}, {x2, x3}, {x2, x4}, {x3, x4} } . Now, observe that {x2, x3}∩{x2, x4} = {x2}, so [{x2, x3}, {x2, x4}] ∈ E(GS(4,2) ). Also, {x1, x2} ∩ {x1, x3} = {x1} which implies that [{x1, x2}, {x1, x3}] is also an edge of GS(4,2) . However, the vertices {x1, x2} and {x3, x4} bear an empty intersection so they are not adjacent to each other. To enumerate the edges of GS(4,2) , we have: E(GS(4,2) ) = { [{x1, x2}, {x1, x3}], [{x1, x2}, {x1, x4}], [{x1, x2}, {x2, x3}], [{x1, x2}, {x2, x4}], [{x1, x3}, {x1, x4}], [{x1, x3}, {x2, x3}], [{x1, x3}, {x3, x4}], [{x1, x4}, {x2, x4}], [{x1, x4}, {x3, x4}], [{x2, x3}, {x2, x4}], [{x2, x3}, {x3, x4}], [{x2, x4}, {x3, x4}] } . It can be observed that the order of GS(4,2) is 6 and its size is 12. The graph illustrated in Figure 2 is a pictorial representation of GS(4,2) . Since [A,A] /∈ E(GS(n,k) ), it follows that a k-restricted intersection graph does not contain any loop. Also, note that V (GS(n,k) ) is the set containing the distinct k-subsets of Sn, this means that E(GS(n,k) ) is not a multiset. Hence, GS(n,k) has no multiple edges. Remark 6. A k-restricted intersection graph GS(n,k) is a simple graph. Theorem 2 determines the order of a GS(n,k) . Recall that the order of a graph refers to the cardinality of its vertex set. Theorem 2. Let GS(n,k) be a k-restricted intersection graph. Then the order of GS(n,k) is( n k ) . Proof. Assume GS(n,k) is a k-restricted intersection graph. By Definition 7, V (GS(n,k) ) is equal to S(n,k). Since |S(n,k)| = ( n k ) , it follows that |V (GS(n,k) )| = ( n k ) . The number ( n k ) provided that n a positive integer and k is nonnegative, has a positive integer value. Meaning to say, V (GS(n,k) ) is nonempty for all n and k. Therefore, GS(n,k) is defined for all the given values of n and k. M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1786 {x1, x2} {x3, x4} {x1, x3} {x2, x4} {x1, x4} {x2, x3} Figure 2: A 2-Restricted Intersection Graph GS(4,2) . Illustration 1. Let GS(4,2) be a 2-restricted intersection graph over the 4-element set S4 = {x1, x2, x3, x4} whose graph is pictorially represented in Figure 2. We see that |V (GS(4,2) )| = 6. To verify this by utilizing Theorem 2, since n = 4 and k = 2, it follows that |V (GS(4,2) )| = ( 4 2 ) = 6. There are instances that a GS(n,k) is a trivial graph. Meaning to say, GS(n,k) has only one vertex. Note that from Theorem 1, ( n k ) = |V (GS(n,k) )| = 1 if and only if k = 0 or k = n. Theorem 3 discusses GS(n,k) when k is 0 or n. Theorem 3. Let Sn be an n-element set. Then GS(n,k) is a trivial graph if and only if k = 0 or k = n. Proof. Let GS(n,k) be a trivial graph. Hence, we have |V (GS(n,k) )| = 1. Since the order of GS(n,k) is equal to ( n k ) , hence we have ( n k ) = 1. By Theorem 1, k is either 0 or n. Conversely, assume that k = 0 or k = n. If k = 0, then S(n,0) = {∅} which implies that V (GS(n,0) ) = {∅}. An empty subset has no element to consider so it does not intersect to itself. It follows that E(GS(n,0) ) is empty. Thus, GS(n,0) is a trivial graph. Moreover, if k = n, then S(n,n) = {Sn} meaning, V (GS(n,n) ) = {Sn}. This implies that GS(n,n) has only one vertex. By Remark 6, [Sn,Sn] /∈ E(GS(n,n) ) so E(GS(n,n) ) = ∅. Therefore, GS(n,n) is also a trivial graph. Illustration 2. Let S4 = {x1, x2, x3, x4}. If k = 0, then V (GS(4,0) ) = {∅}. Furthermore, if k = 4, then V (GS(4,4) ) = { {x1, x2, x3, x4} } . Pictorial representations of GS(4,0) and GS(4,4) are presented in Figure 3. For every GS(n,k) , if k = 1, then V (GS(n,1) ) contains the distinct 1-element subsets of Sn. Discussed in Theorem 4 is a GS(n,k) when k = 1. Theorem 4. Let Sn = {x1, x2, ..., xn} be an n-element set. If k = 1, then GS(n,1) is an empty graph of order n. M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1787 ∅ {x1, x2, x3, x4} Figure 3: Illustrating GS(4,0) (Left) and GS(4,4) (Right). Proof. If k = 1, then V (GS(n,1) ) = {{x1}, {x2}, ..., {xn}}. It can be observed that for all 1 ≤ i, j ≤ n and i ̸= j, {xi} ∩ {xj} = ∅. This implies that every vertex in GS(n,1) is not adjacent to each other. Hence, GS(n,1) is an empty graph. Note that |V (GS(n,1) )| = ( n 1 ) = n, which implies that GS(n,1) is an empty graph of order n. Note that all trivial graphs are empty graphs while not every empty graphs are trivial graphs. Hence, GS(n,n) and GS(n,0) are also empty graphs. Illustration 3. Let S4 = {x1, x2, x3, x4} and consider k = 1. Then, V (GS(4,1) ) ={ {x1}, {x2}, {x3}, {x4} } . It can be observed that the 1-element subsets have no element in common. Thus, E(GS(4,1) ) = ∅ which means that GS(4,1) is an empty graph of order 4. Shown in Figure 4 is a pictorial representation of GS(4,1) of S4. {x1} {x3}{x2} {x4} Figure 4: Pictorial Illustration of GS(4,1) . The degree of every vertex in GS(n,k) depends on the value of the nonnegative integer k. Lemma 1 determines the degree of every vertex in a GS(n,k) when 1 ≤ k ≤ ⌊ n 2 ⌋ . Lemma 1. Let Sn be an n-element set and let GS(n,k) be a k-restricted intersection graph. Then for all A ∈ V (GS(n,k) ), deg(A) = ( n k ) − [( n−k k ) + 1 ] if and only if 1 ≤ k ≤ ⌊ n 2 ⌋ . Proof. Assume deg(A) = ( n k ) − [( n−k k ) + 1 ] for all A in V (GS(n,k) ) and suppose that k = 0 or ⌊ n 2 ⌋ < k ≤ n. If k = 0, ( n 0 ) − [( n−0 0 ) + 1 ] = 1 − (1 + 1) = −1. This is a contradiction since the degree of a vertex cannot be a negative integer. If ⌊ n 2 ⌋ < k ≤ n, then n − k ≤ ⌊ n 2 ⌋ . Since n − k ≤ ⌊ n 2 ⌋ < k which implies that n − k < k, by Remark 4, it follows that ( n−k k ) = 0. Hence, deg(A) = ( n k ) − (0 + 1) = ( n k ) − 1. This is a contradiction to the assumption that deg(A) = ( n k ) − [( n−k k ) + 1 ] . Therefore, 1 ≤ k ≤ ⌊ n 2 ⌋ . Conversely, assume that 1 ≤ k ≤ ⌊ n 2 ⌋ and let A be an arbitrary vertex of V (GS(n,k) ). Since A ⊆ Sn, then by Remark 1, it follows that |Sn \ A| = n − k. Now, let S(n−k,k) be a set containing all the k-element subsets of Sn \ A. Observe that S(n−k,k) ⊆ V (GS(n,k) ). If 1 ≤ k ≤ ⌊ n 2 ⌋ , then ⌊ n 2 ⌋ ≤ n− k. This implies that k ≤ n− k so |S(n−k,k)| = ( n−k k ) . Note that A ∩ (Sn \A) = ∅. Hence, for every B ∈ S(n−k,k), A ∩ B = ∅. This means that A is not adjacent to ( n−k k ) elements of V (GS(n,k) ). By Theorem 2, since |V (GS(n,k) )| = ( n k ) , it follows that deg(A) = ( n k ) − ( n−k k ) . Additionally, by Remark 6, [A,A] /∈ E(GS(n,k) ). This M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1788 implies that deg(A) = ( n k ) − [( n−k k ) + 1 ] . Since A was arbitrarily chosen, it follows that every vertex of GS(n,k) , with 1 ≤ k ≤ ⌊ n 2 ⌋ , has degree equal to ( n k ) − [( n−k k ) + 1 ] . Illustration 4. Let S5 = {x1, x2, x3, x4, x5} and let k = 2. The vertex set of GS(5,2) is given by V (GS(5,2) ) = { {x1, x2}, {x1, x3}, {x1, x4}, {x1, x5}, {x2, x3}, {x2, x4}, {x2, x5}, {x3, x4}, {x3, x5}, {x4, x5} } A pictorial representation of the graph GS(5,2) is shown in Figure 5. {x1, x2} {x3, x5} {x1, x4} {x3, x4} {x1, x5} {x2, x4} {x1, x3} {x2, x3} {x4, x5} {x2, x5} Figure 5: A Pictorial Representation of GS(5,2) . It can be observed that the degree of every vertex in GS(5,2) is 6. Note that k = 2 which implies that k ≤ ⌊ 5 2 ⌋ = 2. By using Lemma 1 with n = 5 and k = 2, the degree of each A ∈ V (GS(5,2) ) is given by deg(A) = ( n k ) − [( n− k k ) + 1 ] = ( 5 2 ) − [( 5− 2 2 ) + 1 ] = ( 5 2 ) − [( 3 2 ) + 1 ] = 10− (3 + 1) = 6. M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1789 Furthermore, Lemma 2 shows the degree of every vertex in GS(n,k) if and only if k = 0 or ⌊ n 2 ⌋ < k ≤ n. Lemma 2. Let Sn be an n-element set and let GS(n,k) be a k-restricted intersection graph. Then deg(A) = ( n k ) − 1 for all A ∈ V (GS(n,k) ) if and only if k = 0 or ⌊ n 2 ⌋ < k ≤ n. Proof. Assume that deg(A) = ( n k ) −1 for all A in V (GS(n,k) ) and suppose that 1 < k ≤⌊ n 2 ⌋ . By Lemma 1, since deg(A) = ( n k ) − [( n−k k ) + 1 ] , it follows that( n k ) − [( n−k k ) + 1 ] = ( n k ) − 1. This implies that − ( n−k k ) = 0 which can be equated to( n−k k ) = 0. The only time that ( n−k k ) = 0 is when n − k < k. Note that if 1 < k ≤ ⌊ n 2 ⌋ , then ⌊ n 2 ⌋ ≤ n − k. So k ≤ n − k. This is a contradiction to the fact that n − k < k. Therefore, k = 0 or ⌊ n 2 ⌋ < k ≤ n. Conversely, assume that k = 0 or ⌊ n 2 ⌋ < k ≤ n. If k is 0 or n, by Theorem 3, GS(n,k) is a trivial graph. Since |V (GS(n,k) )| = ( n k ) = 1 and the degree of the vertex of a trivial graph is 0, it follows that deg(A) = 0 = 1 − 1 = ( n k ) − 1 where A ∈ V (GS(n,k) ). Now, let ⌊ n 2 ⌋ < k < n and let A be an arbitrary vertex of GS(n,k) . Since A ⊆ Sn, then by Remark 1, it follows that |Sn \A| = n−k. Now, consider the set of all k-element subsets of Sn \ A, denoted by S(n−k,k). Observe that S(n−k,k) ⊆ V (GS(n,k) ). If ⌊ n 2 ⌋ < k < n, then n − k ≤ ⌊ n 2 ⌋ which means that n − k < k. Thus by Remark 4, |S(n−k,k)| = ( n−k k ) = 0. Note that A ∩ (Sn \A) = ∅, so for every B ∈ S(n−k,k), A ∩ B = ∅. But S(n−k,k) = ∅, so given that |V (GS(n,k) )| = ( n k ) , deg(A) = ( n k ) − 0. Also, since [A,A] /∈ E(GS(n,k) ) it follows that deg(A) = ( n k ) − 1. Since A was chosen arbitrarily, it follows that every vertex of GS(n,k) , with ⌊ n 2 ⌋ < k < n, has a degree equal to ( n k ) − 1. Illustration 5 provides an example for the degree of every vertex of a GS(n,k) when k = 0 or ⌊ n 2 ⌋ < k ≤ n with n = 4 and k is 0, 4 and 3. Illustration 5. Consider S4 = {x1, x2, x3, x4}. To show an illustration for the case k = 0 or ⌊ n 2 ⌋ < k ≤ n, we have the following: Let k = 0 and consider the pictorial illustration of GS(4,0) in Figure 3 which is a trivial graph containing the vertex ∅. It can be observed that deg(∅) = 0. To verify using Lemma 2 with n = 4 and k = 0, we have deg(∅) = ( 4 0 ) − 1 = 1− 1 = 0. Moreover, let k = 4. By Theorem 3, GS(4,4) is a trivial graph. A pictorial representation of GS(4,4) with a vertex {x1, x2, x3, x4} is shown in Figure 3. It can be observed that deg({x1, x2, x3, x4}) = 0. To verify this using Lemma 2, since n = 4 and k = 4, it follows that deg({x1, x2, x3, x4}) = ( 4 4 ) − 1 = 1− 1 = 0. Now, let k = 3. Then GS(4,3) has the vertex set V (GS(4,3) ) = { {x1, x2, x3}, {x1, x2, x4}, {x1, x3, x4}, {x2, x3, x4} } . A pictorial representation of GS(4,3) is illustrated in Figure 6. It can be observed that deg(A) = 3 for all A ∈ V (GS(4,3) ). Note that k = 3 and⌊ 4 2 ⌋ = 2 < k. To verify using Lemma 2 with n = 4 and k = 3, the degree of each M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1790 {x1, x2, x3} {x1, x2, x4} {x1, x3, x4} {x2, x3, x4} Figure 6: A Pictorial Representation of GS(4,3) . vertex A in GS(4,3) is equal to deg(A) = ( n k ) − 1 = ( 4 3 ) − 1 = 4− 1 = 3. Lemma 1 and Lemma 2 discusses the degree of every vertex in a GS(n,k) . Observe that the vertices in GS(n,k) yield the same degree. By this, then GS(n,k) is a regular graph. Equivalently, we have Theorem 5. Theorem 5. Let GS(n,k) be a k-restricted intersection graph. Then GS(n,k) is an r-regular graph where r = {( n k ) − [( n−k k ) + 1 ] if and only if 1 ≤ k ≤ ⌊ n 2 ⌋ ;( n k ) − 1 if and only if k = 0 or ⌊ n 2 ⌋ < k ≤ n. Proof. This is the direct consequence of Lemma 1 and Lemma 2. Let k = 1. Since 1 ≤ k ≤ ⌊ n 2 ⌋ , by using Lemma 1, then deg(A) = ( n 1 ) − [( n−1 1 ) + 1 ] = n − (n − 1 + 1) = 0 for all A ∈ V (GS(n,1) ). By Theorem 5, it follows that GS(n,1) is a 0-regular graph. Moreover, observe that GS(n,k) is also a 0-regular graph when k = 0 or k = n. Equivalently, we have the following remark. Remark 7. A k-restricted intersection graph GS(n,k) is a 0-regular graph if an only if k is 0, 1, or n. The size of a graph is a parameter that is also helpful in defining a graph. Since GS(n,k) is a regular graph, Equation 1, it follows that |E(GS(n,k) )| can be computed by (nk)(r) 2 where r is equal to either ( n k ) − [( n−k k ) + 1 ] or ( n k ) − 1. Theorem 6. Let GS(n,k) be a k-restricted intersection graph. Then the size of GS(n,k) is given by |E(GS(n,k) )| =  (nk){(nk)−[(n−k k )+1]} 2 if 1 ≤ k ≤ ⌊ n 2 ⌋ ; (nk)[( n k)−1] 2 if k = 0 or ⌊ n 2 ⌋ < k ≤ n. M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1791 Proof. Note that GS(n,k) is a graph of order ( n k ) . By Theorem 5, GS(n,k) is a regular graph. Now, using Equation 1, then the size of GS(n,k) is (nk) ( r ) 2 where r is the degree of every vertex in GS(n,k) . If 1 ≤ k ≤ ⌊ n 2 ⌋ , GS(n,k) is a {( n k ) − [( n−k k ) + 1 ]} -regular graph. Thus, |E(GS(n,k) )| = (nk) { (nk)− [ (n−k k )+1 ]} 2 . Furthermore, if k = 0 or ⌊ n 2 ⌋ < k ≤ n, GS(n,k) is a [( n k ) − 1 ] -regular graph. This implies that |E(GS(n,k) )| = (nk)[( n k)−1] 2 . Illustration 6. Consider GS(5,2) shown in Figure 5. Observe that k = 2 which implies that ⌊ 5 2 ⌋ = 2 = k. Since GS(5,2) is a graph of order 10 and a 6-regular graph, by utilizing Theorem 6, it follows that |E(GS(5,2) )| = 10(6) 2 = 30. Also, given GS(4,3) in Figure 6 that is a 3-regular graph of order ( 4 3 ) = 4, note that k = 3 which is ⌊ 4 2 ⌋ = 2 < k. So, we have |E(GS(4,3) )| = 4(3) 2 = 6. For any positive integer n, we have identified that GS(n,k) is a 0-regular graph if and only if k = 0, k = 1, or k = n by Remark 7. With this, then |E(GS(n,k) )| = (nk)(0) 2 = 0. Equivalently, we have Remark 8. Remark 8. If k = 0, k = 1, or k = n, then |E(GS(n,k) )| = 0. 4. k-restricted Intersection Graph as a Special Class of Graph The k-restricted intersection graph GS(n,k) yields a complete graph and cycle graph depending on the values of the nonnegative integer k. Furthermore, the degree of every vertex for the complement graph of GS(n,k) is given in this section. Theorem 7. A k-restricted intersection graph GS(n,k) is a complete graph of order ( n k ) if and only if k = 0 or ⌊ n 2 ⌋ < k ≤ n. Proof. Assume GS(n,k) is a complete graph of order ( n k ) . By the definition of a complete graph, GS(n,k) is an [( n k ) − 1 ] -regular graph. By Theorem 5, then k = 0 or ⌊ n 2 ⌋ < k ≤ n. Conversely, assume k = 0 or ⌊ n 2 ⌋ < k ≤ n. By Theorem 5, GS(n,k) is an [( n k ) − 1 ] -regular graph. Since |V (GS(n,k) )| = ( n k ) , it follows that every vertex of GS(n,k) is adjacent to every other vertex of GS(n,k) . Hence, GS(n,k) is a complete graph. Since all of the vertex of GS(n,k) where ⌊ n 2 ⌋ < k < n is adjacent to each other, it follows that every A ∈ V (GS(n,k) ) bears an intersection to any other vertex in GS(n,k) . Note that the trivial graph is a complete graph of order 1. Meaning to say, GS(n,0) and GS(n,n) are complete graphs of order 1. Illustration 7. Let S5 be equal to {x1, x2, x3, x4, x5} and let k = 3. The vertex set of the graph GS(5,3) is given by V (GS(5,3) ) = { {x1, x2, x3}, {x1, x2, x4}, {x1, x2, x5}, {x1, x3, x4}, {x1, x3, x5}, {x1, x4, x5}, {x2, x3, x4}, {x2, x3, x5}, {x2, x4, x5}, {x3, x4, x5} } . M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1792 Moreso, GS(5,3) is pictorially illustrated in Figure 7. {x1, x2, x3} {x2, x4, x5} {x1, x2, x5} {x2, x3, x5} {x1, x3, x4} {x1, x4, x5} {x1, x2, x4} {x1, x3, x5} {x3, x4, x5} {x2, x3, x4} Figure 7: A Pictorial Illustration of GS(5,3) . Observe that every vertex in GS(5,3) is adjacent to each other. Since k = 3 and ⌊ 5 2 ⌋ = 2 < 3, by Theorem 7, it follows that GS(5,3) is a complete graph of order ( 5 3 ) = 10. The next theorem imparts the necessary and sufficient conditions for GS(n,k) to be a cycle graph. Theorem 8. A k-restricted intersection graph GS(n,k) is a cycle graph of order 3 if and only if n = 3 and k = 2. Proof. Assume that GS(n,k) is a cycle graph of order 3. It is noted that every cycle graph is a 2-regular graph. Suppose that n ̸= 3 or k ̸= 2. If n < 3, then ( n k ) ≤ 2, which is a contradiction to the assumption that |V (GS(n,k) )| = 3. Moreover, if n > 3, then ( n k ) = 1 or ( n k ) ≥ 4. This is also a contradiction since the order of GS(n,k) is 3. On the other hand, if k < 2, then k is 0 or 1. By Theorem 3 or by Theorem 4, GS(n,k) is a trivial graph or an empty graph of order n, respectively. Hence, this is a contradiction to the assumption that GS(n,k) is a cycle graph of order 3. Furthermore, if k > 2, then ( n k ) is either equal to 1 or greater than or equal to 4. This is a contradiction also to the assumption that GS(n,k) is a cycle graph of order 3. Therefore, n = 3 and k = 2. Conversely, assume that n = 3 and k = 2. Observe that ⌊ 3 2 ⌋ = 1 < 2, so by Theorem 7, GS(3,2) is a complete graph of order( 3 2 ) = 3. By Remark 5, since C3 ≃ K3, it follows that GS(3,2) is a cycle graph of order 3. The only time that a cycle graph is isomorphic to a complete graph is when they have an order equal to 3. It can be verified that when n = 3 and k = 2, GS(3,2) is a complete M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1793 graph of order 3 which implies that GS(3,2) is also a cycle graph of order 3. Hence, for any 3-element set S3, GS(3,2) is a cycle graph as well as a complete graph. Illustration 8. Consider the set S3 = {x1, x2, x3} and let k = 2. Then the vertex set of GS(3,2) is given by { {x1, x2}, {x1, x3}, {x2, x3} } . The order of GS(3,2) is 3. Since k = 3, which means that ⌊ 3 2 ⌋ = 1 < k, by Theorem 7, it follows that GS(3,2) is a complete graph of order 3. By Remark 5, C3 ≃ K3. Hence, GS(3,2) is also a cycle graph of order 3. Shown in Figure 8 is a pictorial illustration of GS(3,2) . {x1, x2} {x1, x3} {x2, x3} Figure 8: Pictorial Representation of GS(3,2) . Note that GS(n,k) is a simple graph. Now, we consider the complement of GS(n,k) , denoted by GS(n,k) , as a simple graph. The next theorem determines GS(n,k) as well as the degree of its vertices. Theorem 9. Let GS(n,k) be a k-restricted intersection graph. Then the complement of GS(n,k) is an r-regular graph GS(n,k) such that r = { 0 if k = 0 or ⌊ n 2 ⌋ < k ≤ n;( n−k k ) if 1 ≤ k ≤ ⌊ n 2 ⌋ Proof. Let GS(n,k) be a k-restricted intersection graph. By Theorem 5, GS(n,k) is a regular graph. Note that its complement graph, GS(n,k) is also a regular graph. Now, to find the degree of every vertex in GS(n,k) , consider the following cases: CASE 1: If k = 0 or ⌊ n 2 ⌋ < k ≤ n, by Theorem 7, it follows that GS(n,k) is a complete graph. The complement of a complete graph is an empty graph which implies that GS(n,k) is an empty graph. Thus, deg(A) = 0 for all A ∈ V (GS(n,k) ). CASE 2: Let A be an arbitrary element of V (GS(n,k) ). If 1 ≤ k ≤ ⌊ n 2 ⌋ , by Lemma 1, deg(A) = ( n k ) − [( n−k k ) + 1 ] for all A ∈ V (GS(n,k) ). It can be observed that A is not adjacent to ( n−k k ) + 1 vertices in GS(n,k) . Since GS(n,k) is a simple graph, it follows that deg(A) = ( n−k k ) for all A ∈ V (GS(n,k) ). To illustrate Theorem 9, we utilize the graphs GS(4,3) and GS(4,2) shown in the previous discussions. M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1794 Illustration 9. Let S4 = {x1, x2, x3, x4} and let k = 3. A pictorial representation of GS(4,3) is presented in Figure 9. Since k = 3 and ⌊ 4 2 ⌋ = 2 < 3 it follows that GS(4,3) is a complete graph of order ( 4 3 ) = 4. The complement of a complete graph is an empty graph, thus, GS(4,3) is an empty graph of order ( 4 3 ) = 4. Presented also in Figure 9 is a pictorial representation of GS(4,3) . {x1, x2, x3} {x1, x2, x4} {x1, x3, x4} {x2, x3, x4} {x1, x2, x3} {x1, x2, x4} {x1, x3, x4} {x2, x3, x4} Figure 9: Pictorial Representations of GS(4,3) and its Complement Graph GS(4,3) , Respectively. It can be observed that deg(A) = 0 for all A ∈ V (GS(4,3) ). Therefore, GS(4,3) is a 0-regular graph. For 1 ≤ k ≤ ⌊ n 2 ⌋ , consider also the set S4 = {x1, x2, x3, x4} and let k = 2. The graph of GS(4,2) is previously shown in Figure 2. Now, shown in Figure 10, is a pictorial representation of the complement graph of GS(4,2) . {x1, x2} {x3, x4} {x1, x3} {x2, x4} {x1, x4} {x2, x3} Figure 10: Pictorial Illustration of the Complement Graph GS(4,2) . Now, by connecting the vertices in GS(4,2) with empty intersection, we have the edge set of GS(4,2) equal to the set { [{x1, x2}, {x3, x4}], [{x1, x3}, {x2, x4}], [{x2, x3}, {x1, x4}] } . It can be observed that every element in V (GS(4,2) ) has a degree equal to 1. Note that k = ⌊ 4 2 ⌋ = 2. Using Theorem 9 with n = 4 and k = 2, the degree of every vertex A in GS(4,2) we have: M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1795 deg(A) = ( n− k k ) = ( 4− 2 2 ) = ( 2 2 ) = 1. Hence, GS(4,2) is a 1-regular graph. It can be perceived from Case 1 of Theorem 9 GS(n,k) is an empty graph of order ( n k ) . Consequently, we have Corollary 1 which is a corollary to Theorem 9. Corollary 1. Let GS(n,k) be a k-restricted intersection graph. If k = 0 or ⌊ n 2 ⌋ < k ≤ n, then GS(n,k) is an empty graph of order ( n k ) . Proof. Assume that k = 0 or ⌊ n 2 ⌋ < k ≤ n. By Theorem 9, GS(n,k) is a complete graph of order ( n k ) . Since the complement of a complete graph is an empty graph, it follows that GS(n,k) is an empty graph of order ( n k ) . Moreover, Corollary 2 determines the degree of every vertex in the complement graph of GS(n,k) when k = 1. This is a corollary to Theorem 9. Corollary 2. Let GS(n,k) be a k-restricted intersection graph. If k = 1, then GS(n,1) is a complete graph of order n. Proof. Assume that k = 1. By Theorem 9, GS(n,1) is a [( n−k k )] -regular graph. Now, setting k = 1, we have deg(A) = ( n−1 1 ) = n − 1 for all A ∈ V (GS(n,1) ). Since |GS(n,1) | is equal to |GS(n,1) | = n, it follows that every vertex of GS(n,1) is adjacent to each other. Therefore, GS(n,1) is a complete graph of order n. Illustration 10. Let S4 = {x1, x2, x3, x4} and let k = 1. If k = 1, then by Theorem 4, GS(4,1) is an empty graph of order 4. We know that the complement graph of an empty graph is a complete graph. So, GS(4,1) is a complete graph of order 4. A pictorial representation of GS(4,1) and GS(4,1) is shown in Figure 11. Observe that every A ∈ V (GS(4,1) ), deg(A) = 4 − 1 = 3. Thus, every vertex of GS(4,1) is adjacent to each other. Therefore, GS(4,1) is a complete graph of order 4. 5. Additional Parameters of GS(n,k) Parameters are numerical values that help define a graph. In this section, other graph parameters such as the independence number, domination number, and isolate domination number are presented with proofs to determine a GS(n,k) . M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1796 {x1} {x2} {x3} {x4} {x1} {x2} {x3} {x4} Figure 11: Pictorial Illustrations of GS(4,1) (Left) and its Complement Graph GS(4,1) (Right). 5.1. Independence Number of a GS(n,k) This subsection examines the independence number of GS(n,k) given the two cases: when 1 ≤ k ≤ ⌊ n 2 ⌋ and k = 0 or ⌊ n 2 ⌋ < k ≤ n. We shall denote the independence number of GS(n,k) as α(GS(n,k) ). The lemma below determines the existence of an independent set in GS(n,k) for 1 ≤ k ≤ ⌊ n 2 ⌋ . Lemma 3. Let Sn = {x1, x2, ..., xn} be an n-element set and let GS(n,k) be a k-restricted intersection graph. If 1 ≤ k ≤ ⌊ n 2 ⌋ , then T = { {x1, x2, ..., xk}, {xk+1, ..., x2k}, ..., {x(⌊n k ⌋−1)k+1, ..., x(⌊n k ⌋)k} } is an independent set in GS(n,k) where |T | = ⌊ n k ⌋ . Proof. Let T = { {x1, x2, ..., xk}, {xk+1, ..., x2k}, ..., {x(⌊n k ⌋−1)k+1, ..., x(⌊n k ⌋)k} } . It can be observed that T contains some of the partitions of Sn where for every A ∈ T , |A| = k. This implies that T ⊆ S(n,k) and thus, T ⊆ V (GS(n,k) ). Since for all A,B ∈ T and A ̸= B, A ∩ B = ∅, it follows that [A,B] /∈ E(GS(n,k) ). Hence, T is an independent set in GS(n,k) . Now, if n is divisible by k, then |T | = n k . On the other hand, if n is not divisible by k, then by Division Algorithm, there exist unique integers a and b with 0 < b < k such that n = ka+ b. Meaning to say, there are b elements of Sn that are not in T . We cannot form a k-element subset from the b remaining elements, so |T | = ⌊ n k ⌋ . Either way |T | = ⌊ n k ⌋ . Lemma 3 identifies one independent set in GS(n,k) . We will utilize this to determine α(GS(n,k) ) for 1 ≤ k ≤ ⌊ n 2 ⌋ . Illustration 11. Let S6 = {x1, x2, x3, x4, x5, x6} and let k = 2. Then the vertex set of a GS(6,2) is given by V (GS(6,2) ) = { {x1, x2}, {x1, x3}, {x1, x4}, {x1, x5}, {x1, x6}, {x2, x3}, {x2, x4}, {x2, x5}, {x2, x6}, {x3, x4}, {x3, x5}, {x3, x6}, {x4, x5}, {x4, x6}, {x5, x6} } A pictorial illustration of GS(6,2) is shown in Figure 12. M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1797 {x1, x2} {x1, x3} {x1, x4} {x1, x5} {x1, x6} {x2, x3} {x2, x4} {x2, x5}{x2, x6} {x3, x4} {x3, x5} {x3, x6} {x4, x5} {x4, x6} {x5, x6} GS(6,2) Figure 12: A Pictorial Illustration of GS(6,2) . Now, we let Ti ⊆ V (GS(6,2) ) for 1 ≤ i ≤ 3. Notice that T1 = { {xi, xj} } where 1 ≤ i, j ≤ 6 and i ̸= j is an independent set since GS(6,2) is a simple graph. Moreover, the set T2 = { {x1, x2}, {x3, x4} } is an independent set also since {x1, x2}∩{x3, x4} = ∅ it follows that [{x1, x2}, {x3, x4}] /∈ E(GS(6,2) ). This implies that there exists an independent set with the cardinality equal to 2. On the other hand, T3 = { {x1, x2}, {x3, x4}, {x5, x6} } is also an independent set since {x1, x2}∩{x3, x4} = ∅, {x1, x2}∩{x5, x6} = ∅, and {x3, x4}∩ {x5, x6} = ∅ it follows that [{x1, x2}, {x3, x4}] , [{x1, x2}, {x5, x6}], [{x3, x4}, {x5, x6}] are not edges in GS(6,2) . Observe that ⌊ 6 2 ⌋ = 3 and |T3| = 3. Hence, there exists an independent set in GS(6,2) with the cardinality equal to 3. Note that there exists an independent set in GS(n,k) . With this, we can now compute for α(GS(n,k) ). Theorem 10 determines the independence number for a GS(n,k) if 1 ≤ k ≤ ⌊ n 2 ⌋ . Theorem 10. Let Sn = {x1, x2, ..., xn} be an n-element set and let GS(n,k) be a k-restricted intersection graph. If 1 ≤ k ≤ ⌊ n 2 ⌋ , then α(GS(n,k) ) = ⌊ n k ⌋ . Proof. Let T = { {x1, x2, ..., xk}, {xk+1, ..., x2k}, ..., {x(⌊n k ⌋−1)k+1, ..., x(⌊n k ⌋)k} } . By Lemma 3, T is an independent set in GS(n,k) with |T | = ⌊ n k ⌋ . Since there exists an M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1798 independent set in GS(n,k) with a cardinality equal to ⌊ n k ⌋ , it follows that α(GS(n,k) ) ≥ ⌊ n k ⌋ . We claim that α(GS(n,k) ) = ⌊ n k ⌋ . Now, suppose α(GS(n,k) ) > ⌊ n k ⌋ . This implies that there exists W ⊆ V (GS(n,k) ) with |W | > ⌊ n k ⌋ that is an independent set in GS(n,k) . Without loss of generality, we say that n is not divisible by k. Hence, by the division algorithm, there exist integers a and b where 0 < b < k such that n = ka + b. However |W | > |T |. Thus, the remaining b elements are now in W in the form of k-subsets. Since b < k, it follows that these b elements are paired with some elements in Sn to form a k-element subset. By this, it can be observed that there will exist A,B ∈ W where A ̸= B such that A ∩ B ̸= ∅. This is a contradiction to the fact that W is an independent set. Therefore, α(GS(n,k) ) = ⌊ n k ⌋ . Illustration 12. Consider S6 = {x1, x2, x3, x4, x5, x6} and let k = 2. A pictorial rep- resentation of GS(6,2) is shown in Figure 12. Recall that from Illustration 11, T ={ {x1, x2}, {x3, x4}, {x5, x6} } is an independent set in GS(6,2) with |T | = 3 = ⌊ 6 2 ⌋ . Note that {x1, x2}, {x3, x4}, {x5, x6} are 2-element set partitions of S6. Thus adding another element of V (GS(6,2) ) will produce an intersection to any of {x1, x2}, {x3, x4}, or {x5, x6}. This entails that there are no independent sets in GS(6,2) of cardinality greater than 3. Therefore, α(GS(6,2) ) = 3. Now, using Theorem 10, setting n = 6 and k = 2, we have α(GS(6,2) ) = ⌊n k ⌋ = ⌊ 6 2 ⌋ = ⌊3⌋ = 3. Now, by Theorem 4, if k = 1, then GS(n,1) is an empty graph of order n. Note that there is no edge connecting every vertex of GS(n,1) and V (GS(n,1) ) ⊆ V (GS(n,1) ), so the set V (GS(n,1) ) is an independent set in GS(n,1) . Since |V (GS(n,1) )| = n, it follows that α(GS(n,1) ) = n. It can be verified from Theorem 10 that when k = 1, α(GS(n,1) ) = ⌊ n 1 ⌋ = n. Correspondingly, we have Remark 9. Remark 9. Let GS(n,k) be a k-restricted intersection graph. If k = 1, then α(GS(n,1) ) is equal to n. We have now identified the α(GS(n,k) ) whenever 1 ≤ k ≤ ⌊ n k ⌋ . Now, Theorem 11 determines the independence number of GS(n,k) when k = 0 or ⌊ n 2 ⌋ < k ≤ n. Theorem 11. Let GS(n,k) be a k-restricted intersection graph. If k = 0 or ⌊ n 2 ⌋ < k ≤ n, then α(GS(n,k) ) = 1. Proof. By Theorem 7, GS(n,k) is a complete graph of order ( n k ) . Since the independence number of a complete graph is 1, it follows that α(GS(n,k) ) = 1. M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1799 5.2. Domination Number of GS(n,k) This subsection further exposes the domination number of a GS(n,k) when 1 ≤ k ≤ ⌊ n 2 ⌋ and k = 0 or ⌊ n 2 ⌋ < k ≤ n. We will denote γ(GS(n,k) ) as the domination number of GS(n,k) . The next lemma establishes the existence of a dominating set in GS(n,k) whenever 1 ≤ k ≤ ⌊ n 2 ⌋ . Lemma 4. Let GS(n,k) be a k-restricted intersection graph. If 1 ≤ k ≤ ⌊ n 2 ⌋ , then T = { {x1, x2, ..., xk}, {xk+1, ..., x2k}, ..., {x(⌊n k ⌋−1)k+1, ..., x(⌊n k ⌋)k} } , is a dominating set in GS(n,k) where |T | = ⌊ n k ⌋ . Proof. Let T = { {x1, x2, ..., xk}, {xk+1, ..., x2k}, ..., {x(⌊n k ⌋−1)k+1, ..., x(⌊n k ⌋)k} } . It can be observed that T contains some of the k-element partitions of Sn. Thus, T ⊆ S(n,k) which implies that T ⊆ V (GS(n,k) ). If n is divisible by k, then T contains all the elements of Sn that are partitioned into k-subsets. By this, then for every A ∈ V (GS(n,k) ) \T , there exists B ∈ T such that A ∩ B ̸= ∅. By Definition 7, [A,B] ∈ E(GS(n,k) ). Hence, T is a dominating set in GS(n,k) . Since n is divisible by k, it follows that |T | = n k . On the other hand, if n is not divisible by k, then by the division algorithm, there exist integers a and b with 0 < b < k such that n = ka + b. Meaning to say, there are b remaining elements that are not in T since we cannot form a k-subset from these elements. Observe that the remaining b elements can be paired to other elements of Sn to form a k-subset such that these subsets are elements of V (GS(n,k) ) \ T . Thus, for all A ∈ V (GS(n,k) ) \ T , there exists B ∈ T where A ∩ B ̸= ∅ that implies [A,B] ∈ E(GS(n,k) ). By this, T is a dominating set in GS(n,k) with |T | = ⌊ n k ⌋ . Either way, |T | = ⌊ n k ⌋ . The set T discussed in Lemma 4 is one of the dominating sets in GS(n,k) . This set shall be employed to find to find γ(GS(n,k) ) whenever 1 ≤ k ≤ ⌊ n k ⌋ . Illustration 13. Let S6 = {x1, x2, x3, x4, x5, x6} and k = 2. To pictorially illustrate GS(6,2) , refer to Figure 12. Also, let T = {{x1, x2}, {x3, x4}, {x5, x6}}. It can be observed that T ⊆ V (GS(6,2) ). Now, the set V (GS(6,2) ) \ T is given by V (GS(6,2) ) \ T = { {x1, x3}, {x1, x4}, {x1, x5}, {x1, x6}, {x2, x3}, {x2, x4}, {x2, x5}, {x2, x6}, {x3, x5}, {x3, x6}, {x4, x5}, {x4, x6} } The vertices in V (GS(6,2) ) \T that are adjacent to {x1, x2} are {x1, x3}, {x1, x4}, {x1, x5}, {x1, x6}, {x2, x3}, {x2, x4}, {x2, x5}, {x2, x6}. Moreover, {x3, x5}, {x3, x6}, {x4, x5}, {x4, x6} are the vertices adjacent to {x3, x4}. All of the elements in V (GS(6,2) ) \ T are adjacent to either {x1, x2} or {x3, x4}. Thus, T is a dominating set. Note that |T | = 3 = ⌊ 6 2 ⌋ . Hence, there exists a dominating set in GS(6,2) with a cardinality of ⌊ n k ⌋ = ⌊ 6 2 ⌋ . By Lemma 4, it can be observed that there exists a dominating set in GS(n,k) . Hence, we can now compute for γ(GS(n,k) ) where 1 ≤ k ≤ ⌊ n 2 ⌋ . M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1800 Theorem 12. Let GS(n,k) be a k-restricted intersection graph. If 1 ≤ k ≤ ⌊ n 2 ⌋ , then γ(GS(n,k) ) = ⌊ n k ⌋ . Proof. Let T = { {x1, x2, ..., xk}, {xk+1, ..., x2k}, ..., {x(⌊n k ⌋−1)k+1, ..., x(⌊n k ⌋)k} } . By Lemma 4, T is a dominating set inGS(n,k) where |T | = ⌊ n k ⌋ . Since there exists a dominating set in GS(n,k) with a cardinality equal to ⌊ n k ⌋ , it follows that γ(GS(n,k) ) ≤ ⌊ n k ⌋ . We claim that γ(GS(n,k) ) = ⌊ n k ⌋ . Now, suppose γ(GS(n,k) ) < ⌊ n k ⌋ . Thus, there exists W ⊆ V (GS(n,k) ) such that W is a dominating set in GS(n,k) and |W | < ⌊ n k ⌋ . Without loss of generality, assume that n is not divisible by k. So by the division algorithm, there exist unique integers a and b where n = ka + b. But note that |W | < |T |. Hence, k ≤ b to make |W | < |T |. This is a contradiction to the fact that 0 < b < k. Therefore, γ(GS(n,k) ) = ⌊ n k ⌋ . Illustration 14. Let S6 = {x1, x2, x3, x4, x5, x6} and k = 2. In Illustration 13, we have identified that T = {{x1, x2}, {x3, x4}, {x5, x6}} is a dominating set. We cannot remove {x5, x6} from T since {x1, x2}∩{x5, x6} = ∅ and {x3, x4}∩{x5, x6} = ∅ which implies that they are not adjacent to each other if {x5, x6} becomes an element of V (GS(6,2) )\T . Thus, there are no dominating sets in GS(6,2) with cardinality less than 3. Hence, γ(GS(6,2) ) = 3. Now, by using Theorem 12, setting n = 6 and k = 2, we have: γ(GS(6,2) ) = ⌊n k ⌋ = ⌊ 6 2 ⌋ = ⌊3⌋ = 3. By Theorem 4, GS(n,1) is an empty graph of order n. Since every vertex of an empty graph is isolated, or has no adjacency to every other vertex, it follows that V (GS(n,1) ) is a dominating set in GS(n,1) . It can be verified that there are no existing dominating set in GS(n,1) with cardinality less than n, therefore, γ(GS(n,1) ) = n. To verify using Theorem 12 with k = 1, then we have γ(GS(n,1) ) = ⌊ n 1 ⌋ = n. Equivalently, we have Remark 10. Remark 10. Let GS(n,k) be a k-restricted intersection graph. If k = 1, then γ(GS(n,1) ) is equal to n. Moreover, Theorem 13 determines the domination number of GS(n,k) whenever k = 0 or ⌊ n 2 ⌋ < k ≤ n. Theorem 13. Let GS(n,k) be a k-restricted intersection graph. If k = 0 or ⌊ n 2 ⌋ < k ≤ n then γ(GS(n,k) ) = 1. Proof. Note that by Theorem 7, GS(n,k) is a complete graph. Since GS(n,k) is a complete graph, since the domination number of a complete graph is 1, it follows that γ(GS(n,k) ) = 1. M.E. Pelagio, N. Mame, K. Mendoza / Eur. J. Pure Appl. Math, 17 (3) (2024), 1779-1803 1801 5.3. Isolate Domination Number of GS(n,k) This subsection analyzes the isolate domination of GS(n,k) given the two cases: if 1 ≤ k ≤ ⌊ n 2 ⌋ and if k = 0 or ⌊ n 2 ⌋ < k ≤ n. We will utilize the notion γ0(GS(n,k) ) to denote the isolate domination number of GS(n,k) . The next theorem determines the γ0 of a GS(n,k) for 1 ≤ k ≤ ⌊ n 2 ⌋ . The set T discussed in Lemma 3 and Lemma 4 will be used to define the existence of an isolate dominating set in GS(n,k) . Theorem 14. Let Sn = {x1, x2, ..., xn} be an n-element set and let GS(n,k) be a k-restricted intersection graph. If 1 ≤ k ≤ ⌊ n 2 ⌋ , then γ0(GS(n,k) ) = ⌊ n k ⌋ . Proof. Let T = { {x1, x2, ..., xk}, {xk+1, ..., x2k}, ..., {x(⌊n k ⌋−1)k+1, ..., x(⌊n k ⌋)k} } . Note that by Lemma 3, T is an independent set in GS(n,k) where |T | = ⌊ n k ⌋ . It can be verified that < T > is an empty graph of order ⌊ n k ⌋ . Thus, for all A ∈ V (< T >), we have deg(A) = 0 which implies that every vertex in < T > is an isolated vertex. Moreover, by Lemma 4, the set T is also a dominating set in GS(n,k) . Since T is an independent set and dominating set in GS(n,k) , it follows that T is an isolate dominating set in GS(n,k) with |T | = ⌊ n k ⌋ . Hence, there exist an isolate dominating set in GS(n,k) with cardinality equal to ⌊ n k ⌋ . This implies that γ0(GS(n,k) ) ≤ ⌊ n k ⌋ . By Theorem 12, γ(GS(n,k) ) = ⌊ n k ⌋ . Note that γ(GS(n,k) ) ≤ γ0(GS(n,k) ). Therefore, γ0(GS(n,k) ) = ⌊ n k ⌋ . Theorem 15. Let GS(n,k) be a k-restricted intersection graph. Then γ0(GS(n,k) ) = 1 if k = 0 or ⌊ n 2 ⌋ < k ≤ n. Proof. By Theorem 7, GS(n,k) is a complete graph of order ( n k ) . Since GS(n,k) is a complete graph, since the isolate domination number of a complete graph is 1, it follows that γ0(GS(n,k) ) = 1. 6. Summary, Conclusion, and Recommendations This study introduces and discusses a k-restricted intersection graph including some of the graph’s parameters.A k-restricted intersection graph is a simple graph whose vertex set is equal to S(n,k) and two vertices A,B in GS(n,k) are adjacent whenever A ∩ B ̸= ∅ and A ̸= B. The case S0 is a trivial case for GS(n,k) . The order of GS(n,k) is given by ( n k ) . It was determined that GS(n,k) is a trivial graph if and only if k = 0 or k = n. Also, if k = 1, then GS(n,k) is an empty graph of order n. In addition, it was established that GS(n,k) is a regular graph such that for any A ∈ V (GS(n,k) ), deg(A) = ( n k ) − [( n−k k ) + 1 ] if and only if 1 ≤ k ≤ ⌊ n k ⌋ . Furthermore, deg(A) = ( n k ) − 1 if and only if k = 0 or ⌊ n k ⌋ < k ≤ n. With these, the size of GS(n,k) is proven to be equal to |E(GS(n,k) )| =  (nk) { (nk)− [ (n−k k )+1 ]} 2 if 1 ≤ k ≤ ⌊ n 2 ⌋ ; (nk) [ (nk)−1 ] 2 if k = 0 or ⌊ n 2 ⌋ < k ≤ n. REFERENCES 1802 Additionally, the study disclosed that GS(n,k) was a complete graph if and only if k = 0 or ⌊ n 2 ⌋ < k ≤ n. More so, GS(n,k) is a cycle graph of order 3 if and only if n = 3 and k = 2. The complement graph of GS(n,k) was also determined. Considering that GS(n,k) is a simple graph, then its complement graph is also a simple graph. It was further established that GS(n,k) is a regular graph having the following degree for all A ∈ V (GS(n,k) ), depending on each cases: if 1 ≤ k ≤ ⌊ n 2 ⌋ , deg(A) = ( n−k k ) ; on the other hand if k = 0 or ⌊ n 2 ⌋ < k ≤ n, deg(A) = 0. Finally, other parameters of GS(n,k) such as the independence number, domination number, and the isolate domination number were specified. The independence number of GS(n,k) when 1 ≤ k ≤ ⌊ n 2 ⌋ is equal to ⌊ n k ⌋ while if k = 0 or ⌊ n 2 ⌋ < k ≤ n, then the independence number is 1. Further, it was found out that for any value of k, we have γ(GS(n,k) ) = γ0(GS(n,k) ). If 1 ≤ k ≤ ⌊ n 2 ⌋ , then γ(GS(n,k) ) = γ0(GS(n,k) ) = ⌊ n k ⌋ . Meanwhile, γ(GS(n,k) ) = γ0(GS(n,k) ) = 1 if k = 0 or ⌊ n 2 ⌋ < k ≤ n. In conclusion, we determine the order, size, independence number, domination number, and isolated domination number of a k-restricted intersection graph in this study. Also, we provided the necessary and sufficient conditions for a GS(n,k) to be isomorphic to a cycle graph and a complete graph. From the results drawn, the researchers believed that a parallel study may be done to further characterize GS(n,k) . In particular, we recommend that future studies find other parameters of a GS(n,k) such as its girth, clique number, chromatic number, and locating domination number to name a few, for this will also be helpful in determining the graph. Moreover, it is recommended to further investigate GS(n,k) proposing the utilization of binary graph operations wherein some of these are the sum of joint, cartesian product, composition, edge gluing, and vertex gluing may be imperatively conducted. Lastly, future researchers may consider adapting GS(n,k) in solving real-world problems for some of the results established are based on the binomial coefficient or the combination formula that has several real-world applications. Acknowledgements The authors would like to acknowledge the following institutions for their support on the fulfilment of this research project: Batangas State University - The National Engineer- ing University (BatStateU-TNEU) and Department of Science and Technology - Science Education Institute, Science and Technology Regional Alliance of Universities for National Development (DOST-SEI, STRAND). Also, the authors would like to extend their heart- felt gratitude to the anonymous reviewers of this study and the editors of this journal, for their efforts in reviewing this publication. References [1] A. Neumaier A. Brouwer, A. Cohen. Distance-Regular Graphs. Springer Berlin, Heidelberg, 1989. REFERENCES 1803 [2] Richard A. Brualdi. Introductory Combinatorics. Prentice-Hall, 2010. [3] J. Harris et al. Combinatorics and Graph Theory. Springer Nature, 2008. [4] D. Fowler. The binomial coefficient function. The American Mathematical Monthly, 1996. [5] M. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Elsevier, 2004. [6] D. Guichard. Graph Coloring and Independence Number of a Complete Graph. Whit- man College 2017, 2017. [7] I. Hamid and S. Balamurugan. Isolate domination in graphs. Arab Journal of Math- ematical Sciences, 2016. [8] N. Helwig. Introduction to Set Theory. University of Minnesota, 2020. [9] D. Magpantay J.C. Bonifacio, C.J. Andaya. On the j-edge intersection graph of cycle graph. European Journal of Pure and Applied Mathematics, 2023. [10] L. Pósa P. Erdős, A. Goodman. The representation of a graph by set intersections. Canadian Journal of Mathematics, 18(1):106–112, 1966. [11] M. Schaefer. Complexity of some geometric and topological problems. Springer Link, 2010. [12] S. Selkow. The independence number of graphs in terms of degrees. Discrete Mathe- matics, 122(1):343–348, 1993. [13] A. Sugumaran and E. Jayachandran. Domination number of some graphs. Interna- tional Journal of Scientific Development and Research (IJSDR), 2018. [14] E. Szpilrajn-Marczewski. On Two Properties of Set Classes. American Mathematical Society, 33:303–307, 1945. [15] F.R. McMorris T. McKee. Topics in Intersection Graph Theory. Society for Industrial and Applied Mathematics, Philadelphia, United States, 1999.