EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2025, Vol. 18, Issue 2, Article Number 5499 ISSN 1307-5543 – ejpam.com Published by New York Business Global 1 Middle Graph of the Identity Graph of Finite Cyclic2 and Dihedral Groups3 Jiel Mark D. Jagmis1, Daryl M. Magpantay2,∗4 1 College of Arts and Sciences, Camarines Sur Polytechnic Colleges, Nabua, Camarines5 Sur, Philippines6 2 Batangas State University - The National Engineering University, Pablo Borbon Campus,7 Batangas City, Batangas, Philippines8 9 Abstract. Given a group G with e as the identity element, the identity graph ΓG having the vertex-set G and the edge-set E satisfies two conditions: (i) for every x, y ∈ G where x ̸= y, x and y are adjacent in ΓG if and only if xy = e; (ii) for each x ∈ G, x and e are adjacent in ΓG. The middle graph of G denoted by M(G) is the graph with vertex set V (G) ∪ E(G) where two vertices will be adjacent if and only if they are either adjacent edges of G or one is a vertex and the other is an edge incident to it. It can be obtained by inserting a new vertex into every edge of G and connecting the new obtained vertices if they are adjacent edges in G. In this paper, we constructed the middle graph of the identity graph particular for finite cyclic and dihedral groups. Some parameters of a graph such as the size, order, graph measurements, independence number, domination number, vertex chromatic number and edge chromatic number were also investigated. 2020 Mathematics Subject Classifications: 0510 Key Words and Phrases: Middle Graph, Identity Graph, Cyclic Groups, Dihedral Groups,11 Graph Properties12 13 1. Introduction14 The linking of group theory to graph theory was started in 2009 in the book of [1] by15 creating a new kind of graph from the concepts of group theory. They represented the16 finite groups in terms of graphs which they called identity graphs or identity graphs since17 the identity element of the group is the main role in order to create a graph.18 19 A.D. Godase [2] in 2015 gave some examples of the identity graphs of some finite20 groups particular in finite cyclic and dihedral groups which he discovered that the graph21 formed were consists of lines and triangles. In the papers [3] and [4], the authors further22 ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v18i2.5499 Email addresses: jagmis656@gmail.com (J. M. Jamis), daryl.magpantay@g.batstate-u.edu.ph (D. M. Magpantay https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0) J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 2 of 18 studied the said graph by investigating its properties and characteristics.23 24 Another focus of studies in graph theory is the construction new graphs from another25 graph. Given a graph, operation will be defined that yields to another form of graph. One26 particular example is the paper of Akiyama, Hamada, and Yoshimura [5] which introduced27 the concept of the middle graph and established some characterizations in particular for28 some common classes of graphs. The middle graph of a graph is obtained by inserting a29 new vertex into every edge of the original graph and connecting the new obtained vertices30 if they are adjacent edges in the original graph.31 32 The combination of two concepts motivates the authors to explore the middle graphs33 of the identity graph of the finite cyclic and dihedral groups. This is in parallel with34 the study of Murusegan and Nair [6] which discussed the (1, 2)-domination in middle and35 central graph of a star, cycle and path. They also established some upperbounds and36 lower bounds. Later on 2017, they investigated the power domination of middle graph of37 path, cycle and star. Alib et al. [7] presented the construction of the central graph of the38 identity graph of finite cyclic group and investigated some of its graph properties.39 40 This paper presents the construction of the middle graphs of the identity graph of41 the finite cyclic and dihedral groups. The properties particular in graph measurements,42 independence number, domination number and graph coloring were also investigated.43 2. Preliminaries44 For the purpose of further understanding concepts, examples, and illustrations are45 given.46 2.1. Group Theory47 This section contains some basic concepts in group theory and its examples that will48 be needed in the discussion of the following chapters. Groups can be finite or infinite. In49 general, groups can be classified into two categories, these are the cyclic and noncyclic50 groups. In this paper, we focus in finite cyclic groups and the dihedral groups. Let us51 start by defininng a binary operation.52 Definition 1. Let S be a set. A binary operation ∗ on S is a function that assigns each53 ordered pair of elements of S an element of S.54 Consider the set of even integers S = 2Z using the addition as the operation. If we55 take a = 2k, b = j ∈ S, for some integers k and j, a+ b = 2k+2j = 2(k+ j) which is also56 an even integer. Thus, addition is a binary operation in S.57 Definition 2. A group is a non-empty set G with binary operation ∗ such that58 i. a ∗ (b ∗ c) = (a ∗ b) ∗ c for all a, b, c in G (associativity),59 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 3 of 18 ii. there is an element e ∈ G such that a ∗ e = e ∗ a = a for all a ∈ G (existence of60 identity),61 iii. if a ∈ G, then there is an element a−1 ∈ G such that a∗a−1 = a−1 ∗a = e (existence62 of inverse).63 Example 1. The set of integers is a group under the operation of ordinary addition. Note64 that the set of integers under the operation of addition is closed, associative, contains iden-65 tity element 0, and for any integer a it has an −a.66 67 The set of integers under ordinary multiplication is not a group. The third property68 fails since there is no integer b such that 2b = 1 where 1 is the identity element.69 70 Now we will define a cyclic subgroup,71 Definition 3. If G is a group and a ∈ G, then the cyclic subgroup generated by a is72 the set73 ⟨a⟩ = {an : n ∈ Z} If, in G, there exists an element a such that G = ⟨a⟩, then we say that G is a cyclic74 group and a is a generator of G. We may also say that G is a group generated by a.75 If no such element exists in G, then G is said to be a noncyclic group.76 Example 2. Let G = Z,+. Then G = ⟨1⟩ = ⟨−1⟩, so G is cyclic. On the other hand,77 G = Q,+ is noncyclic, since there is no rational number which generates all possible78 rational numbers. For the same reason, G = R,+ is noncyclic79 Another type of finite groups are dihedral groups which belongs to the classification80 of noncyclic.81 Definition 4. The group of symmetries of an n-sided regular polygon for n ≥ 1 with82 rotations and reflections is termed Dihedral group, which is denoted as Dn. The order83 of the Dihedral group is 2n.84 For n ≥ 3, Dn is the group of symmetries of a regular polygon with n-sides. Number85 the vertices 1, ..., n in the counterclockwise direction. Let r be the rotation through 2π/n86 about the centre of polygon (so i 7→ i + 1 mod n), and let s be the reflection in the87 line (= rotation about the line) through the vertex 1 and the centre of the polygon (so88 i 7→ n+ 2− i mod n). Here is an illustration.89 90 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 4 of 18 2.2. Graph Theory91 A graph G is an ordered pair G = (V (G), E(G)) where V (G) is a nonempty set of92 elements called vertices, and E(G) is a set of unordered pairs of vertices called edges.93 The number |V (G)| is called the order of G and the number |E(G)| is called the size of94 G .95 Connected graphs are the graphs in which every two vertices is adjacent to each other.96 If [u, v] is an edge of G, then u and v are adjacent vertices. If [u, v] and [v, w] are97 distinct edges in G, then [u, v] and [v, w] are adjacent edges. The vertex u and the edge98 [u, v] are said to be incident with each other.99 A graph H is called a subgraph of a graph G, written as H ⊆ G, if V (H) ⊆ V (G)100 and E(H) ⊆ E(G). The degree of a vertex v in a graph G denoted by degG(v) or101 simply by deg(v) is the number of vertices in G that are adjacent to v. A vertex of degree102 0 is referred to as an isolated vertex and a vertex of degree 1 is an end-vertex or a103 leaf. An edge incident with an end-vertex is called a pendant edge.104 The distance d(u, v) between u, v ∈ V (G) is the length of a shortest u − v path in105 the graph G. The eccentricity of a vertex u ∈ V (G) is e(u) = max{d(u, v)|u ∈ V (G)}.106 The diameter of a graph G is diam = max{e(u)|u ∈ V (G)}. The radius of a graph G is107 rad = min{e(u)|u ∈ V (G)}. If e(u) = rad(G), the vertex u is a central vertex. The set108 of all such vertices is the center of G. The girth of a graph G denoted by gir(G) is the109 length of the shortest cycle (if any) in G.110 Definition 5. Given a group G with e as the identity element, define the identity graph111 ΓG = Γ(G,E) to have the vertex-set G and the edge-set E satisfying two conditions:112 (i) For every x, y ∈ G where x ̸= y, x and y are adjacent in ΓG if and only if xy = e ;113 (ii) For each x ∈ G, x and e are adjacent in ΓG .114 Two important structures in identity graph are lines and triangles defines as follows:115 Definition 6. Given a group G, a line in the identity graph ΓG is an edge [x, e] such that116 the degree of a vertex x is one. The number of lines in the identity graph ΓG is denoted117 by line(G).118 Definition 7. A triangle in the identity graph ΓG is a subgraph which is isomorphic to119 the cycle of length three. The number of the triangles in the identity graph is denoted by120 tri(G).121 To give an example, consider the identity graphs of selected cyclic groups below.122 123 To further understand the properties of groups and graphs, here are some propositions.124 Propositions are presented without proof and can be found in [5], [8], [1], [9] and [3].125 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 5 of 18 Proposition 1. For a cyclic groups Cn of order n, if n is odd, then line(Cn) = 0 and126 tri(Cn) = n−1 2 . If n is even, then line(Cn) = 1 and tri(Cn) = n−2 2 .127 Proposition 2. If Cn is a cyclic group of order n, then we have128 |E(ΓCn)| = { 3(n−1) 2 , if n is odd 3(n−2) 2 + 1, if n is even. 129 Proposition 3. (Handshaking Lemma) If G is a graph of size m, then130 ∑ v∈V (G) deg(v) = 2m.131 Proposition 4. A nontrivial connected graph G is Eulerian if and only if every vertex132 of G has even degree.133 At this point, we will formally define the main focus of the study, the graph operation134 middle graph of a graph.135 Definition 8. Let G = (V (G), E(G)) be a simple graph. The middle graph of G denoted136 by M(G) is the graph whose vertex set is V (G) ∪ E(G) where two vertices are adjacent137 if (1) they are either adjacent edges of G or (2) one is a vertex and the other is an edge138 incident to it.139 For example,140 Example 3. Consider the graphs C4 . The middle graph of C4, M(C4), is given by141 .142 The middle graph M(C4) of C4 is a graph with V (M(C4)) = {a, b, c, d, 1, 2, 3, 4} and143 two vertices is adjacent if and only if they are adjacent edges of C4 or one is a vertex and144 the other is an edge incident to it. For instance the vertices 4 and 1 in M(C4) are adjacent145 since they are adjacent edges in C4. Also the vertices 3 and d in M(C4) are adjacent since146 3 is an edge incident to a vertex d in C4.147 3. The Middle Graph of ΓCn148 Below is the structure of the middle graph of the identity graph of the finite cyclic149 groups. For easy reference, we refer to the middle graph of the identity graph as MIG.150 This will be used for the rest of this paper.151 Definition 9. Let Cn be a finite group of order n and ΓCn be the identity graph of Cn. The152 middle graph of ΓCn denoted by M(ΓCn) is the graph whose vertex set is V (ΓCn)∪E(ΓCn)153 where two vertices are adjacent if (1) they are either adjacent edges of ΓCn or (2) one is154 a vertex and the other is an edge incident to it.155 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 6 of 18 In this study, the vertex-set and edge-set notations of M(ΓCn) are fixed. Here are the156 following steps on how to construct the middle graph of the identity graph of finite cyclic157 groups.158 Step 1. Draw the identity graph of finite cyclic group ΓCn for n ≥ 2. Set the vertices159 V (ΓCn) = {e}∪{xi|1 ≤ i ≤ n−1} where e is the identity element of the cyclic group160 Cn. Set the edges E(ΓCn) = {zi|zi = [xi, e]for all1 ≤ i ≤ n− 1}161 ⋃ {yp|yp = [xi, xi+1]andp = i+1 2 } { for all odd 1 ≤ i ≤ n− 2}, if n is odd for all odd 1 ≤ i ≤ n− 3}, if n is even. 162 Step 2. Subdivide the edges of the original graph. The additional new vertices will be ob-163 tained by subdividing the edges and the second condition of the middle graph will164 automatically be satisfied.165 Step 3. Connect the new obtained vertices to each other if they are adjacent edges in the166 original graph.167 Consider the following example,168 Example 4. Let ΓC3 be the identity graph of C3 with vertices V (C3) = {e, x1, x2} and169 E(C3) = {z1, z2, y1} shown in the figure below and its corresponding MIG.170 .171 3.1. The middle graph of ΓCn where n is odd172 For the general structure of the middle graph of ΓCn where n is odd, set first the173 vertices of the identity graph of ΓCn as174 V (ΓCn) = {e} ∪ {xi|1 ≤ i ≤ n− 1} and175 E(ΓCn) = {zi|1 ≤ i ≤ n− 1} ∪ { yp|p = i+ 1 2 for all odd 1 ≤ i ≤ n− 2 } Here is the pictorial representation,176 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 7 of 18 .177 To generalize the vertex set and edge set of M(ΓCn) for n is odd, we now have;178 V (M(ΓCn)) = {e} ⋃ {xi|1 ≤ i ≤ n− 1} ⋃ {zi|1 ≤ i ≤ n− 1}⋃{ yp|p = i+1 2 for all odd 1 ≤ i ≤ n− 2 } and179 E(M(ΓCn)) = {[e, zi]|1 ≤ i ≤ n− 1}⋃ {[zi, zj ]|1 ≤ i ≤ n− 1, 1 ≤ j ≤ n− 1, i ̸= j}⋃ {[xi, zi]|1 ≤ i ≤ n− 1, 1 ≤ j ≤ n− 1}⋃{ [yp, zi]|p = i+1 2 for all odd1 ≤ i ≤ n− 2 }⋃{ [yp, zi+1]|p = i+1 2 for all odd1 ≤ i ≤ n− 2 }⋃{ [yp, xi]|p = i+1 2 for all odd1 ≤ i ≤ n− 2 }⋃{ [yp, xi+1]|p = i+1 2 for all odd1 ≤ i ≤ n− 2 } Here is the pictorial representation,180 .181 The degree of the vertices of M(ΓCn) where n is odd is summarized below:182 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 8 of 18 a. deg(e) = n− 1183 b. deg(xi) = 2, 1 ≤ i ≤ n− 1184 c. deg(yp) = 4, 1 ≤ p ≤ i+1 2 for all odd 1 ≤ i ≤ n− 2185 d. deg(zi) = n+ 1, 1 ≤ i ≤ n− 1.186 For the summation of all of the degrees of the vertices of M(ΓCn) for n is odd, we187 have188 ∑ v∈V (M(ΓCn )) deg(v) = (n− 1) + 2(n− 1) + 4(n−1 2 ) + (n+ 1)(n− 1) = n− 1 + 2n− 2 + 2n− 2 + n2 − 1 = n2 + 5n− 6. 3.2. The Middle Graph of ΓCn, where n is even189 For the general structure of the middle graph of ΓCn where n is even, set first the190 vertices of the identity graph of ΓCn as191 V (ΓCn) = {e} ∪ {xi|1 ≤ i ≤ n− 1} and192 E(ΓCn) = {zi|1 ≤ i ≤ n− 1} ∪ { yp|p = i+1 2 for all odd 1 ≤ i ≤ n− 3 } Here is the pictorial representation,193 .194 To generalize the vertex set of M(ΓCn) where n is odd, we have;195 V (M(ΓCn)) = {e} ⋃ {xi|1 ≤ i ≤ n− 1} ⋃ {zi|1 ≤ i ≤ n− 1}⋃{ yp|p = i+1 2 for all odd 1 ≤ i ≤ n− 3 } and196 E(M(ΓCn)) = {[e, zi]|1 ≤ i ≤ n− 1} J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 9 of 18⋃ {[zi, zj ]|1 ≤ i ≤ n− 1, 1 ≤ j ≤ n− 1, i ̸= j}⋃ {[xi, zi]|1 ≤ i ≤ n− 1, 1 ≤ j ≤ n− 1}⋃{ [yp, zi]|p = i+1 2 for all odd1 ≤ i ≤ n− 3 }⋃{ [yp, zi+1]|p = i+1 2 for all odd1 ≤ i ≤ n− 3 }⋃{ [yp, xi]|p = i+1 2 for all odd1 ≤ i ≤ n− 3 }⋃{ [yp, xi+1]|p = i+1 2 for all odd1 ≤ i ≤ n− 3 } Here is the pictorial representation,197 .198 The degree of the vertices of M(ΓCn) where n is even is summarized below:199 a. deg(e) = n− 1200 b. deg(xi) = 2, 1 ≤ i ≤ n− 2201 c. deg(xn−1) = 1202 d. deg(yp) = 4, 1 ≤ p ≤ n−2 2203 e. deg(zi) = n+ 1, 1 ≤ i ≤ n− 2204 f. deg(zn−1) = n205 To sum up all the degrees of the vertices of M(ΓCn) where n is even we have:206 ∑ v∈V (M(ΓCn )) deg(v) = (n− 1) + 1 + n+ 2(n− 2) + 4(n−2 2 ) + (n+ 1)(n− 2) = 2n+ 2n− 4 + 2n− 4 + n2 − n− 2 = n2 + 5n− 10 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 10 of 18 Theorem 1. Let Cn be a cyclic group of order n and M(ΓCn) be the MIG of Cn for207 n ≥ 2. The order of M(ΓCn) is208 |V (M(ΓCn))| = { 5n−3 2 , if n is odd 5n−4 2 , if n is even. 209 Proof.210 i. For n is odd,211 |V (M(ΓCn)| = |V (ΓCn)|+ |E(ΓCn)| = n+ 3(n− 1) 2 = 2n+ 3n− 3 2 = 5n− 3 2 ii. For n is even,212 |V (M(ΓCn)| = |V (ΓCn)|+ |E(ΓCn)| = n+ [ 3(n− 2) 2 + 1] = (2n+ 3n− 6) + 2 2 = 5n− 4 2 Now, for the size of the middle graph of identity graph of a cyclic group, refer to the213 theorem below.214 Theorem 2. The MIG of a cyclic group Cn of order n has size215 |E(M(ΓCn))| = { n2+5n−6 2 , if n is odd n2+5n−10 2 , if n is even. 216 Proof. To prove this, we need to consider two cases.217 i. First we will consider if n is odd. From the summation of all of the degrees of218 the vertices where n is odd, ∑ v∈V (M(ΓCn )) deg(v) = n2 + 5n − 6. By Theorem219 3, for a graph of size m, ∑ v∈V (M(ΓCn )) deg(v) = 2m. By substitution, we have220 n2 + 5n− 6 = 2m. Thus m = n2+5n−6 2 .221 ii. For n is even, using the summary of the degree of the vertices where n is even,222 ∑ v∈V (M(ΓCn )) deg(v) = n2+5n−10. Also by Theorem 3, the sum of all of its vertices223 is ∑ v∈V (M(ΓCn )) deg(v) = 2m where m is the size of the graph. By substitution, we224 have n2 + 5n− 10 = 2m. Thus m = n2+5n−10 2 .225 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 11 of 18 4. Properties of M(ΓCn) on some parameters226 In this section, we will explore the graphical properties of MIGs to further understand227 its structure.228 4.1. Distance between two vertcices229 Theorem 3. Let M(ΓCn) be the middle graph of ΓCn for n ≥ 4. The distance230 i. d(xi, a) ≤ 3 for all a ∈ V (M(ΓCn)) \ xi where 1 ≤ i ≤ n− 1,231 ii. d(yp, a) ≤ 3 for all a ∈ V (M(ΓCn)) \ yp for all 1 ≤ p ≤ n−1 2 if n is odd and232 1 ≤ p ≤ n−2 2 if n is even,233 iii. d(zi, a) ≤ 2 for a ∈ V (M(ΓCn)) \ zi where 1 ≤ i ≤ n− 1,234 iv. d(e, a) ≤ 2for a ∈ V (M(ΓCn)) \ e.235 Proof. We divided it into four cases:236 i. Let a ∈ V (M(ΓCn)) \ xi. If a = xi+1, then the distance d(xi, xi+1) = 2 since both237 [xi, yi+1] and [xi+1, yi+1] ∈ E(M(ΓCn)) and [xi, xi+1] /∈ E(M(ΓCn)). If a = xj such238 that j ̸= i or i+ 1, then [xj , zj ] ∈ E(M(ΓCn)). Also note that [xi, zi] ∈ E(M(ΓCn))239 and [zi, zj ] ∈ E(M(ΓCn)). Now since neither [xi, zj ] nor [xj , zi] ∈ E(M(ΓCn)),240 then the shortest path from xi to xj is the path xi, zi, zj , xj of length 3. Thus the241 distance d(xi, xj) = 3. Similar argument if a = yp. Hence the distance d(xi, yp) = 3.242 If a = zi, then d(xi, zi) = 1 since [xi, zi]] ∈ E(M(ΓCn)). If a = zj such that i ̸= j,243 then [zi, zj ] ∈ E(M(ΓCn)). Also since [xi, zi] ∈ E(M(ΓCn)), then we have a path244 xi, zi, zj from xi to zj and this is the shortest since [xi, zj ] /∈ E(M(ΓCn)). Thus the245 distance d(xi, zj) = 2. Lastly if a = e, the argument is similar to a = zj . Hence the246 distance d(xi, a) ≤ 3 for all a ∈ V (M(ΓCn)) \ xi.247 ii. The proof for the distance d(yp, a) ≤ 3 is analogous to case i.248 iii. Let a ∈ V (M(ΓCn)) \ zi. If a = zj such that i ̸= j, then d(zi, zj) = 1 since249 [zi, zj ] ∈ E(M(ΓCn)). Similar argument if a = e. If a = xi, then clearly d(xi, zi) =250 1. Now suppose a = xj where i ̸= j, note that [xj , zj ] ∈ E(M(ΓCn)) and also251 [zi, zj ] ∈ E(M(ΓCn)), it follows that zi, zj , xj is a shortest path from zi to xj since252 [zi, xj ] /∈ E(M(ΓCn)). Thus the distance d(zi, xj) = 2. Lastly, if a = yp where253 p = i+1 2 , then clearly d(zi, y i+1 2 ) = 1. For p = j+1 2 where i ̸= j, it follows that254 [y j+1 2 , zj ] ∈ E(M(ΓCn)) and we know that [zi, zj ] ∈ E(M(ΓCn)), thus a shortest255 path from zi to y i+1 2 is zi, zj , y i+1 2 since [y i+1 2 , zi] /∈ E(M(ΓCn)). Hence the distance256 d(zi, yp) ≤ 2. Therefore the distance d(zi, a) ≤ 2 for all a ∈ V (M(ΓCn)) \ zi.257 iv. Let M(ΓCn) be the middle graph of ΓCn and let a ∈ V (M(ΓCn)) \ e. If a = zi,258 then d(e, zi) = 1 since [e, zi] ∈ E(M(ΓCn)). Now if a = xi for 1 ≤ i ≤ n − 1, then259 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 12 of 18 [xi, zi] ∈ E(M(ΓCn)) also since [e, zi] ∈ E(M(ΓCn)) then we have a path e, zi, xi of260 length 2 from e to xi. And also since [e, xi] /∈ E(M(ΓCn)), thus this is the shortest261 path from e to xi. Hence d(e, xi) = 2. Finally if a = yp for p = i+1 2 for all odd262 1 ≤ i ≤ n−2, then [yp, zi] ∈ E(M(ΓCn)). The other arguments are similar for a = xi.263 Thus d(e, yp) = 2. Therefore the distance d(e, a) ≤ 2 for all a ∈ V (M(ΓCn)) \ e.264 4.2. Eccentricity of the vertcices265 Theorem 4. Let M(ΓCn) be the middle graph of ΓCn. The eccentricity of the vertices266 i. e(xi) = { 2, if n=2 or 3 3, if n ≥ 4 267 for all 1 ≤ i ≤ n− 1,268 ii. e(yp) = { 2, if n=3 3, for n ≥ 4 269 for all 1 ≤ p ≤ n−2 2 ,270 iii. e(zi) = { 1, if n=2 or 3 2, if n ≥ 4 271 for all 1 ≤ i ≤ n− 1,272 iv. e(e) = 2273 Proof. Let M(ΓCn) be the middle graph of ΓCn .274 i. For n = 2, it is very obvious since the middle graph M(ΓC2) is isomorphic to a path275 P3 with the vertex set V (M(ΓC2) = {e, x1, z1} and edges276 E(M(ΓC2) = {[e, z1], [z1, x1]}.277 ii. For n = 3, note that ΓC3 is isomorphic to a cycle C3 with the vertex set V (ΓC3) =278 {e, x1, x2} and edge set E(ΓC3) = {z1 = [e, x1], z2 = [e, x2], y1 = [x1x2]}. Now for279 M(ΓC3), the vertex set V (M(ΓC3)) = {e, x1, x2, z1, z2, y1} where the vertices x1, x2280 and e are the corner vertices and the vertices z1, z2 and y1 are the inner vertices.281 Note that [x1, z1] and [z1, z2] ∈ E(ΓC3) but [x1, x2] /∈ E(ΓC3) thus the distance from282 x1 to z2 is 2 same with x2 to x1 and e to y1. Also the distance of each corner283 vertex to each other is 2. Now for the distance of all inner vertices to each other is284 1 since they are adjacent edges in ΓC3 . Thus the maximum distance or eccentricity285 e(x1) = e(x2) = e(e) = e(z1) = e(z2) = e(y1) = 2.286 iii. For n ≥ 4, the proof follows from Theorem 3.287 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 13 of 18 4.3. Radius288 Theorem 5. If M(ΓCn) be the middle graph of ΓCn, then289 rad(M(ΓCn)) = { 1, if n=2 2, for n ≥ 3 and diam(M(ΓCn)) = { 2, if n=2 or 3 3, for n ≥ 4. 290 Proof. Let M(ΓCn) be the middle graph of ΓCn . We divided it into three cases:291 i. For n = 2, sinceM(ΓC2) is isomorphic to a path of length 3, clearly rad(M(ΓC2)) = 1292 and the diameter diam(M(ΓC2)) = 2.293 ii. For n = 3, by Theorem 4, the eccentricity of all the vertices is equal to 2, thus the294 radius and diameter rad(M(ΓC3)) = 2 and diam(M(ΓC3)) = 2 respectively.295 iii. For n ≥ 4, from Theorem 4, e(zi) = 2 for all 1 ≤ i ≤ n− 1 and e(e) = 2 and this is296 the minimum eccentricity, thus the radius rad(M(ΓCn)) = 2 . Also using the same297 reference, the vertices with the maximum eccentricities are the vertices xi and yi298 with e(xi) = 3 for all 1 ≤ i ≤ n− 1 and e(yp) = 3 for all 1 ≤ p ≤ n−1 2 if n is odd and299 1 ≤ p ≤ n−2 2 if n is even. Hence the diameter diam(M(ΓCn)) = 3.300 4.4. Central Vertices301 Theorem 6. For the middle graph M(ΓCn) for n ≥ 4, the central vertices are the vertices302 zi ∈ V (M(ΓCn)) and e.303 Proof. From Theorem 4, the eccentricity e(zi) = 2 for all i, 1 ≤ i ≤ n−1 and e(e) = 2.304 Now by Theorem 5, the radius rad(M(ΓCn)) = e(zi) = e(e) = 2 for all 1 ≤ i ≤ n− 1. The305 ramaining vertices xi′s and yp′s has the eccentricity of 3. Thus the central vertices are all306 the zi ∈ V (M(ΓCn)) and e.307 4.5. Center308 Theorem 7. The set of vertices Cen(M(ΓCn)) = {{zi|1 ≤ i ≤ n− 1} ⋃ {e}} is the center309 of M(ΓCn) for n ≥ 4.310 Proof. The proof of this theorem follows from Theorem 6.311 4.6. Complete Subgraph312 Theorem 8. Let H be a subgraph induced by Cen(M(ΓCn)) for n ≥ 4, then H is a313 complete subgraph of order n .314 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 14 of 18 Proof.315 LetM(ΓCn) be the middle graph of ΓCn for n ≥ 4. SupposeH is a subgraph induced by316 Cen(M(ΓCn)), then V (H) = {{zi|1 ≤ i ≤ n−1} ⋃ {e}} = Z∪{e} and clearly |V (H)| = n.317 Note that for every vertex zi and zj element of Z where i ̸= j, [zi, zj ] ∈ E(M(ΓCn))318 and also [zi, e] ∈ E(M(ΓCn)) thus degH(zi) = degH(e) = n − 1. Consequently, the size319 |E(H)| = |E(Kn)| = n(n−1) 2 . Hence H is a complete graph of order n.320 4.7. Circumference321 Theorem 9. If M(ΓCn) be the middle graph of ΓCn, then the circumference322 c(M(ΓCn)) = { 5n−3 2 , if n is odd, 5n−6 2 , if n is even. 323 Proof. Let M(ΓCn) be the middle graph of ΓCn . We divided it into two cases.324 i. For n is odd, we will find a cycle C ⊆ M(ΓCn) with the largest size. From the325 structure of M(ΓCn) where n is odd, since [e, zi] ∈ E(M(ΓCn)) for 1 ≤ i ≤ n − 1,326 take e as our initial vertex, followed by z1. Note that [zi, xi] ∈ E(M(ΓCn)), then327 we have a path e, z1, x1. Now also [xi, y i+1 2 ] and [xi+1, y i+1 2 ] ∈ E(M(ΓCn)), then328 we can extend our path to e, z1, x1, y1, x2, z2,. Also since [zi, zi] ∈ E(M(ΓCn)), we329 can have e, z1, x1, y1, x2, z2, z3 then repeat the process. By continuing, we now have330 e, z1, x1, y1, x2, z2, z3, x3, y2, x4,331 z4, ...zi, xi, y i+1 2 , xi+1, zi+1, ...zn−2, xn−2, yn−1 2 , xn−1,332 zn−1. Now we can connect zn−1 to e since [e, zi] ∈ E(M(ΓCn)) for 1 ≤ i ≤ n − 1.333 Clearly, C : e, z1, x1, y1, x2, z2, z3, x3, y2, x4, z4, ...zi, xi, y i+1 2 , xi+1, zi+1, ...zn−2,334 xn−2, yn−1 2 , xn−1, zn−1, e is a cycle since no vertex is repeated except for the first and335 the last. To compute the length, we have to compute its order since the length of336 a cycle is equal to its order. So |e| = 1, |zi′s| = n − 1, |xi′s| = n − 1, |yi′s| = n−2 2 .337 Thus |V (C)| = 1 + (n − 1) + (n − 1) + (n−1 2 ) = 5n−3 2 . Note that C ⊆ M(ΓCn),338 thus |V (C)| ≤ |V (M(ΓCn))|. And from Theorem 1 the order |V (M(ΓCn))| = 5n−3 2339 if n is odd . It implies that |V (C)| = |V (M(ΓCn))| = 5n−3 2 , hence the length of the340 maximum cycle in M(ΓCn) = 5n−3 2 .341 2. For n is even, we will find a cycle C ⊆ M(ΓCn) of maximum length. From the342 structure ofM(ΓCn) where n is even, since [e, zi] ∈ E(M(ΓCn)) for 1 ≤ i ≤ n−1, then343 choose e as our initial vertex followed by zn−1, then z1 since [zi, zj ] ∈ E(M(ΓCn)) so344 that we have a path e, zn−1, z1. also since [zi, xi] ∈ E(M(ΓCn)), then we can extend345 it to e, zn−1, z1, x1,. Similar to Case 1, [xi, y i+1 2 ] and [xi+1, y i+1 2 ] ∈ E(M(ΓCn)) for346 all odd 1 ≤ i ≤ n − 3, thus we have e, zn−1, z1, x1, y − 1, x2. Now choose z2 as our347 next vertex so that we have e, zn−1, z1, x1, y−1, x2, z2. By continuing the process,we348 now have a cycle349 C : e, zn−1, z1, x1, y − 1, x2, z2, z3, x3, y2, x4, z4, ...zi, xi, y i+1 2 , xi+1, zi+1, ...zn−3, xn−3,350 yn−2 2 , xn−2, zn−2, e. To compute the order of C, we have351 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 15 of 18 V (C) = {e} ⋃ {zi|1 ≤ i ≤ n − 1} ⋃ {xi|1 ≤ i ≤ n − 2} ⋃ {yp|1 ≤ p ≤ n−2 2 }. Implies352 that353 |V (C)| = 1 + (n− 1) + (n− 2) + ( n− 2 2 ) = 2n− 2 + n− 2 2 = 4n− 4 + n− 2 2 = 5n− 6 2 . By Theorem 13, there exist exactly one vertex v ∈ V (M(ΓCn)) of degree 1. Thus354 clearly v /∈ V (C). It follows that355 |V (C)| ≤ |V (M(ΓCn))| − 1 ≤ 5n− 4 2 − 1 ≤ 5n− 4− 2 2 ≤ 5n− 6 2 . Thus |V (Ck)| = |V (M(ΓCn))| − 1 = 5n−6 2 . Hence 5n−6 2 is the maximum length of a356 cycle contained in (M(ΓCn). Therefore the circumference c(M(ΓCn)) = 5n−6 2 , if n is357 even.358 4.8. Girth359 Theorem 10. If M(ΓCn) be a middle graph of a ΓCn, then the gir(M(ΓCn)) = 3 for360 n ≥ 3.361 Proof. Let e be the vertex representing the identity element in ΓCn . Now for ΓCn , there362 are n− 1 edges incident to e. Pick any edges namely z1, z2. By the Definition 8 of MIG,363 z1 and z2 are vertices in M(ΓCn). Also by the condition (1), [z1, z2] is an edge in M(ΓCn).364 Now by the condition (2), [z1, e] and [z2, e] are edges in M(ΓCn). Thus z1, z2, e, z1 is a365 cycle of length 3 in M(ΓCn). Therefore the girth gir(M(ΓCn)) = 3 for n ≥ 3.366 4.9. Clique Number367 Theorem 11. If M(ΓCn) be a middle graph of a ΓCn, then the clique number ω[M(ΓCn)] =368 n for n ≥ 3.369 Proof. Let M(ΓCn) be the middle graph of ΓCn . We will show that the clique num-370 ber ω[M(ΓCn)] = n. Note that from Theorem 8, the subgraph induced by the center371 Cen(M(ΓCn)) = {zi|1 ≤ i ≤ n − 1} ⋃ {e} is a complete graph of order n. Suppose there372 is another complete subgraph Km of order m where m ≥ n. But from the summary of373 the degree of the vertices, the degree deg(xi) = 2 for 1 ≤ i ≤ n − 1 and deg(yp) = 4 for374 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 16 of 18 1 ≤ p ≤ n−1 2 if n is odd and 1 ≤ p ≤ n−2 2 if n is even. Thus clearly xi′s and yp′s are not375 elements of V (Km). Now we are left with the vertices zi for 1 ≤ i ≤ n − 1 and e since376 V (M(ΓCn)) \ {xi ∪ yp} = {zi} ∪ {e} for all 1 ≤ i ≤ n − 1 and 1 ≤ p ≤ n−1 2 if n is odd377 and 1 ≤ p ≤ n−2 2 if n is even which is clearly the center Cen(M(ΓCn)). Hence it is not378 possible to have a complete subgraph Km of order m where m ≥ n. Therefore the clique379 number ω[M(ΓCn)] = n.380 4.10. Independence Number381 Theorem 12. The indepedendence number α(M(ΓCn)) = n.382 Proof. To start with, we know that from Theorem 11, the largest complete graph K383 contained in (M(ΓCn) has order n so that the clique number ω(M(ΓCn)) = n. Note that384 the vertices V (K) = {zi|1 ≤ i ≤ n − 1} ⋃ {e}. Let S be an independent set that has a385 maximum number of elements. It follows that exactly one vertex V (K) must be in S.386 Thus it is either e only or one of the zi′s only. For n is odd, we have two cases.387 1. Let zj be a fixed element in S, then it follows that xj and yq are not in S for any fixed388 xj and yq such that yq = [xj , xj + 1] ∈ V (ΓCn) but xj+1 ∈ S since zj is not adjacent389 to xj+1. Now we are left with the set of vertices X = {xi|1 ≤ i ≤ n− 1} \ {xj , xj+1}390 for all odd 1 ≤ j ≤ n−2 and the set Y = yp|1 ≤ p ≤ n−1 2 \yq. But note that for every391 yp, there are exactly 2 xi′s adjacent to it. Thus for every yp ∈ S there are exactly 2392 xi /∈ S so that S = {zj , xi+1}∪Y . Hence |S| = |{zj , xi+1}|∪|Y | = 2+ n−1 2 −1 = n+1 2 .393 Now if we choose xi ∈ S, it follows that yp is not in S for yp = [xi, xi+1. But since394 xi is not adjacent to xi+1, then xi+1 must be in S so that S = {zj , xj+1} ∪X. Thus395 |S| = |{zj , xj+1}| ∪ |X| = 2 + n− 3 = n− 1.396 2. Suppose e ∈ S then clearly each of the zi for all 1 ≤ i ≤ n − 1 is not in S.397 Now we are left with the set of vertices X = {xi|1 ≤ i ≤ n − 1} and the set398 Y = yp|1 ≤ p ≤ n−1 2 . Similar to Case 1, for every yp, there are exactly 2 xi′s399 adjacent to it. Thus for every yp ∈ S there are exactly 2 xi /∈ S so that S = {e}∪Y .400 Hence |S| = |{e}| ∪ |Y | = 1 + n−1 2 = n+1 2 . Now if we choose xi ∈ S, it follows that401 yp is not in S for yp = [xi, xi+1. But since xi is not adjacent to xi+1, then xi+1 must402 be in S so that S = {e} ∪X. Thus |S| = |{e}| ∪ |X| = 1+ n− 1 = n. Therefore the403 cardinality of the maximum independent set in (M(ΓCn) is n for n is odd.404 The proof for n is even is analogous for n is odd.405 4.11. Other Properties406 Theorem 13. If n is even, then the middle graph M(ΓCn) contains exactly one vertex of407 degree 1.408 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 17 of 18 Proof. By Theorem 1, the line in the identity graph ΓCn is 1 if n is even. Now let x409 be the vertex of degree 1 in ΓCn where n is even and let a be the edge connecting x to410 another vertex say y. Now by the definition of the middle graph, a will become a vertex411 in M(ΓCn). Also by condition (2) from the definition of MIG in Definition 8, [x, a] is an412 edge. Suppose there exists another vertex w such that [x,w] is an edge in M(ΓCn). By413 (2) in the definition of the MIG, it follows that w is an edge in ΓCn that is incident to x414 which contradicts the fact that x has degree 1 in ΓCn . Thus M(ΓCn) contains a vertex of415 degree 1. Suppose there exists another vertex u where u ̸= x in M(ΓCn) of degree 1, then416 u cannot be in E(ΓCn) since there are two edges namely q and r incident to u and by (2)417 of Definition 8, u will become a vertex adjacent to q and r. Thus it must be u ∈ V (ΓCn).418 Note that ΓCn contains only one line, it follows that u lies in some triangles of ΓCn which419 implies that atleast two edges say s and t are incident to u that will eventually become420 vertices in M(ΓCn). By the (2) of Definition 8, s and t will be vertices adjacent to u which421 contradicts that u has of degree 1. Hence there is only one vertex in M(ΓCn) of degree 1.422 Theorem 14. Every vertex of M(ΓCn) has an even degree if n is odd.423 Proof. The summary of the degree of the vertices ofM(ΓCn) whwre n is odd is sufficient424 enough to prove this theorem.425 Theorem 15. The middle graph M(ΓCn) is Eulerian if n is odd.426 Proof.427 Let M(ΓCn) be the middle graph of ΓCn . Suppose n is odd, by Theorem 14, every428 vertex of M(ΓCn) is of even degree. Thus by Theorem 4, M(ΓCn) is Eulerian.429 Theorem 16. If n is odd, then the middle graph M(ΓCn) is Hamiltonian.430 Proof. From Theorem 9, if n is odd, the order of the largest cycle |V (C)| contained in431 M(ΓCn) is 5n−3 2 = |M(ΓCn)|. Thus C is Hamiltonian cycle. Consequently, M(ΓCn) where432 n is odd is a Hamiltonian graph.433 5. Conclusion and Recommendations434 This paper focuses on the middle graph of the identity graph of finite cyclic and435 dihedral groups denoted by M(ΓCn) and M(ΓDn) respectively. These graphs are simple,436 finite, connected and undirected graphs. The concept of the identity graph and middle437 graph is introduced in this paper.438 Using these concepts, the middle graphs M(ΓCn) and M(ΓDn) were constructed and439 the labeling for the vertices and edges were discussed. In addition, some parameters such440 as the size and order were easily shown using the construction and other existing theorems441 and propositions. It is also found that the middle graph M(ΓCn) is both Eulerian and442 Hamiltonian if n is odd. Other properties on some parameters is summarized in Table ??.443 Here is the table for the properties of M(ΓCn) and M(ΓDn) on some parameters of a444 graph.445 J. M. Jamis, D. M. Magpantay / Eur. J. Pure Appl. Math, 18 (2) (2025), 5499 18 of 18 Parameters Values gir(M(ΓCn)) 3 ω[M(ΓCn)] n α(M(ΓCn)) n γ(M(ΓCn)) n+1 2 if n is odd and n 2 if n is even χ(M(ΓCn)) n χ′(M(ΓCn)) n+ 2 if n is odd and n+ 1 if n is even gir(M(ΓDn)) 3 ω[M(ΓDn)] 2n α(M(ΓDn)) 2n γ(M(ΓDn)) 3n−1 2 if n is odd and 3n 2 if n is even. χ(M(ΓDn)) 2n χ′(M(ΓDn)) 2n+ 1 446 The problem on the identity graphs is still open. For instance, the middle graph of447 the identity graph of symmetric groups is also interesting to investigate.448 References449 [1] W. B. V. Kandasamy and F. Smarandache. Groups as Graphs. Editura CuArt,450 Slobozia, 2009.451 [2] A. D. Godase. Unit graph of some finite group. International Journal of Universal452 Science and Technology, 1(1):12–18, 2015.453 [3] N. F. Yalcin and Y. Kirgil. Identity graph of finite cyclic groups. Journal of Balikesir454 University Institute of Science and Technology, 21(2):614–624, 2019.455 [4] J. U. Jeeshma. Coloring for the identity graphs of groups. International Research456 Journal of Engineering and Technology, 7(7):3459–3462, 2020.457 [5] J. Akiyama, T. Hamada, and I. Yoshimora. On characterization of the middle graphs.458 https://www.researchgate.net/publication/269002499, 1975.459 [6] N. Murugesan and D. S. Nair. Power domination of middle graph of central graph460 of path, cycle, and star. International Journal of Pure and Applied Mathematics,461 115(6):121–126, 2017.462 [7] C. Alib and D. Magpantay. On some parameters of the central graphs of the identity463 graphs of finite cyclic groups. European Journal of Pure and Applied Mathematics,464 15(4):1888–1904, 2022.465 [8] G. Chartrand and P. Zhang. A First Course in Graph Theory. Dover Publications,466 Mineola, NY, 2012.467 [9] W. Somnuek. Counting lines and triangle in a unit graph. Current Applied Science468 and Technology, 18(2):148–155, 2018.469