The Metrics Dimension of the Cyclic Subgroup Graph of Finite 2-Group of Maximal Class

The Metric Dimension of the Cyclic Subgroup Graph of Finite 2-Groups of Maximal Class Sabyasachi Kundu Department of Mathematics and Statistics Indian Institute of Science Education and Research, Kolkata [email protected] December 5, 2025 Abstract The cyclic subgroup graph Γ(G) is a simple graph associated with a group G, where the vertex set consists of the cyclic subgroups of G, and two distinct vertices are adjacent if one is a maximal subgroup of the other. This graph encodes significant structural information regarding the lattice of subgroups. This paper extends the classification of graph invariants for finite groups by investigating the metric dimension of Γ(G) for infinite families of 2-groups of maximal class. Specifically, the exact metric dimension is determined for the Dihedral groups D2n, the Semi-Dihedral groups SD2n, and the Generalized Quaternion groups Q2nfor n≥3. It is proven that dim(Γ(D2n)) = 2n−1, dim(Γ(SD2n)) = 3 ·2n−3−1, and dim(Γ(Q2n)) = 2n−2+ 1. These results demonstrate that the metric dimension is a sensitive invariant capable of distinguishing between groups of the same order and nilpotency class, reflecting subtle differences in the distribution of involutions within the subgroup lattice. A rigorous graph-theoretic analysis of the “caterpillar” versus “star-like” topologies exhibited by these algebraic structures is provided. Keywords: Metric dimension, Cyclic subgroup graph, Finite 2-groups, Resolving set, Dihedral group, Generalized Quaternion group. Mathematics Subject Classification (2020): 05C12, 05C25, 20D15. 1 1 Introduction The exploration of combinatorial properties within algebraic structures has established itself as a cornerstone of modern algebra. The methodology of associating a graph with a group allows researchers to translate complex algebraic properties into graph-theoretic language, thereby facilitating the application of powerful combinatorial tools to solve algebraic problems. This interdisciplinary approach has led to the definition and analysis of numerous graph classes, including the well-known Cayley graphs, commuting graphs, power graphs, and subgroup lattice graphs. Each of these constructions highlights a different aspect of the group structure, ranging from element interaction to subgroup containment. The specific focus of this research is the cyclic subgroup graph, denoted by Γ(G), which was formally introduced and investigated by T˘arn˘auceanu [12, 13]. This graph is derived from the poset of cyclic subgroups, a fundamental structure in the theory of finite groups. Unlike the full subgroup lattice, which can be exponentially large and structurally chaotic, the poset of cyclic subgroups often provides a more tractable yet sufficiently rich landscape for analyzing the group’s internal architecture. The edges of Γ(G) correspond to the covering relations within this poset; that is, two cyclic subgroups are connected if and only if one is a maximal subgroup of the other. While structural properties of Γ(G) such as the number of edges, degree sequences, and diameter have been the subject of prior investigations, the metric dimension of these graphs remains an open area of research, particularly for non-abelian p-groups. The concept of metric dimension was introduced independently by Slater [11] and by Harary and Melter [6] in the context of resolving sets. A set of vertices Win a graph is said to resolve the graph if every vertex in the graph is uniquely identified by its vector of distances to the vertices in W. The metric dimension is defined as the cardinality of the smallest such resolving set. The determination of the metric dimension is a problem of significant importance not only in graph theory but also in practical applications such as network discovery, robot navigation, and chemical structure analysis. In the context of algebraic graphs, the metric dimension serves as a numerical invariant that quantifies the structural complexity and symmetry of the group. A lower metric dimension typically indicates a structure that is easily navigable or “linear,” while a higher dimension suggests a high degree of symmetry or indistinguishability among vertices. 1.1 Literature Review The study of cyclic subgroups dates back to the early 20th century. In 1929, Miller [9] initiated the investigation into the arithmetic properties of the number of cyclic subgroups, establishing fundamental counting principles. This line of inquiry lay dormant for decades until Richards [10] provided refined bounds on the number of cyclic subgroups for finite groups. In recent years, the classification of groups based on the quantitative properties of their cyclic subgroups has seen a resurgence. T´oth [14] derived exact formulas for the number of cyclic subgroups in finite abelian groups, utilizing the properties of the Euler totient function. Building on this, Garonzi and Patassini [4] and Garonzi and Lima [5] explored inequalities detecting structural properties of finite groups based on cyclic subgroup counts. A significant body of work has focused on the “inverse problem”: identifying a group 2 based on the number of its cyclic subgroups. Belshoff et al. [2], Jafari and Madadi [7], Kalra [8], and Zhou [15] have systematically classified finite groups possessing a specific number of cyclic subgroups (e.g., |G| − rfor small r). These classification results are crucial as they highlight the constraints imposed by the subgroup lattice on the group structure. Parallel to these counting problems, the graph-theoretic perspective has advanced through the work of T˘arn˘auceanu [12,13], who established the definitions and basic properties of the cyclic subgroup graph. Additionally, Ashrafi and Haghi [1] contributed to the understanding of n-cyclic groups, further bridging the gap between the arithmetic and graph-theoretic viewpoints. Despite this extensive literature, the metric dimension of Γ(G) for specific infinite families of non-abelian groups has not been adequately addressed. This paper aims to fill this gap by focusing on finite 2-groups of maximal class. 1.2 Motivation and Main Contribution The class of finite p-groups is vast and notoriously difficult to classify. However, the 2groups of maximal class—namely the Dihedral, Semi-Dihedral, and Generalized Quaternion groups—are well-understood and completely classified. These groups share identical orders (2n) and nilpotency classes (n−1), making them ideal candidates for comparative structural analysis. Their subtle differences lie in the distribution of involutions (elements of order 2) and the structure of their subgroup lattices. This study performs a complete classification of the metric dimension of the cyclic subgroup graph for these three infinite families. The main contributions are as follows: 1. An exact formula is derived for the metric dimension of the Dihedral group D2n, demonstrating a linear growth with respect to the group order. 2. The metric dimension for the Semi-Dihedral group SD2nis determined, revealing a structural dependence on the distribution of non-cyclic subgroups along the central spine. 3. The case for the Generalized Quaternion group Q2nis solved, identifying a “symmetry breaking” phenomenon caused by the presence of a unique involution, which forces a higher metric dimension compared to the Semi-Dihedral case. 4. A comparative analysis is provided, establishing the metric dimension as a structural discriminator that distinguishes the “caterpillar” topology of SD2nfrom the “star” topology of Q2n. The remainder of this paper is organized as follows. Section 2 provides the necessary preliminaries on group definitions and graph theory concepts. Sections 3, 4, and 5 present the main theorems for the Dihedral, Semi-Dihedral, and Generalized Quaternion groups, respectively. Section 6 provides explicit examples for small orders to illustrate the theoretical findings. Section 7 presents an asymptotic analysis of the results. Section 8 provides computational data verifying the results for small orders. Finally, Section 9 offers concluding remarks. 3 2 Preliminaries This section formally defines the groups under investigation and the graph-theoretic tools required for the proofs. 2.1 Finite 2-Groups of Maximal Class A finite p-group of order pnhas maximal class if its nilpotency class is n−1. For p= 2, the groups of maximal class are completely classified. For n≥3, they consist of the Dihedral, Semi-Dihedral, and Generalized Quaternion groups. Definition 2.1 (Dihedral Group).The Dihedral group D2nof order 2n(n≥3) has the presentation: D2n=⟨r, s |r2n−1= 1, s2= 1, srs =r−1⟩.(1) Definition 2.2 (Semi-Dihedral Group).The Semi-Dihedral group SD2nof order 2n(n≥ 3) has the presentation: SD2n=⟨r, s |r2n−1= 1, s2= 1, srs =r2n−2−1⟩.(2) Definition 2.3 (Generalized Quaternion Group).The Generalized Quaternion group Q2n of order 2n(n≥3) has the presentation: Q2n=⟨x, y |x2n−1= 1, y2=x2n−2, y−1xy =x−1⟩.(3) Lemma 2.4. Let n≥3and D2n=⟨r, s |r2n−1= 1, s2= 1, srs =r−1⟩. 1. The rotation subgroup ⟨r⟩is cyclic of order 2n−1and contains exactly one subgroup of order 2kfor each 0≤k≤n−1. Denote these by C0={e} ⊂ C1⊂ · · · ⊂ Cn−1=⟨r⟩, where |Ck|= 2k. 2. The set of reflections s⟨r⟩={srk: 0 ≤k < 2n−1}has size 2n−1; each element srk has order 2and generates a distinct cyclic subgroup of order 2which is not contained in any cyclic subgroup of order >2. Proof. (1) is standard for a cyclic group. For (2), s⟨r⟩is the nontrivial coset of index 2, hence has size 2n−1. Each srkhas order 2 since (srk)2=srksrk=s(rks)rk=ssr±krk=e. If ⟨sri⟩=⟨srj⟩then sri= (srj)±1, so i≡ ±j(mod 2n−1), which forces i=j. Finally, a reflection is not a square of an element of ⟨r⟩, so no reflection lies in any cyclic subgroup of order >2. Lemma 2.5. Let n≥3and use the standard presentation of SD2nwith rotation rand reflection-like element s. Then elements outside ⟨r⟩split by parity: (sr2k)2= 1,(sr2k+1)2=r2n−2, so there are 2n−2involutions of the form sr2kand 2n−2elements of order 4of the form sr2k+1. Consequently the number of distinct order-2cyclic subgroups outside the spine is 2n−2and the number of distinct order-4cyclic subgroups outside the spine is 2n−3. Proof. Compute (srm)2=srmsrm=s(rms)rm. Using the semi-dihedral relation srs = r2n−2−1, a straightforward parity check shows the asserted identities. Counting elements in the coset s⟨r⟩gives 2n−1elements outside the spine; splitting by parity yields the two claimed counts. Dividing the order-4 element count by ϕ(4) = 2 gives the number of distinct order-4 cyclic subgroups. 4 Lemma 2.6. Let n≥3and Q2n=⟨x, y |x2n−1= 1, y2=x2n−2, y−1xy =x−1⟩. Then ⟨x⟩is the unique maximal cyclic subgroup (the spine) and there is a unique involution z:= x2n−2. Every element outside ⟨x⟩has order 4, and the number of distinct order-4 cyclic subgroups outside the spine equals 2n−2. Proof. Elements outside ⟨x⟩are of the form yxk, and (yxk)2=yxkyxk=y(xky)xk= yyx±kxk=x2n−2=z. Hence these elements have order 4. There are 2n−1such elements and each order-4 cyclic subgroup has exactly two generators, giving 2n−2distinct order-4 subgroups. 2.2 The Cyclic Subgroup Graph Let Gbe a finite group. The set of cyclic subgroups of Gis denoted by C(G). Definition 2.7. The cyclic subgroup graph Γ(G) is a simple undirected graph with vertex set V(Γ(G)) = C(G). Two distinct vertices H, K ∈ C(G) are adjacent if and only if either His a maximal subgroup of Kor Kis a maximal subgroup of H. This definition implies that the edges of Γ(G) correspond to the covering relations in the poset (C(G),⊆). For p-groups, maximal subgroups have prime index, so His adjacent to Kif |K:H|=p(assuming H⊂K). 2.3 Metric Dimension and Twin Sets Standard definitions from graph theory are recalled here. Let Γ = (V, E) be a connected simple graph. The distance d(u, v) between two vertices u, v ∈Vis the length of a shortest path connecting them. Definition 2.8. A set of vertices W={w1, w2, . . . , wk} ⊆ Vis called a resolving set for Γ if for every pair of distinct vertices u, v ∈V, there exists at least one wi∈Wsuch that d(u, wi)=d(v, wi). The metric dimension of Γ, denoted by dim(Γ), is the minimum cardinality of a resolving set. A powerful tool for determining the metric dimension is the concept of twins. Definition 2.9. Two vertices u, v ∈Vare called twins if they share the same open neighborhood, i.e., N(u)\ {v}=N(v)\ {u}. Lemma 2.10 (Twin Lemma).Let u, v be twins in a graph Γ. Then, for any vertex w∈V\ {u, v},d(u, w) = d(v, w). Consequently, if Tis a set of vertices such that every pair in Tare twins (a twin set), then any resolving set must contain at least |T| − 1 vertices from T. Proof. Since uand vare twins, N(u)\ {v}=N(v)\ {u}. Let w∈V\ {u, v}. Let P= (w, x1, . . . , xk, u) be a shortest path from wto uof length d(w, u). If xk=v, then xk∈N(u)\ {v}=N(v)\ {u}, so xk∈N(v). Thus, (w, . . . , xk, v) is a path of the same length to v. If xk=v, then the path is (w, . . . , v, u), implying d(w, v) = d(w, u)−1. But since uand vare adjacent (if connected) or share neighbors, the symmetry of twins implies d(u, w) = d(v, w). Formally, any path to uavoiding vcan be redirected to vat the penultimate step, and vice-versa. 5 Therefore, the vector of distances from any w /∈ {u, v}to uis identical to the vector to v. To resolve the pair u, v, the resolving set Wmust contain at least one of them, otherwise d(w, u) = d(w, v) for all w∈W, implying uand vare indistinguishable. Generalizing to a set Tof size k, if we select only k−2 elements, there remain two unselected twins u, v which cannot be distinguished by any node outside Tnor by the selected nodes in T (distances would be equal). Thus |W∩T| ≥ |T| − 1. 3 The Dihedral Group D2n This section analyzes the metric dimension of the cyclic subgroup graph of the Dihedral group. This group serves as a baseline for understanding 2-groups with a large number of involutions. The group D2ncontains a unique maximal cyclic subgroup ⟨r⟩of order 2n−1. The elements outside this subgroup are reflections of the form srk, where 0 ≤k < 2n−1. It is a well-known property that every reflection in D2nhas order 2. Theorem 3.1. Let n≥3. The metric dimension of the cyclic subgroup graph of the Dihedral group D2nis given by: dim(Γ(D2n)) = 2n−1.(4) Proof. Let G=D2n. The cyclic subgroups of Gcan be partitioned into two sets. The spine, as described in Lemma 2.4, consists of the subgroups of the maximal cyclic group ⟨r⟩:C0⊂C1⊂ · · · ⊂ Cn−1. By Lemma 2.4, the set Rof reflection-generated order-2 subgroups has size |R| = 2n−1. Since each H∈ R is a maximal subgroup only of itself and contains only the identity, N(H) = {C0}for all H∈ R. Thus, Ris a twin set. By Lemma 2.10, any resolving set Wmust satisfy |W∩ R| ≥ |R| − 1. Consider the case where we select exactly |R| − 1 vertices from R. Let u∈ R \ Wbe the unselected reflection. We must determine if uis resolved from the spine nodes. Note that N(C1) = {C0, C2}. For any sensor s∈W∩ R (a sibling reflection), the distance is d(s, u) = d(s, C0) + d(C0, u) = 1 + 1 = 2. Similarly, d(s, C1) = d(s, C0) + d(C0, C1) = 1 + 1 = 2. Thus, sensors in Rcannot distinguish ufrom C1. The only nodes that can distinguish ufrom C1are the spine nodes Ckfor k≥2, where d(Ck, u) = k+1 and d(Ck, C1) = k−1. Consequently, to resolve uand C1,Wmust either contain uitself, or contain a spine node Ck(k≥2). If we include a spine node, the size of Wbecomes (|R| − 1) + 1 = |R|. If we simply include uin W(selecting all of R), the size is |R|. The set W=Ris a resolving set because every leaf is distance 0 from itself, and for any spine node Ck,d(u, Ck) = k+ 1, which uniquely identifies k. Thus, dim(Γ(D2n)) = |R| = 2n−1. Remark 3.2.The graph structure of Γ(D2n) resembles a “fan” or “star” centered at the identity, with one long arm (the spine) and 2n−1short arms (the reflections). This high degree of symmetry at the identity vertex is responsible for the linear growth of the metric dimension with respect to the group order. 4 The Semi-Dihedral Group SD2n The Semi-Dihedral group represents a structural variation where the involutions are not as uniform as in the Dihedral case. 6 Theorem 4.1. Let n≥3. The metric dimension of the cyclic subgroup graph of the Semi-Dihedral group SD2nis given by: dim(Γ(SD2n)) = 3 ·2n−3−1.(5) Proof. Let G=SD2n. Similar to the Dihedral case, there is a unique maximal cyclic subgroup spine C0⊂ · · · ⊂ Cn−1. By Lemma 2.5, the non-spine subgroups partition into two sets: •L2: cyclic subgroups of order 2 generated by sr2k.|L2|= 2n−2. These are adjacent only to C0. •L4: cyclic subgroups of order 4 generated by sr2k+1.|L4|= 2n−3. These contain C1 (the unique spine involution), so they are adjacent to C1. Both L2and L4form disjoint twin sets. By Lemma 2.10, we require at least |L2| − 1 sensors from L2and |L4| − 1 sensors from L4. Let ube an unselected vertex from L2and vbe an unselected vertex from L4. We verify if these unselected vertices create ambiguity with the spine. 1. Ambiguity of u(vs C1): Sensors in L4can distinguish ufrom C1. Let w∈ L4. d(w, C1) = 1. d(w, u) = d(w, C1) + d(C1, C0) + d(C0, u) = 1 + 1 + 1 = 3. Thus, uis resolved provided we have sensors in L4. 2. Ambiguity of v(vs C2): We check if vcan be distinguished from the spine node C2(order 4). C2is adjacent to C1and C3.vis adjacent to C1. •Distance from a sensor s4∈ L4\{v}:d(s4, v) = 2 (path s4−C1−v). d(s4, C2) = 2 (path s4−C1−C2). Indistinguishable. •Distance from a sensor s2∈ L2:d(s2, v) = d(s2, C0) + d(C0, C1) + d(C1, v) = 1 + 1 + 1 = 3. d(s2, C2) = d(s2, C0) + d(C0, C1) + d(C1, C2) = 1 + 1 + 1 = 3. Indistinguishable. Since neither set of sensors can distinguish the unselected leaf v∈ L4from the spine node C2, we must increase the resolving set size by 1 (either including vor C2or a higher spine node). Thus, the dimension is (|L2|−1)+(|L4|−1)+1 = |L2|+|L4|−1. Substituting the counts: 2n−2+ 2n−3−1=2·2n−3+ 2n−3−1 = 3 ·2n−3−1. 5 The Generalized Quaternion Group Q2n The Generalized Quaternion group presents the most restricted structure due to its unique involution. Theorem 5.1. Let n≥3. The metric dimension of the cyclic subgroup graph of Q2nis: dim(Γ(Q2n)) = 2n−2+ 1.(6) Proof. By Lemma 2.6, let Ldenote the set of 2n−2cyclic subgroups of order 4 contained in Q2n\ ⟨x⟩. Each L∈ L contains the unique involution C1=⟨x2n−2⟩. Thus N(L) = {C1}. Crucially, consider the identity subgroup C0. Since C0⊂C1and C0is not maximal in any other cyclic subgroup (as all other minimal subgroups are C1itself in this lattice 7 structure, or rather, C0is only covered by the unique minimal subgroup C1), we have N(C0) = {C1}. Therefore, the set T=L∪{C0}forms a single twin set of size |L| + 1 = 2n−2+1. By Lemma 2.10, we must select |T|−1 vertices. Let u∈T\Wbe the unselected vertex. We must check if uis distinguishable from the next spine node C2(order 4). Note N(C2) = {C1, C3}. For any sensor s∈W⊂T:d(s, u) = 2 (path s−C1−u). d(s, C2) = 2 (path s−C1−C2). The distances are identical. Thus, the unselected twin uis indistinguishable from C2 using only sensors in T. To resolve this, we must include u(or C2) in the resolving set. Consequently, the minimal resolving set size is |T|. dim(Γ(Q2n)) = 2n−2+ 1. 6 Explicit Examples for Small Order (n= 3) To illustrate the theoretical results derived in Sections 3, 4, and 5, a detailed manual construction of the resolving sets is provided for the smallest non-abelian cases where n= 3. The order of the groups is |G|= 23= 8. 6.1 The Dihedral Group D8 For n= 3, the group is D8=⟨r, s |r4= 1, s2= 1, srs =r−1⟩. The cyclic subgroups are: •Spine: C0={e},C1=⟨r2⟩,C2=⟨r⟩. •Reflections: H1=⟨s⟩,H2=⟨sr⟩,H3=⟨sr2⟩,H4=⟨sr3⟩. In the graph Γ(D8), the spine forms the path C0−C1−C2. The four reflection subgroups H1, . . . , H4are all of order 2 and do not contain any proper non-trivial subgroups. Thus, they are all adjacent exclusively to C0. This creates a “star” of 4 leaves attached to C0. The spine node C1is also attached to C0. According to Theorem 3.1, the metric dimension is 23−1= 4. Indeed, the set W= {H1, H2, H3, H4}is required. If H4is omitted, then d(H4, C0) = 1 and d(C1, C0) = 1. Since H4and C1share the neighbor C0, and are equidistant from all other Hi(distance 2), they become indistinguishable. Thus, all 4 reflection subgroups must be in the resolving set. 6.2 The Quaternion Group Q8 For n= 3, the group is Q8=⟨x, y |x4= 1, y2=x2, y−1xy =x−1⟩. The cyclic subgroups are: •Spine: C0={e},C1=⟨x2⟩=⟨−1⟩,C2=⟨x⟩=⟨i⟩. •Leaves: L1=⟨y⟩=⟨j⟩,L2=⟨xy⟩=⟨k⟩. Note that in Q8, elements like yand xy generate subgroups of order 4. L1={1,−1, j, −j} contains C1={1,−1}. Thus L1∼C1.L2={1,−1, k, −k}contains C1. Thus L2∼C1. The graph consists of C0attached to C1.C1is the central hub, connected to C0, C2, L1, L2. According to Theorem 5.1, dim = 23−2+ 1 = 2 + 1 = 3. The set T={C0, L1, L2} forms the twin set at C1. It is essential to resolve the leaves L1, L2and the base C0against the spine top C2. A valid resolving set is W={C0, L1, L2}. 8 7 Asymptotic Behavior An important question in the study of graph invariants is the asymptotic behavior of the invariant relative to the size of the graph or the underlying algebraic structure. The ratio of the metric dimension to the order of the group as n→ ∞ is examined. Let β(G) = dim(Γ(G)) |G|denote the metric dimension density. Proposition 7.1. For the families of 2-groups of maximal class, the asymptotic metric dimension densities are: 1. limn→∞ β(D2n) = 1 2. 2. limn→∞ β(SD2n) = 3 8. 3. limn→∞ β(Q2n) = 1 4. Proof. The order of all groups is |G|= 2n. 1. For the Dihedral group: lim n→∞ 2n−1 2n= lim n→∞ 1 2= 0.5 This indicates that for large n, half of the subgroups in the graph must be sensors to resolve the structure, reflecting the high symmetry of the reflections. 2. For the Semi-Dihedral group: lim n→∞ 3·2n−3−1 2n= lim n→∞ 3·2n·2−3 2n−1 2n=3 8= 0.375 3. For the Generalized Quaternion group: lim n→∞ 2n−2+ 1 2n= lim n→∞ 2n·2−2 2n+1 2n=1 4= 0.25 Figure 1 visualizes this convergence. As nincreases, the metric dimension ratio stabilizes to the theoretical limits derived in Proposition 7.1. This asymptotic analysis quantitatively confirms the structural observations. The Quaternion group graphs are the “simplest” to resolve relative to their size (requiring only 25% of nodes), while Dihedral graphs are the most complex (requiring 50%), with Semi-Dihedral graphs occupying the intermediate spectrum. 8 Computational Analysis The theoretical results were verified using Python-based algorithms on the NetworkX graph library. The metric dimension was calculated by brute-force search for minimal resolving sets for groups of small order. Table 1 summarizes the results. Structural Comparison: The data highlights the structural divergence. •D2ngrows most rapidly. Its graph is a “star” centered at {e}, requiring roughly half the group elements to resolve the leaves. 9