Paperlane

no. 1 · Friday 23 October 2026

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

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

math.CO · 18 pp

Abstract

The canonical double cover $BX$ of a graph $X$ is the direct product $X\times K_2$. A graph $X$ is stable if every automorphism of $BX$ 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.

comments
18 pages
fields
Combinatorics
pdf ↗ page arXiv:2610.30373 ↗