EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 16, No. 3, 2023, 1894-1901 ISSN 1307-5543 – ejpam.com Published by New York Business Global The Generator Graph of a Group Teresa L. Tacbobo Mathematics Department, College of Arts and Sciences, Bukidnon State University, Malaybalay City, Bukidnon, Philippines Abstract. This paper presents a way to represent a group using a graph, which involves the concept of a generator element of a group. The graph representing a group is called the generator graph. In the generator graph, the vertices correspond to the elements of the group, and two vertices, x and y, are connected by an edge if either x or y serves as a generator for the group. The paper investigates some properties of these generator graphs and obtains the generator graphs for specific groups. Additionally, it explores the relationship between the generator graph of a group and the generating graph introduced by Lucchini et al. in their work [7]. 2020 Mathematics Subject Classifications: 05C25 Key Words and Phrases: Graph, Group, Generator graph, Generating graph 1. Introduction In graph theory, a graph is a collection of points called vertices, and edges that connect the vertices. It is widely known for its applications in networks such as Facebook. Graphs can be used to model relationships or connections between objects, describe events and even in analysis and problem solving. In most cases, objects are represented by vertices while the relationship between two objects is represented by an edge in the graph. A group can be briefly defined as a set with an associative binary operation, an identity element, and inverses with respect to that identity element. For example, the set of real numbers is a group under the usual addition operation. Group theory also finds application in chemistry in the study of the group of symmetries of crystals and molecules. Basic concepts in graph theory and group theory may be found in [4], and in [3] and [5] respectively. The interplay between group theory and graph theory has been explored in literature for many years. Some researchers represent groups as graphs, while others do it the other way around. The concept of identity graph of a group is introduced in [6]. The identity graph is a graph with elements of group as vertices and adjacency of vertices is defined in terms of the identity element of a group. Two vertices x and y can be joined by an DOI: https://doi.org/10.29020/nybg.ejpam.v16i3.4863 Email address: teresatacbobo@buksu.edu.ph (T. L. Tacbobo) https://www.ejpam.com 1894 © 2023 EJPAM All rights reserved. T. L. Tacbobo / Eur. J. Pure Appl. Math, 16 (3) (2023), 1894-1901 1895 edge in the identity graph if xy = e (e− being the identity of a group). Lucchini et al. introduced the concept of generating graph of a group in [7]. The generating graph of a group is also a graph with the elements of group as vertices, and adjacency of vertices is restricted to subgroup generated by the given pair of vertices. The generating graph of symmetric groups is considered in [2]. Other graphs associated with finite groups are discussed in [8]. The above ideas of group representations have motivated the present paper to introduce a graph with the elements of the group as vertices, and adjacency of vertices is defined in terms of the generator element of the group. The graph will be called the generator graph of a group. 2. Basic Concepts 2.1. Graphs Althroughout this paper, we only consider undirected graphs with no loops. The basic definitions and concepts used in this study are adopted from [1]. Given a graph G = (V (G), E(G)), the sets V (G) and E(G) are, respectively, the vertex set and edge set of G. The cardinality of V (G), denoted |V (G)|, is called the order of G and the cardinality |E(G)| of E(G) is the size of G. Each element of V (G) is considered a vertex of G. If u, v ∈ V (G) and e = [u, v] is in E(G), then e is an edge of G, and e is said to join u and v. In this case, it is customary to write e = uv and say that u and v are adjacent, while u and e are incident, as v and e are. Adjacent vertices are also called neighbors. The degree degG(v) of a vertex v is the number of edges incident to v. A subgraph of a graph G is a graph having all its vertices and edges in G. It is a spanning subgraph if it contains all the vertices of G. The induced subgraph ⟨S⟩ is the maximal subgraph with vertex set S. The path of order n, denoted by Pn = [v1, v2, ..., vn], is the graph with vertices v1, v2, ..., vn, and edges v1v2, v2v3, ..., vn−1vn. We also call Pn as a u-v path of length n− 1, where u = v1 and v = vn. A graph G is connected if there is a path that joins each pair of vertices. A graph G is called complete if every pair of its vertices is adjacent. Kn denotes the complete graph of order n. The graph K1 is the trivial graph. It is trivial to see that Kn contains n(n− 1)/2 edges. A graph with an empty edge set is called a null graph. A null graph of order n is denoted Kn. The join G1 +G2 of two graphs G1 and G2 is their disjoint union together with all the edges that connect all the vertices of G1 with all the vertices of G2. 2.2. Groups A binary operation or law of composition on a set G is a function G × G → G that assigns to each pair (a, b) ∈ G×G a unique element a◦b, or ab ∈ G, called the composition of a and b. A group (G, ◦) is a set G together with a law of composition (a, b) 7→ a ◦ b that satisfies the following axioms: (i) the law of composition is associative, i.e., (a ◦ b) ◦ c = a◦ (b◦ c) for a, b, c ∈ G; (ii) there exists an element e ∈ G called the identity element, such T. L. Tacbobo / Eur. J. Pure Appl. Math, 16 (3) (2023), 1894-1901 1896 that for any element a ∈ G, e ◦ a = a ◦ e = a; and for each element a ∈ G, there exists an inverse element in G, denoted by a−1, such that a ◦ a−1 = a−1 ◦ a = e. A group G with the property that a ◦ b = b ◦ a for all a, b ∈ G is called abelian or commutative. Groups not satisfying this property are said to be non−abelian or noncom- mutative. A subgroup H of a group G is a subset H of G such that when the group operation of G is restricted to H, H is a group in its own right. The subgroup H = e of a group G is called the trivial subgroup. A subgroup that is a proper subset of G is called a proper subgroup. Let G be a group, and let a be any element in G. Then the set (a) = {ak : k is an integer} is a subgroup of G. Furthermore, (a) is the smallest subgroup of G that contains a. For a ∈ G, we call (a) the cyclic subgroup generated by a. If G contains some element a such that G = (a), then G is a cyclic group. In this case, a is a generator of G. The order of a is the smallest positive integer n such that an = e, and we write |a| = n. If there is no such integer n, we say that the order of a is infinite and write |a| = ∞ to denote the order of a.b Note that a cyclic group can have more than a single generator. For example, from the group of integers modulo 6, both 1 and 5 generate Z6; hence, Z6 is a cyclic group. Not every element in a cyclic group is necessarily a generator of the group. The order of 2 ∈ Z6 is 3. The cyclic subgroup generated by 2 is (2) = {0, 2, 4}. The Klien 4-group V is an abelian noncyclic group consisting of 3 elements a, b, c and an identity element e, with the property that a2 = b2 = c2 = e. 3. Generator Graph of Group Definition 1. The generator graph gg(G) of a group G is a graph whose vertices are the elements of G, and two vertices x and y in gg(G) are joined by an edge if either x or y is a generator of G. Figure 1 illustrates the generator graphs gg(Z6) and gg(Z5) of groups Z6 under addition modulo 6 and Z5 under addition modulo 5, respectively. The set SZ6 = {1, 5} is the set of all generators of Z6 while the set SZ5 = {1, 2, 3, 4} is the set of all generators of Z5. Observe that in Z6, degZ6(1) = degZ6(5) = 5 = |V (gg(G))|−1 while degZ6(0) = degZ6(2) = degZ6(3) = degZ6(4) = 2 = |SZ6 |. Theorem 1. Let G be a group of order n > 1 and, SG be the set of all generators of G. Let x ∈ V (gg(G)). Then (i) degG(x) = n− 1 if x ∈ SG and degG(x) = |SG| if x /∈ SG; and (ii) the size of gg(G) is given by |E(gg(G))| = |SG| 2 (2n− |SG| − 1). . T. L. Tacbobo / Eur. J. Pure Appl. Math, 16 (3) (2023), 1894-1901 1897 .................................... .................................... .................................... .................................... .................................... .................................... ................... .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. ........... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... .. ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ....................................................................................................................................................................... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........ ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ......................................................................................................................................................................................................................................................... ...................................................................................................................................................................................................................................................... ........................................................................................................• • 1 5 0 2 3 4 gg(Z6) .................................... .................................... .................................... .................................... .................................... ..................................................................................................................................... ................................................................................................................................................................................................................................................................................ ............................................................................................................................................................................................................................................................................................................................................................... .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. ....................................................................................................................................................................................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... ........... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... . ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .. ............................................................................................................................................................................................................................................ ..................................................................................................................................................................................................... • • •• 0 1 2 34 gg(Z5) Figure 1: The generator graphs gg(Z6) and gg(Z5). Proof. (i) If x ∈ SG, then x is adjacent to the other n − 1 vertices of gg(G). In this case, degG(x) = n − 1. If x /∈ SG , then x is adjacent only to the |SG| vertices in gg(G). In this case, degG(x) = |SG|. (ii) The size of gg(G) is |E(gg(G))| = 1 2 ∑ x∈V (gg(G)) (degG(x)) = 1 2 [|SG|(n− 1) + (n− |SG|)|SG|] = |SG| 2 [(n− 1) + (n− |SG|)] = |SG| 2 (2n− |SG| − 1). Theorem 2. Let G be a group of order n > 1. The generator graph gg(G) of G is complete if and only if n is prime. Proof. Assume that gg(G) is complete, and suppose the order n > 1 of G is not prime. This implies that for some integer k ̸= n there exists an integers m ̸= n such that km = n, and k is the order of some vertex a ∈ V (gg(G)), i.e., (a) ̸= G. This means that a is not a generator of G. Consequently, vertex a is not adjacent to the identity element of G in gg(G). Thus, degG(a) ≤ n− 2 in gg(G). This is a contradiction to the assumption that gg(G) is complete. Therefore, the order n of G must be prime. Suppose that the order of G is prime, and let e be the identity element of G. Then for all x ∈ G\{e}, (x) = G. This means that x is a generator of G, and x is adjacent to all other n − 1 vertices of gg(G). Thus, deggg(G)(x) = n − 1 for all x ∈ G\{e}. Since T. L. Tacbobo / Eur. J. Pure Appl. Math, 16 (3) (2023), 1894-1901 1898 all elements of x ∈ G\{e} are generators, all |x ∈ G\{e}| = n − 1 vertices of gg(G) are adjacent to the identity element e of G in gg(G). So, deg(e) = n− 1. This proves that for all x ∈ V (gg(G)), deggg(G)(x) = n− 1. Therefore, gg(G) is a complete graph. Example 1. Let Zp be the group of integers under addition modulo p, where p is prime. Then gg(Zp) = Kp.The graph gg(Z5) of Z5 in Figure 1 is a complete graph K5. Remark 1. Let G be a nontrivial group. The generator graph of G is connected if and only if G is cyclic. Example 2. In Figure 1, the generator graphs gg(Z6) of Z6 under addition modulo 6 and gg(Z5) of Z5 under addition modulo 5 are connected. It is easy to verify that the generator graph gg(V ) of Klien 4-group V is a null graph of order 4 which is disconnected. Theorem 3. Let G be a cyclic group of order n > 1, and SG be the set of all generators of G. Then each of the following is true: (i) the induced subgraph < SG > generated by SG of gg(G) is the complete graph K|SG|; and (ii) the induced subgraph < G\SG > generated by G\SG of gg(G) is the empty graph Kn−|SG|. Proof. (i) Since G is cyclic and n > 1, there exist a ∈ SG such that (a) = G, i.e., SG ̸= ∅. Then for every pair x and y in SG, x and y generate each other, i.e., x ∈ (y) and y ∈ (x). Hence, x and y are adjacent in gg(G) for all x and y in SG. This means also that x and y are adjacent in < SG > for all x and y in SG. Therefore, < SG > is a complete graph, i.e., < SG >= K|SG|. (ii) For every x, y ∈ G\SG, x and y are not adjacent in gg(G). Thus, x and y are also not adjacent in < G\SG >. Therefore, E(< G\SG >) = ∅ and < G\SG > is an empty graph. Example 3. In Z6, ⟨SZ6⟩ = ⟨{1, 5}⟩ is a complete subgraph while ⟨Z6\SZ6⟩ = ⟨{0, 2, 3, 4}⟩ is a null subgraph of Z6. These are illustrated in Figure 2 and Figure 3, respectively. .................................... ...................................................................................................................................................................................................................................• • 1 5 < SZ6) > Figure 2: The induced subgraph of SZ6 = {1, 5} of Z6 under addition modulo 6. T. L. Tacbobo / Eur. J. Pure Appl. Math, 16 (3) (2023), 1894-1901 1899 .................................... .................................... .................................... ....................................0 2 3 4 < Z6\(SZ6) > Figure 3: The induced subgraph of Z6\SZ6under addition modulo 6. Theorem 4. Let G be a cyclic group of order n > 1, and SG be the set of all generators of G. Then G = K|SG| +Kn−|SG|. Proof. Let G be a cyclic group of order n > 1,and let SG be the set of all generators of G. For x, y ∈ V (ggG), if x, y ∈ G\SG, then xy /∈ E(ggG). This case is the same as connecting the generator element of the group to all other elements of the group whether they are another generator or non-generators. In other words, all gerators of G are adjacent in gg(G), forming a complete subgroup. The other edges are formed by connecting each genrator by an edge to each of the non-generators. Therefore, the generator graph ggG can be described as the join of complete graph of order |SG| and null graph of order n− |SG|. 4. Relationship between generating graph and generator graph of group The concept of the generating graph of a group was introduced by Luchini et al in [7]. In their study, two non-generator elements of a group G are adjacent in the generating graph of G if they generate G, while they are not adjacent in the generator graph of G. Definition 2. [7] The generating graph Γ(G) of a group G is the graph defined on the elements of G, with edge between two vertices if and only if they generate G. Figure 4 illustrates the generating graph of the group of integers modulo 6, Z6. Both sets {2, 3}) and {3, 4} generate the group Z6, that is, ({2, 3}) = Z6 and ({3, 4}) = Z6. Thus, (2, 3), (3, 4) ∈ E(Z6). Note that 2, 3 and 4 are not generators of G, hence none of these vertices are adjacent in the generator graph of G. This can be verified in Figure 1. This observation is generalized in the next result. .................................... .................................... .................................... .................................... .................................... .................................... ................... .................. .................. .................. .................. .................. .................. .................. ..... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ..... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........................................................................................................... ........... ........... ........... ........... ........... ........... ........... .. ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .......................................................................................................................................................... ...................................................................................................................................................... .............................................................. ............ ........... ........... ........... ........... ........... ........... ........... .. ..............................................................• • • • • •1 5 0 2 3 4 Γ(Z6) Figure 4: The generating graph of Γ(Z6) REFERENCES 1900 Theorem 5. Let G be a group. Then the generator graph of G is a spanning subgraph of the generating graph of G. Proof. Let G be a group. By definition of the generator graph and the generating graph, V (ggG) = V (Γ(G)). Let x, y ∈ V (ggG). If both or one of x and y are generators, then the set {x, y} clearly generates G. In this case, xy ∈ E(ggG) and xy ∈ E(Γ(G)). If both x and y are non-generators, then the set {x, y} either generates G or does not generate G. In this case, xy /∈ E(ggG) but either xy ∈ E(Γ(G)) or xy /∈ E(Γ(G)). It follows that E(ggG) ⊆ E(ΓG). Therefore, gg(G) is a spanning subgraph of Γ(G). Example 4. The dihedral group Dn is the symmetry group, which includes rotations and reflections, of an n-sided regular polygon for n > 1. Dihedral groups Dn are non-Abelian permutation groups for n > 2. The group Dn has elements r0, ..., rn−1 that represents rotations and s0, ..., sn−1 that represents reflections. Their compositions are given by: rirj = r(i+j)(mod n), risj = s(i+j)(mod n), sirj = r(i−j)(mod n), and sisj = r(i−j)(mod n) where i, j ∈ {0, 1, 2}. For n3, D3 = {r0, r1, r2, s0, s1, s2}, representing the symmetric group of triangle with the identity r0. Note that the generator graph of D3 is the empty graph of order 6, i.e., gg(D3) = K6, since D3 has no generator. It is easy to verify that Γ(D3) = (K2 +K3) ∪K1. Clearly, V (gg(D3)) ⊂ V (K2 +K3) ∪K1) = Γ(D3). Therefore, gg(D3) is a spanning subgraph of Γ(D3). 5. Conclusion This paper introduces the concept of the generator graph of a group. The properties of the generator graph are presented in terms its structure, the degree of a vertex, and size of the induced subgraph of the set of generators or non-generators. Additionally, the generator graphs of some special graphs are also presented. It has been shown that the generator graph of a group forms a spanning subgraph of the generating graph. Acknowledgements The author is very grateful to the referees for the corrections and suggestions they made in the initial manuscript. The author would also like to thank the Center of Mathematical Innovations, Bukidnon State University, for funding this research. References [1] F Buckley and F Harary. Distance in Graphs. Addison-Wesley, Redwood City, 1990. [2] F Erdem. On the generating graphs of symmetric groups. Journal of Group Theory (2018), 21(4), pp. 629-649. [3] J Fraleigh. A First Course in Abstract Algebra (5th ed.), Addison-Wesley, 2000. REFERENCES 1901 [4] F Harary.Graph Theory.Addison-Wesley Publication Company, Inc., Massachusetts, 1972. [5] T Hungerford. Abstract Algebra: an Introduction (2nd ed.), Sunders College, 1991. [6] WB Kandasamy and F Smarandache. Group as Graphs. Romania: Editura CuArt, 2009. [7] A Lucchini, A Maroti and C. Roney-Dougal. On the Generating Graph of a Simple Group. Journal of the Australian Mathematical Society (2018) 103(1), 91-103. [8] Y Zakaraya. Graphs from Finite Groups: An Overview. Proceedings of the 53rd Mathematical Association of Nigeria Annual Conference, September 2016.