On minimal graphs for hamiltonian groups and their fixing set

Kirti Sahu, Ranjit Mehatari · 2026

Read On minimal graphs for hamiltonian groups and their fixing set by Kirti Sahu, Ranjit Mehatari (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-21575.txt.

Introduction

Kirti Sahu and Ranjit Mehatari compute the smallest graphs whose symmetry group is a Hamiltonian group. A Hamiltonian group is a non-commutative group where every subgroup is normal, a rare and tidy structure. Graphs with exactly that group of symmetries are of special interest in algebra.

The authors find the minimal orders of such graphs. They also study the fixing number, the fewest vertices to pin down so no symmetry survives. Both numbers measure how cheaply a tidy group can be realized as pure symmetry. The results add concrete data to the link between group theory and graph design.

Catalog record

CREATORKirti Sahu, Ranjit Mehatari
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE21 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-21575

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On minimal graphs for hamiltonian groups and their fixing set Kirti Sahu, Ranjit Mehatari Abstract A finite non-abelian group H H is hamiltonian if all of its subgroups are normal. We compute the minimal orders of graphs having a hamiltonian group as their automorphism group. The fixing number of a graph Γ \Gamma is the minimum cardinality of a subset S S of V ⁡ ( Γ ) V(\Gamma) such that the stabilizer of S S is trivial. For a given finite group G G , the fixing set is defined as the set comprising all possible fixing numbers of graphs having group G G as their automorphism groups. We determine the fixing sets corresponding to finite hamiltonian groups. AMS Subject Classification (2020): 05C25. Keywords: Automorphism group, hamiltonian group, vertex-minimal graph, fixing number, fixing set. 1 Introduction Suppose \Gamma be a simple finite graph having vertex set V(\Gamma) and edge set E(\Gamma) . Define an automorphism of graph \Gamma as an adjacency-preserving permutation from its vertex set to itself. Then the set consisting of all automorphisms of \Gamma , represented by \mathop{\mathrm{Aut}}\Gamma , forms a group known as automorphism group of \Gamma . In 1936, König asked a question in his book: when is it possible for a given group be expressed as the automorphism group of some graph? In response to this question, Frucht [ 9 ] proved that for every finite group G , there exist a graph \Gamma such that the automorphism group of \Gamma is isomorphic to G . Later, he proved that if \Gamma is a cubic graph [ 7 ] then the solution to the above question is also possible. In 1957, Sabidussi [ 26 ] proved the question with some extra properties of graphs, such as prescribed regularity, prescribed chromatic number, or vertex-connectivity. However, for a given group G , we have infinite number of graphs having group G as their full automorphism group. Considering G to be a finite group, we define \alpha(G) as the minimum number of vertices among all graphs \Gamma such that \mathop{\mathrm{Aut}}\Gamma\cong G . Babai proved in [ 3 ] that if G is a finite group other than C_{3} , C_{4} , and C_{5} , then \alpha(G)\leq 2|G| . The exact value of \alpha(G) for various groups has been determined completely: finite abelian groups [ 1 ] , symmetric groups [ 25 ] , alternating groups A_{n} for degree n\geq 13 [ 22 ] , hyperoctahedral groups [ 14 ] , dihedral groups [ 10 , 12 , 15 , 24 ] , generalized quaternion groups [ 11 ] , quasi-abelian groups [ 21 ] , quasi-dihedral groups [ 21 ] , and modular p -groups [ 27 ] . Throughout this paper, we consider a family of groups called hamiltonian groups. A non-abelian group H is said to be hamiltonian if every subgroup of H is normal. A nice characterization of hamiltonian groups is given as follows. Theorem 1.1 . [ 16 ] A hamiltonian group is the direct product of a quaternion group with an abelian group in which every element is of finite odd order and an abelian group of exponent two. Arlinghaus [ 1 ] evaluated the value of \alpha(A) , for A to be a finite abelian group. His results are too lengthy to recall here. We use a few of these results to determine \alpha(H) , where H is a hamiltonian group. Let G be a group that acts on set X , and x\in X . Define \mathop{\mathrm{stab}}(x)=\{g\in G:g(x)=x\} as the stabilizer of x . The set-wise stabilizer of set Y\subseteq X is \mathop{\mathrm{stab}}(Y)=\{g\in G:g(y)=y,\forall y\in Y\} . For a graph \Gamma , the fixing number (equivalently, the determining number defined in [ 4 ] ) is defined as the minimum cardinality of vertex subset S of V(\Gamma) such that \mathop{\mathrm{stab}}(S) is trivial, and S is called a fixing set of \Gamma . The study of fixing sets of different graphs families have been studied by various authors. While the fixing numbers for certain cases of Kneser graphs have been studied in [ 4 , 5 ] and for Fullerene graphs in [ 18 ] , the fixing numbers for trees and complete graphs have been characterized in [ 8 ] . The concept of fixing the number of graphs has been extended to finite groups by Gibbons and Laison [ 13 ] . For a finite group G , the fixing set ( \mathop{\mathrm{fix}}(G) ) is defined as the set consisting all fixing numbers of graphs having group G as their full automorphism group. Researchers have completely determined the fixing sets of finite abelian groups [ 13 ] , generalized quaternion groups [ 6 ] , dihedral groups [ 20 ] , quasi-abelian groups [ 2 ] , quasi-dihedral groups [ 2 ] , and modular p -groups [ 27 ] . For finite abelian groups we have the following theorem. Theorem 1.2 . [ 13 ] Suppose for a finite abelian group A , the number of elementary divisors be d . Then \mathop{\mathrm{fix}}(A)=\{1,2,\ldots,d\} . In [ 13 ] , Gibbons and Laison proved the following lemma: Lemma 1.3 . [ 13 ] Suppose G_{1} and G_{2} are two non-trivial finite groups, then the set \mathop{\mathrm{fix}}(G_{1})+\mathop{\mathrm{fix}}(G_{2})\subseteq\mathop{\mathrm{fix}}(G_{1}\times G_{2}) , where the sum \mathop{\mathrm{fix}}(G_{1})+\mathop{\mathrm{fix}}(G_{2}) is defined as \{a+b\mid a\in\mathop{\mathrm{fix}}(G_{1}),b\in\mathop{\mathrm{fix}}(G_{2})\} . Further,they posed the following open problem: Problem 1.4 . [ 13 ] Let G_{1} and G_{2} be any two finite non-trivial groups. Is it true that \mathop{\mathrm{fix}}(G_{1})+\mathop{\mathrm{fix}}(G_{2})=\mathop{\mathrm{fix}}(G_{1}\times G_{2})\setminus\{1\} ? The above open problem is certainly true if both G_{1} and G_{2} are abelian. We solve Problem 1.4 partially by considering \mathop{\mathrm{fix}}(G_{1})=\{1,2,\ldots,d\} and \mathop{\mathrm{fix}}(G_{2})=\{1\} . As a consequence of the above result, we determine the fixing set for hamiltonian groups. The structure of this article is as follows: In Section 2, we discuss several useful results and the notions that we use later on to prove our main results. In Section 3, we construct vertex-minimal graphs for a finite hamiltonian group H and determine \alpha(H) . Finally, in Section 4, we provide a partial solution to Problem 1.4 and compute \mathop{\mathrm{fix}}(H) . 2 Preliminaries This section presents several key concepts and preliminary results that serve as essential tools for proving the main results of this paper. Throughout this paper, all graphs and grops considered are assumed to be finite, unless explicitly stated otherwise. This paper is devoted to the computation of \alpha(H) . Throughout the work, we consider H as a permutation group. Let G be a permutation group acting on a set X with n symbols, and x\in X . Then the set O(x)=\{g(x):g\in G\} is defined as the orbit of x . Let \Gamma be a graph with the vertex set V(\Gamma) and the edge set E(\Gamma) . If G is a subgroup of the symmetric group S_{V(\Gamma)} , then the Edge Orbit of an edge [v_{1},v_{2}]\in E(\Gamma) is defined as O\{v_{1},v_{2}\}=\Big\{[g(v_{1}),g(v_{2})]:g\in G\Big\}. Also, we define the support of a permutation g\in G as \mathop{\mathrm{supp}}(g)=\{x\in X:g(x)\neq x\} . The quaternion group Q_{8} is defined as Q_{8}=\langle\sigma,\tau\mid\sigma^{4}=\tau^{4}=1,\sigma^{2}=\tau^{2},\sigma\tau=\tau\sigma^{-1}\rangle . The following lemma describes the subgroup representation of quaternion group Q_{8} in symmetric group, which is as follows. Lemma 2.1 . For

Read the complete text