Graphs with given automorphism group and large clique number

John Haslegrave · 2025

Read Graphs with given automorphism group and large clique number by John Haslegrave (2025) 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-2501-09779.txt.

Introduction

John Haslegrave presents a short 2025 note in graph theory. A graph's automorphism group collects all the ways its structure can be mapped onto itself. Earlier work by Barbieri showed that graphs realizing any given finite symmetry group can have unbounded genus. That result answered a question from Cornwell and others. Haslegrave gives a brief proof of a stronger claim. Those same graphs can have unbounded clique number, so they can contain arbitrarily large sets of points that are all directly connected to each other.

Catalog record

CREATORJohn Haslegrave
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE3 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-09779

Browse the full library · About the Tower of Babel

Full text

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

Graphs with given automorphism group and large clique number
John Haslegrave

Abstract
Barbieri recently showed that the finite graphs realising any given finite automorphism group have unbounded genus, answering a question of Cornwell et al. In this note we give a short proof of a stronger result: they have unbounded clique number.



In a paper concerned primarily with the minimum genus of graphs realising a given automorphism group, Cornwell, Doring, Lauderdale, Morgan and Storr asked how to determine the maximum genus of such a graph, or more precisely the maximum genus of a surface on which such a graph has a cellular embedding
[
2
, Open Question 3]
. Barbieri recently showed that the genus of a connected graph with given automorphism group is unbounded, and so this maximum does not exist for any group
[
1
]
. Barbieri’s construction has high genus by virtue of containing a high-dimensional hypercube. However, we note that this structure does not guarantee that other parameters of potential interest, such as the chromatic number, are also large. We give a simple proof that graphs realising any given automorphism group have unbounded clique number, and hence unbounded genus and chromatic number.

Proposition 1
.

Let
G
be a non-complete finite graph, and let
G^{\prime}
be the graph obtained from
G
by adding a disjoint clique with the same number of vertices and a perfect matching between the two. Then
\operatorname{Aut}(G^{\prime})\cong\operatorname{Aut}(G)
.

Proof.

Let
n=|V(G)|
. The statement holds for the unique non-complete graph on at most
2
vertices, so we may assume
n\geq 3
. We partition
V(G^{\prime})
as
V_{1}\cup V_{2}
, where
|V_{1}|=|V_{2}|=n
and
G^{\prime}[V_{1}]\cong G
and
G^{\prime}[V_{2}]\cong K_{n}
. Furthermore, we may write
V_{2}=\{v^{\prime}\mid v\in V_{1}\}
such that
vv^{\prime}\in E(G^{\prime})
for each
v\in V_{1}
. Note that
G^{\prime}[V_{2}]
is the unique copy of
K_{n}
in
G^{\prime}
, and so any automorphism
\phi
of
G^{\prime}
must have
\phi(V_{2})=V_{2}
and therefore
\phi(V_{1})=V_{1}
. Consequently,
\phi
restricted to
V_{1}
is an automorphism of
G
. Conversely, for any
\psi\in\operatorname{Aut}(G)
, there is a unique
\psi^{\prime}\in\operatorname{Aut}(G^{\prime})
whose restriction to
V_{1}
is
\psi
, obtained by setting
\psi^{\prime}(v^{\prime})=\psi(v)^{\prime}
for each
v\in V_{1}
. For any
\psi_{1},\psi_{2}\in\operatorname{Aut}(G)
we have
(\psi_{1}\psi_{2})^{\prime}=\psi_{1}^{\prime}\psi_{2}^{\prime}
, since these agree on
V_{1}
, and hence
\operatorname{Aut}(G^{\prime})\cong\operatorname{Aut}(G^{\prime})
.
∎

Corollary 2
.

For any graph
G
there exist connected graphs with automorphism group
\operatorname{Aut}(G)
and arbitrarily large clique number.

Proof.

If
G
is not complete, this follows immediately by iterating the construction of Proposition
1
. If
G
is complete then
\operatorname{Aut}(G)\cong S_{n}
for some
n
, and we may apply the same argument to some non-complete graph with the same automorphism group:
\overline{K}_{n}
if
n\geq 2
or the graph obtained from the
6
-vertex path by adding an edge between the second and fourth vertices if
n=1
.
∎

Since the possible values of
\operatorname{Aut}(G)
range over all finite groups
[
3
]
, it follows that any finite group
\Gamma

Read the complete text