Asymptotical results on the automorphism groups of canonical double cover of graphs

Bartłomiej Bychawski; Ademir Hujdurović; Đorđe Mitrović; Gabriel Verret

paper

Asymptotical results on the automorphism groups of canonical double cover of graphs

arXiv:2610.30373

Abstract

The canonical double cover $B X$ of a graph $X$ is the direct product $X \times K_{2}$ . A graph $X$ is stable if every automorphism of $B X$ is induced by automorphisms of $X$ and $K_{2}$ , and unstable otherwise. We prove several asymptotic results on stable and unstable graphs. In particular, we show that the automorphism group of the canonical double cover of almost every graph has order $2$ , and consequently that almost all graphs are stable. We also prove that the dominant sources of instability are having twins and being disconnected, in that order, and that graphs arising from a known construction are the next step in this hierarchy.

arXiv comment18 pages