Vertex-minimal planar graphs with cyclic 2-group symmetry
- PDF / 562,019 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 24 Downloads / 180 Views
Vertex-minimal planar graphs with cyclic 2-group symmetry Kassie Archer1 · Rebecca Darby1 · L.-K. Lauderdale2 · Asa Linson1 · Mariah K. Maxfield1 · Charles Schmidt1 · Phung T. Tran3 Received: 8 July 2018 / Accepted: 31 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract For the positive integer m, let Zm denote the cyclic group of order m. Vertex-minimal planar graphs with prescribed automorphism group Zm were first considered by Marušiˇc. In particular, when m is odd he produced a vertex-minimal planar graph with Zm -symmetry. Marušiˇc then conjectured the order of a vertex-minimal planar graph with Zm -symmetry when m is a power of 2; in this article, we prove his conjecture. We conclude by discussing vertex-minimal planar graphs with noncyclic automorphism groups and pose some open questions.
1 Introduction The automorphism group of a graph , denoted Aut , is the set of adjacencypreserving permutations of the vertices. Frucht [5] proved that for any finite group G, there exists a graph such that Aut ∼ = G. Naturally, this result gave rise to numerous extremal problems in graph theory. For instance, vertex-minimal graphs with a prescribed automorphism group are the subject of prior research by numerous authors. In this article, we are primarily interested in vertex-minimal planar graphs with cyclic automorphism groups. For a finite group G, let α(G) denote the minimal number of vertices among all graphs whose automorphism groups are isomorphic to G. The graphical regular representation problem and the minimal degree of a faithful representation of a group, which we discuss below, give bounds on the value of α(G). A simple graph is said to be a graphical regular representation (GRR) of the finite group G if Aut is a
B
Kassie Archer [email protected]
1
University of Texas at Tyler, Tyler, TX, USA
2
Towson University, Towson, MD, USA
3
University of New Mexico, Albuquerque, NM, USA
123
Journal of Algebraic Combinatorics
regular permutation group that is isomorphic to G. In this case, G admits a GRR, and the GRR problem was to identify all finite groups that admit a GRR. Clearly, if G is a finite group that admits a GRR, then α(G) ≤ |G|. The results of numerous authors combined to solve the GRR problem. Theorem 1 [4,7,8,14–16,23,24,27–30] Suppose G is a finite group distinct from each of the following groups: (a) (b) (c) (d)
an abelian group of exponent greater than 2; an elementary abelian group of order 4, 8 or 16; a generalized dicyclic group; and one of 10 exceptional groups whose orders are at most 32 (including the dihedral groups of order 6, 8 and 10, the alternating group of degree 4, and three cyclic extensions of the quaternion group).
Under these assumptions, the group G admits a GRR, and thus, α(G) ≤ |G|. The abelian groups considered in this article do not admit a GRR, and thus, the upper bound given in Theorem 1 does not apply. However, all but three finite groups G satisfy the following upper bound proven by Babai [3]. Theorem 2 [3] If G i
Data Loading...
