EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 17, No. 4, 2024, 3815-3825 ISSN 1307-5543 – ejpam.com Published by New York Business Global Some Generator Subgraphs of the Square of a Cycle Realiza M. Mame College of Teacher Education, Batangas State University, The National Engineering University, Pablo Borbon Campus, Batangas City, Philippines Abstract. Graphs considered in this paper are finite simple graphs, which have no loops and multiple edges. Let G = (V (G), E(G)) be a graph with E(G) = {e1, e2, . . . , em}, for some positive integer m. The edge space of G, denoted by E (G), is a vector space over the field Z2. The elements of E (G) are all the subsets of E(G). Vector addition is defined as X +Y = X ∆ Y, the symmetric difference of sets X and Y, for X,Y ∈ E (G). Scalar multiplication is defined as 1 · X = X and 0 · X = ∅ for X ∈ E (G). Let H be a subgraph of G. The uniform set of H with respect to G, denoted by EH(G), is the set of all elements of E (G) that induces a subgraph isomorphic to H. The subspace of E (G) generated by EH(G) shall be denoted by EH(G). If EH(G) is a generating set, that is EH(G) = E (G), then H is called a generator subgraph of G. This paper provides characterization for the star graph, path graph, (3, r)− tadpole graph, and kite graph Ktr,s so that these classes of graphs are generator subgraphs of the square of a cycle. 2020 Mathematics Subject Classifications: 05C25 Key Words and Phrases: Edge space of a graph, Generator Subgraph, Square of a cycle, Uniform set 1. Introduction Many interesting studies in graph theory use algebraic structures to define new classes of graphs. Then, determine the characteristics of the new developed graphs using graph- theoretic properties. For example, to mention some, the set of k− subset of an artibrary set was used in [10]. The notion of group was used in [1]. In [2], the set of all induced subgraphs were utilized to develop new classes of graphs. There are several similar studies that can be found in the literature, although some uses different algebraic structures. The notion of the generator subgraph of a graph introduced by Gervacio in 2008 links the graph theory with algebra. This notion stems from the theory of the edge space of a graph. In this study, graphs considered are finite simple undirected graphs, which have no loops and multiple edges. Let G be a graph with E(G) = {e1, e2, . . . , em}, for some positive integer m. The edge space of G, denoted by E (G), is a vector space over the field Z2 = {0, 1}. The elements DOI: https://doi.org/10.29020/nybg.ejpam.v17i4.5566 Email address: realiza.mame@g.batstate-u.edu.ph (R. Mame) https://www.ejpam.com 3815 Copyright: © 2024 The Author(s). (CC BY-NC 4.0) R. Mame / Eur. J. Pure Appl. Math, 17 (4) (2024), 3815-3825 3816 of E (G) are all the subsets of E(G). Vector addition is defined as X + Y = X ∆ Y, the symmetric difference of sets X and Y, for X,Y ∈ E (G). Scalar multiplication is defined as 1 ·X = X and 0 ·X = ∅ for X ∈ E (G). The set S ⊆ E (G) is called a generating set if every element of E (G) is a linear combination of the elements of S. For a non-empty set X ⊆ E(G), the smallest subgraph of G with edge set X is called the edge-induced subgraph of G, which we denote by G[X]. In this paper, when we say induced subgraph, we mean an edge-induced subgraph of a graph. Let H be a subgraph of G.The uniform set of H with respect to G, denoted by EH(G), is the set of all elements of E (G) that induces a subgraph isomorphic to H. The subspace of E (G) generated by EH(G) is denoted by EH(G). If EH(G) is a generating set, that is EH(G) = E (G), then H is called a generator subgraph of G. It can be verified that the set A = {{e1}, {e2}, . . . , {em}} forms a basis of E (G). Hence, dimE (G) = m, the size of G. The set A is called the natural basis for the edge space of G, as adopted from [7]. Clearly, EH(G) ⊆ E (G). To show that a subgraph H is a generator subgraph of G, it is sufficient to show that E (G) ⊆ EH(G). That is, the basis {{e1}, {e2}, . . . , {em}} ⊆ EH(G). Equivalently, we have the following useful remark. Remark 1 ([8]). Let H be a subgraph of G. Then H is a generator subgraph of G if and only if for every e ∈ E(G) the singleton {e} ∈ EH(G). Readers may refer to [8] for an illustration of finding the generator subgraph of a graph using Remark 1. In [8], the concept of even edge space E ∗(G) of a graph was introduced. If G is a graph with size m, it was shown that E ∗(G) is a maximal subspace of the edge space of G with dimension m− 1. The results on the notion of even edge space are useful in this study. Several studies on this problem focuses on the determination of the generator subgraphs of some common classes of graphs, see [11], [8], [6], [5], [7]. It can be noted that among the classes of graphs being studied, only the generator subgraphs of the complete graph and star graph were completely known. One significant result on this problem was a necessary condition that the size of a subgraph H of G must be odd, [4]. Hence, in finding the generator subgraph of a graph, we consider only those subgraphs with odd sizes. Equivalently, we have the following theorem. Theorem 1 ([4]). Let H be a subgraph of the graph G. If H is a generator subgraph of G, then |E(H)| is odd. By a graph G, we mean an ordered pair (V (G), E(G)), where V (G) is a finite non- empty set of elements called vertices and E(G) is a set of 2− subset of V (G) whose elements are called edges. The sets V (G) and E(G) are called the vertex set and edge set of G, respectively. The order of G is the cardinality of V (G), denoted by |V (G)|, and the size of G is the cardinality of E(G), denoted by |E(G)|. If [x, y] ∈ E(G), we say that x is adjacent to y or y is adjacent to x. For the two graphs G and H, by G ≃ H, we mean G is isomorphic to H. A vertex in a graph with degree 1 is called a pendant vertex while an edge of the graph incident to a pendant vertex is called pendant edge. We used the usual notations for some special classes of graphs, Kn for complete graph of order n, Pn for R. Mame / Eur. J. Pure Appl. Math, 17 (4) (2024), 3815-3825 3817 path of order n, and Sn for star graph of order n+1. Some other classes of graphs, which were identified to be a generator subgraphs of the square of a cycle, are defined in the appropriate section of this paper. For other basic concepts in graph theory, readers may refer to the book written by Chartrand & Zhang [3]. For the algebra concepts,particularly vector spaces and some of its properties, readers may refer to the book written by E.D. Nering [9]. Let x, y ∈ V (G). The distance between x and y, denoted by d(x, y), is the length of the shortest x − y path. Let Cn be a cycle of length n. The square of the cycle Cn, denoted by C2 n, is the graph obtained from Cn by adding the edge [x, y] to the cycle Cn if and only if d(x, y) = 2. Examples of square of some cycle graphs Cn are given in Figure 1. Figure 1: Illustrating the square of different cycle graphs This study focuses on determining the generator subgraphs of the square of the cycle. At first, we provide the fixed labeling of the square of a cycle and define the edges in terms of its vertices. Then, use some properties of the square of a cycle, such as rotational symmetry to determine its generator subgraphs. Finally, some classes of graphs were found to be generator subgraphs of the square of the cycle. In determining the dimension of the edge space of the square of a cycle graph, we utilize the following theorem, a well-known theorem in graph theory. Theorem 2. If G is a graph of size m, then∑ v∈V (G) deg(v) = 2m. 1.1. Some other known results on the generator subgraph of a graph This section provides some other results on the generator subgraph of a graph. These results are useful in proving results of this study. The remaining theorems can be found in [8]. The first theorem states that the path P2 is a generator subgraph of a nonempty graph G. Theorem 3. Let G be a graph with |E(G)| = m > 0. Then the path P2 is a generator subgraph of G. In [8], it was found that the subspace generated by set of all elements of E (G) with even cardinality has dimension m− 1, where m is the size of the graph. This vector space R. Mame / Eur. J. Pure Appl. Math, 17 (4) (2024), 3815-3825 3818 is called even edge space of graph, denoted by E ∗(G). Equivalently, the following theorem is stated below. Theorem 4 ([8]). Let G be a graph with E(G) = {e1, e2, . . . , em}. Then E ∗(G) is a subspace of E (G). Moreover, dimE ∗(G) = m− 1. Also, they found a basis for E ∗(G), which is stated below. Theorem 5 ([8]). Let G be a graph with E(G) = {e1, e2, . . . , em} and define B = {X1, X2, . . . , Xm−1}, where X1 = {e1, e2}, X2 = {e1, e3}, . . . , Xm−1 = {e1, em}. Then B forms a basis for E ∗(G). Finally, in [8], they determined some properties of graphs wherein a star is one of its generator subgraphs. Theorem 6. Let p > 0 be an odd integer. If G is a graph such that for every edge [a, b] in G either deg(a) > p or deg(b) > p, then star Sp is a generator subgraph of G. Below is an immediate consequence of Theorem 6. Corollary 1. Let p > 0 be odd. If G is k- regular and k > p then star Sp is a generator subgraph of G. The converse of Theorem 6 is not true for p = 1 since star S1 ≃ P2 is a generator subgraph of the graph G = kP2, a graph consisting of k vertex-disjoint copies of P2. If p ̸= 1, we have the following result. Theorem 7. Let p > 1 be odd. Then Sp is a generator subgraph of G if and only if for every edge [a, b] in G, either deg(a) > p or deg(b) > p. 2. Results The main results of this study are divided into two parts. The first part investigated the edge space of the square of a cycle, its dimension and discusses some preliminary results. The second part provides some special classes of graphs which are generator subgraphs of the square of a cycle. The preliminary results in the first part were utilized in obtaining the generator subgraphs of the square of a cycle. 2.1. Edge Space of the Square of a Cycle Let C2 n denote the square of a cycle of order n. Let V (C2 n) = {1, 2, 3, . . . , n} where the sequence of vertices [1, 2, 3, . . . , n] forms the cycle Cn. We shall assume that the vertices 1, 2, 3, . . . , n−1 and n are arranged in increasing order in a clockwise direction. Thus, the edges of C2 n are of the form [i, i+1] and [i, i+2], where 1 ≤ i ≤ n and n+1 = 1 & n+2 = 2. Define ei = [i, i+1] and si = [i, i+2]. Although [i, i+1] = [i+1, i] and [i, i+2] = [i+2, i], for isomorphism purposes, we shall observe the order of the vertices in the definition of ei and si. Thus, by the mapping of vertices ei 7→ ej , we mean the mapping of vertices i 7→ j R. Mame / Eur. J. Pure Appl. Math, 17 (4) (2024), 3815-3825 3819 .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................................................................................................................................................................................................................................... .............. ............. ............. ............. ............. ............. ............. ............. ............. .... .............. ............. ............. ............. ............. ............. ............. ............. ............. .......... ................................ ................................ ................................ .................... ................................. ................................ ................................ ......................... .......................................................................................................................................................................................................................................... .............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............ ................... .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. ................. ................... .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. ................. .......................................................................................................................................................................................................................................... .................................................................................................................................................................................................................................................................................................................................................................... ........ ........ ........ e1 e2 e3 e4 en−1 en e5 sn 1 2 3 4 5 n− 1 n 6 sn−1 s1 s2 s3 s4 Figure 2: The labeling of C2 n and i+ 1 7→ j + 1. Here, subscripts are taken modulo n. Unless otherwise stated, we shall use this labeling throughout the discussion of this paper and we shall call this the labeling of C2 n. Figure 2 represents the labeling of C2 n. Remark 2. The following statements hold. i. C2 3 ≃ K3, C 2 4 ≃ K4, and C2 5 ≃ K5. ii. Let n be a positive integer. If n ≥ 5 then C2 n is a 4− regular graph. In this study we consider the square of Cn where n > 5 since C2 n is a complete graph of order n if n = 3, 4,&5 and the generator subgraphs of complete graphs were completely known by Gervacio [4]. Next, we determine the dimension of the edge space of C2 n. Theorem 8. Let n ≥ 5 be an integer. Then dimE (C2 n) = 2n. Proof. To show that dimE (C2 n) = 2n, it is enough to show that the size of C2 n is 2n. Let V (C2 n) = {v1, v2, v3, . . . , vn}. By Theorem 2, 2|E(C2 n)| = ∑n i=1 deg(vi). By Remark 2, C2 n is a 4− regular graph. Hence, 2|E(C2 n)| = ∑n i=1 4 = 4n. This implies that |E(C2 n)| = 2n. The following remark and lemma are simple observations. Remark 3. Let H be a subgraph of C2 n. If {ei, si} ∈ E (C2 n) for some integer i, 1 ≤ i ≤ n, then by rotational symmetry on C2 n, {ei, si} ∈ E (C2 n) for all i. Similarly, if {ei, si−1} ∈ E (C2 n) for some integer i, 1 ≤ i ≤ n, then {ei, si−1} ∈ E (C2 n) for all i. Lemma 1. Let H be a subgraph of C2 n. Then {ei, si} ∈ EH(C2 n) if and only if {ei, si−1} ∈ EH(C2 n) where 1 ≤ i ≤ n. Proof. Let us consider the labeling of C2 n. Assume that {ei, si} ∈ EH(C2 n). Then {ei, si} = H1∆H2∆ · · ·∆Hk, where Hj ∈ EH(C2 n), j and k are positive integers, where R. Mame / Eur. J. Pure Appl. Math, 17 (4) (2024), 3815-3825 3820 1 ≤ j ≤ k. Define the mapping ϕ : Hj −→ H ′ j by ϕ(ei) = en−(i−1) and ϕ(si) = sn−i. Here, subscripts are taken modulo n. It can be verified that ϕ is an isomorphism. Thus, H ′ j ∈ EH(C2 n) for all j. Hence, {ϕ(ei), ϕ(si)} = {en−(i−1), sn−i} = {e(n−i+1), sn−i} = H ′ 1∆H ′ 2∆ · · ·∆H ′ k ∈ EH(C2 n). By Remark 3, {ei, si−1} ∈ EH(C2 n). For the converse, the proof is similar. The next result is an extension of the above lemma. Lemma 2. Let H be a subgraph of C2 n. If {ei, si} ∈ EH(C2 n) for some integer i, where 1 ≤ i ≤ n, then E ∗(C2 n) ⊆ EH(C2 n). Proof. Consider the labeling of C2 n, let B = {{e1, e2}, {e1, e3}, . . . , {e1, en}, {e1, s1}, {e1, s2}, . . . , {e1, sn}}. By Theorem 5, B forms a basis for E ∗(C2 n) so it is enough to show that B ⊆ EH(C2 n). Let X ∈ B. Then X = {e1, ei} or X = {e1, si} for some i, where 1 ≤ i ≤ n. First, we show that {e1, ei} ∈ EH(C2 n). Since {ei, si} ∈ EH(C2 n) for some i, by Remark 3, {ei, si} ∈ EH(C2 n) for all i. By Lemma 1, {ei+1, si} ∈ EH(C2 n) for all i. Now, {ei, ei+1} = {ei, si}∆{ei+1, si} ∈ EH(C2 n) for all i. In particular, {e1, e2} ∈ EH(C2 n). Thus, for 3 ≤ i ≤ n, X = {e1, ei} = {e1, e2}∆{e2, e3}∆ · · ·∆{ei−1, ei} ∈ EH(C2 n). Next, we show that {e1, si} ∈ EH(C2 n). Clearly, {e1, s1} ∈ EH(C2 n). Now, for 2 ≤ i ≤ n, we have {e1, si} = {e1, ei}∆{ei, si} ∈ EH(C2 n). Thus, X ∈ EH(C2 n). Therefore, B ⊆ EH(C2 n). Now, we give necessary and sufficient conditions for a subgraph H to be a generator subgraph of C2 n. Lemma 3. Let H be a subgraph of C2 n where |E(H)| is odd. Then H is a generator subgraph of C2 n if and only if {ei, si} ∈ EH(C2 n) for some integer i, where 1 ≤ i ≤ n. Proof. Let us consider the labeling of C2 n. Assume that H is a generator subgraph of C2 n. Then {ei, si} ∈ EH(C2 n) for all i. Conversely, let H be a subgraph of C2 n. We show {ei}, {si} ∈ EH(C2 n) for all i, where 1 ≤ i ≤ n. Since {ei, si} ∈ EH(C2 n) for some integer i, there exists A ∈ EH(C2 n), such that ei ∈ A. Observe that |A| is odd since |E(H)| is odd. Define B = A\{ei}. Then |B| is even so B ∈ E ∗(C2 n). By Lemma 2, B ∈ EH(C2 n). Thus, {ei} = A∆B ∈ EH(C2 n). By rotational symmetry on C2 n, {ei} ∈ EH(C2 n) for all i. In similar argument, we can show that {si} ∈ EH(C2 n) for all i. By Remark 1, H is a generator subgraph of C2 n. 2.2. Generator Subgraphs of the Square of a Cycle First, we determine the necessary and sufficient conditions for star graph Sq to be a generator subgraph of C2 n. Theorem 9. Let q and n be positive integers. Then the star Sq is a generator subgraph of C2 n if and only if q = 1 or q = 3. Proof. Assume that Sq is a generator subgraph of C2 n. We show that q = 1 or q = 3. Suppose on the contrary, q ̸= 1 and q ̸= 3. Note that C2 n is 4-regular. Then by Theorem 1 R. Mame / Eur. J. Pure Appl. Math, 17 (4) (2024), 3815-3825 3821 , q < 4. This implies that q = 2. Thus |E(Sq)| = 2, which is even. This is a contradiction in view of Theorem 1. Therefore, q = 1 or q = 3. Conversely, suppose q = 1 or q = 3. We show that Sq is a generator subgraph of C2 n. Case 1, q = 1. Then Sq is isomorphic to P2. By Theorem 3, Sq is a generator subgraph of C2 n. For case 2, q = 3, since C2 n is a 4-regular graph and q < 4 then the star Sq is a generator subgraph of C2 n in view of Corollary 1. The theorem below determines the necessary and sufficient conditions for the path Pk to be a generator subgraph of C2 n. Theorem 10. Let k and n are positive integers. Then the path Pk is a generator subgraph of C2 n if and only if k is even and 2 ≤ k ≤ n. Proof. Assume that Pk is a generator subgraph of C2 n. Then by Theorem 1, |E(Pk)| must be odd. This implies that k is even. Next, we claim that 2 ≤ k ≤ n. Suppose not, then either k = 1 or k > n. If k = 1, then Pk has no edge so EPk (C2 n) = ∅. If k > n, then Pk is not a subgraph of C2 n, so EPk (C2 n) = ∅ also. In either case EPk (C2 n) = ∅ ≠ E (C2 n). This is a contradiction to the assumption that Pk is a generator subgraph of C2 n. Conversely, since k is even, |E(Pk)| is odd. If k = 2, then Pk ≃ P2. By theorem 3, Pk is a generator subgraph of C2 n.Let us assume that 2 < k ≤ n. Consider the labeling of C2 n. Let A = {e1, e2, e3, . . . , ek} and define B = A\{e2}∪{s1}. It can be verified that A,B ∈ EPk (C2 n), as shown in Figure 3. .................................... .................................... .................................... .................................... .................................... .................................... .................................... ............................................................................................................................................................ .............................................................................. .............................................................................. .............. ............. ............. ............. ............. ............ e1 e2 e3 ek−1 ek C2 n[A] .................................... .................................... .................................... .................................... .................................... .................................... .................................... .............................................................................. .............................................................................. .............................................................................. .............. ............. ............. ............. ............. ............ ........................................................................................................................................................ ........ ........ ........ e1 e3 ek−1 ek s1 C2 n[B] ........ ........ ........ Figure 3: Illustrating the subgraphs C2 n[A] and C2 n[B] Now, A∆B = {e2, s1} ∈ EPk (C2 n). By Lemma 2, {e1, s1} ∈ EPk (C2 n). By Lemma 3.4.3 , Pk is a generator subgraph of C2 n. We consider another class of subgraphs of C2 n, the tadpole graph. The (k, r)- tadpole graph, denoted by Tk,r, is the graph obtained by joining a cycle graph Ck to a path graph Pr with an edge [a, b] where a ∈ V (Ck) and b ∈ V (Pr), deg(b) in Pr is either 0 or 1. For instance the graphs T6,2 and T8,1 are shown in Figure 4. First, we investigated the tadpole graph T3,2. The result is stated below. Theorem 11. The tadpole graph T3,2 is a generator subgraph of C2 n. Proof. Consider the labeling of C2 n. Let A = {e1, e2, e3, e4, s1} and define B = A\{e3}∪ {s3}. As shown in Figure 5, it can be observed that C2 n[A] ≃ T3,2 and C2 n[B] ≃ T3,2. Thus R. Mame / Eur. J. Pure Appl. Math, 17 (4) (2024), 3815-3825 3822 .............................. ...... .............................. ...... ......... ........ ........ ........ ........ ...... ................. ................ .............. .............................. ...... ............................................... .............................. ...... ............................................... .............................. ...... ................. ................ .............. .............................. ...... ......... ........ ........ ........ ........ ...... ......... ........ ........ ........ ........ ...... .............................. ...... ......... ........ ........ ........ ........ ...... .............................. ...... .............................. ...... T6,2 .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................. .................................. .................................. .................................. .......... ......... ......... ...... .......... ......... ......... ...... ...................... ............ ...................... ............ ......... ........ ........ ........ ........ ...... T8,1 Figure 4: Illustrating the graphs T6,2 and T8,1 .................................... .................................... .................................... .................................... .................................... ............................................................................................................................................................ .............. ............. ............. ............. ............. ............ ................................. ................................ ............. ........................................................................................................................................................ e1 e2 e3 e4 s1 C2 n[A] .................................... .................................... .................................... .................................... .................................... ............................................................................................................................................................ ................................. ................................ ............. ........................................................................................................................................................ .................. .................. ................. .................. ................. .................. .................. .................. .......... e1 e2 e4 C2 n[B] s1 s3 Figure 5: Illustrating the subgraphs C2 n[A] and C2 n[B] A,B ∈ ET3,2(C 2 n). Now, A∆B = {e3, s3} ∈ ET3,2(C 2 n). By Lemma 3, T3,2 is a generator subgraph of C2 n. The next result gives the characterization for the tadpole T3,r so that it is a generator subgraph of C2 n. Theorem 12. Let n and r be positive integers. Then the tadpole graph T3,r is a generator subgraph of C2 n if and only if r is even and 2 ≤ r ≤ n− 3. Proof. Assume that the tadpole graph T3,r is a generator subgraph of C2 n. Then the size of T3,r must be odd in view of Theorem 1. It follows that r is even. We claim that 2 ≤ r ≤ n − 3. Suppose, on the contrary, r = 1 or r > n − 3. If r = 1 then T3,r consists of four edges, which are even. This is a contradiction by Theorem 1. If r > n − 3, then the order of T3,r is greater than n. Meaning, T3,r is not a subgraph of C2 n. Again, a contradiction to the assumption that T3,r is a generator subgraph of C2 n. Conversely, assume that r is even and 2 ≤ r ≤ n−3. We show that T3,r is a generator subgraph of C2 n. Since r is even, then the size of the T3,r is odd. If r = 2, then T3,r is a generator subgraph of C2 n by Theorem 11. Let us assume that 2 < r ≤ n− 3. Consider the labeling of C2 n. Let A = {en−1, sn−1, sn, e1, e2, . . . , er}and define B = A\{e1} ∪ {sn}. It can be verified that A,B ∈ ET3,r(C 2 n), as shown in Figure 6. Now, A∆B = {e1, sn} ∈ ET3,r(C 2 n). By Lemma 1, {e1, sn} ∈ E (C2 n). By Lemma 3, T3,r is a generator subgraph of C2 n. By a kite graph, denoted by Ktr,s, we mean a graph formed by joining a path graph Pr, a path graph Ps and a cycle C3 with two edges. One edge joins one vertex of C3 to a R. Mame / Eur. J. Pure Appl. Math, 17 (4) (2024), 3815-3825 3823 .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................................................................................................................................................................................................................................................. ............. ............. ............. ............. ............. ............. ............. ............. .......... ................................ ................................ ................................ .................... ................................. ................................ ................................ ......................... ................... .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. ................. .......................................................................................................................... e1 e2 er−1 en−1 en C2 n[A] er sn−1 .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... ........................................................................................................................................ ............. ............. ............. ............. ............. ............. ............. ............. .......... ................................ ................................ ................................ .................... ................................. ................................ ................................ ......................... ................... .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. ................. .......................................................................................................................... .......................................................................................................................................................................................................................................... e2 er−1 en−1 en sn sn−1 C2 n[B] er sn−1 ........ ........ ........ ........ ........ ........ Figure 6: Illustrating the subgraphs C2 n[A] and C2 n[B] vertex of Pr whose degree in Pr is either 0 or 1. The second edge joins another vertex of C3 to a vertex of Ps whose degree in Ps is either 0 or 1. Some examples of kites are shown in Figure 7. ............................................................................................................................................ ............................................................................................. .................................... ........... .......... .......... .......... .......... .......... .......... .......... .......... .. .. .................................. .................................... ......... ........ ........ ........ ........ ....... .................................... .................................... ................................................ .................................... .................................... Kt1,1 ............................................................................................................................................ ............................................................................................. .................................... ........... .......... .......... .......... .......... .......... .......... .......... .......... .. .. .................................. .................................... ......... ........ ........ ........ ........ ....... .................................... .................................... ................................................ .................................... ................................................ .................................... ................................................ .................................... .................................... Kt1,3 ............................................................................................................................................ ............................................................................................. .................................... ........... .......... .......... .......... .......... .......... .......... .......... .......... .. .. .................................. .................................... ......... ........ ........ ........ ........ ....... .................................... ......... ........ ........ ........ ........ ....... .................................... .................................... ................................................ .................................... ................................................ .................................... .................................... Kt2,2 Figure 7: Illustrating the graphs Kt2,2, Kt1,3 and Kt1,1 The following remark can be easily observed. Remark 4. The size and order of the graph Ktr,s is r + s+ 3. Thus, Ktr,s is a subgraph of C2 n if and only if r + s ≤ n− 3. First we show that Kt1,1 is a generator subgraph of C2 n Theorem 13. The Kite graph Kt1,1 is a generator subgraph of C2 n. Proof. Consider the labeling of C2 n. Let A = {en−1, sn−1, en, en−2, e1}. Define B = A\{e1} ∪ {s1}. It can be verified that A,B ∈ EKt1,1(C 2 n). Thus, A + B = {e1, s1} ∈ EKt1,1(C 2 n). Clearly, the size of Kt1,1 is 5, which is odd. By Lemma 3, Kt1,1 is a generator subgraph of C2 n. The next result gives the criteria for the subgraph Ktr,s to be a generator subgraph of C2 n. REFERENCES 3824 Theorem 14. Let r and s be positive integers. Then the kite graph Ktr,s is a generator subgraph of C2 n if and only if r + s is even and r + s ≤ n− 3. Proof. Assume that the kite Ktr,s is a generator subgraph of C2 n. By Theorem 1, the size of Ktr,s is odd. It follows that that r+ s is even in view of Remark 4. We claim that r+s ≤ n−3. Suppose r+s > n−3, then by Remark 4, Ktr,s is not a subgraph of C2 n. This is a contradiction. Conversely, since r+s is even and r+s ≤ n−3, the size of Ktr,s is odd and Ktr,s is a subgraph of C2 n. So the uniform set EKtr,s(C 2 n) is not empty. If r = s = 1 then Ktr,s is a generator subgraph of C2 n in view of Theorem 13. Let us assume that r, s > 1. Consider the labeling of C2 n, let A = {en, e1, sn, e2, e3, . . . , er+1, en−1, en−2, . . . , en−s}. Define B = A\{e2} ∪ {s1}. It can be verified that A,B ∈ EKtr,s(C 2 n). Thus, A + B = {e2, s1} ∈ EKtr,s(C 2 n). By Lemma 1, {e1, s1} ∈ EKtr,s(C 2 n). By Lemma 3,Ktr,s is a generator subgraph of C2 n. 3. Summary and Conclusions Some classes of generator subgraphs of C2 n were found, such as the star graphs, path graphs,(3, r)− tadpole graphs and kite graphs. Characterization for the generator sub- graphs of the square of a cycle is still open. Acknowledgements Part of this work was done while the author was taking Ph.D. fellowship at the Batan- gas State University through the Faculty Scholarship grant of the Batangas State Uni- versity under the research supervision of Dr. Neil M. Mame. Also, the author wishes to thank the anonymous reviewers for their comments and suggestions, which have signifi- cantly improved this manuscript. References [1] C. Alib and D. Magpantay. Some parameters of the central graphs of the identity graphs of finite cyclic groups. European Journal of Pure and Applied Mathematics, 15(3):1098–1112, 2022. [2] J. Bonifacio, C. Adaya, and D. Magpantay. On the j− edge intersection graph of cycle graph. European Journal of Pure and Applied Mathematics, 16(4):2476–2498, 2023. [3] G. Chartrand and P. Zhang. Introduction to Graph Theory. Mc Graw Hill, Singapore, 2005. [4] S. Gervacio. Generator graphs. In 4th International Conference On Combinatorial Mathematics and Combinatorial Computing., U.A., New Zealand, 2008. REFERENCES 3825 [5] S. Gervacio. Determination of uniform generating sets of the edge space of some graphs. research project under URCO, De La Salle University-Manila, 2009. [6] S. Gervacio and N. Mame. Universal and primitive graphs. In Proc., Osaka Univer- sity - De La Salle University Academic Research Workshop., pages 51–54, Manila, Philippines, 2007. Osaka University- De La Salle University-Manila. [7] S. Gervacio, M. Valdez, and D. Bengo. Generator subgraphs of fans and wheels. In Proc., Osaka University - De La Salle University Academic Research Workshop., Manila, Philippines, 2008. Osaka University- De La Salle University-Manila. [8] N. Mame and S. Gervacio. A note on generator subgraph of a graph. Electronic Journal of Graph Theory and Applications, 8(3):17–27, 2020. [9] E. Nering. Linear Algebra and Matrix Theory. John Wiley and Sons, USA, 1970. [10] M. Pelagio, K. Mendoza, and N. Mame. On the k− restricted intersection graph. European Journal of Pure and Applied Mathematics, 17(3):1779–1803, 2024. [11] L. Ruivivar. Some generator subgraphs of the complete bipartite graph. In Proc., 5th Asian Mathematical Conference., pages 516–520, Malaysia, 2009. South East Asian Mathematical Society.