Vertex-minimal graphs with nonabelian $${\mathbf{2}}$$ 2 -group symmetry
- PDF / 563,501 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 93 Downloads / 182 Views
Vertex-minimal graphs with nonabelian 2-group symmetry L.-K. Lauderdale1 · Jay Zimmerman1 Received: 13 October 2019 / Accepted: 17 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract A graph whose full automorphism group is isomorphic to a finite group G is called a G-graph, and we let α(G) denote the minimal number of vertices among all Ggraphs. The value of α(G) has been established for numerous infinite families of groups. In this article, we expand upon the subject matter of vertex-minimal G-graphs by computing the value of α(G) when G is isomorphic to either a quasi-dihedral group or a quasi-abelian group. These results completely establish the value of α(G) when G is a member of one of the six infinite families of 2-groups that contain a cyclic subgroup of index 2. Keywords Automorphism group · Graph · Vertex-minimal · Quasi-abelian group · Quasi-dihedral group
1 Introduction Throughout this article, all groups considered are finite and all graphs considered are simple and finite. In 1936, König [16] famously inquired about which abstract groups could be realized as the automorphism group of some graph. Three years later, Frucht [5] proved that for every group G, there exists a graph whose full automorphism group is isomorphic to G; such a graph is called a G-graph. For a group G, let α(G) denote the minimal number of vertices among all G-graphs. In general, α(G) ≤ 3|G| and the cyclic groups of orders 3, 4, and 5 demonstrate that this bound is best possible (i.e., α(G) = 3|G| provided G is a cyclic group of orders 3, 4, or 5). Without sacrificing much generality, Babai improved this bound on the value of α(G). Theorem 1 (Babai [2]) If G is a group different from the cyclic group of orders 3, 4, or 5, then α(G) ≤ 2|G|.
B 1
L.-K. Lauderdale [email protected] Towson University, Towson, MD, USA
123
Journal of Algebraic Combinatorics
The constant 2 in Theorem 1 is sharp. For example, Sabidussi [23] proved that α(G) = 2|G| for cyclic groups of prime order p ≥ 7, and Graves et. al. [9] proved equality for generalized quaternion groups. However, this constant can be sharpened for most groups by considering a graphical regular representation. A graph is a graphical regular representation (GRR) of a group G if the automorphism group of is a regular permutation group that is isomorphic to G. In this case, G admits a GRR, and the GRR problem was to identify all groups that admit a GRR. It follows immediately from these definitions that if the group G admits a GRR, then α(G) ≤ |G|. The results of numerous authors provided partial solutions for the GRR problem (see [4,14,15,20,21,24,26–28]). A complete classification of groups that admit a GRR was found by Hetzel [13] and Godsil [6,7], and we state their result below. Theorem 2 (Hetzel [13], Godsil [6,7]) The group G admits a GRR provided it is distinct from each of the following groups: (a) (b) (c) (d)
an abelian group of exponent greater than 2; an elementary abelian group of orders 4, 8, or 16; a generalized dicycl
Data Loading...
