A graph $X$ is said to be unstable if the direct product $X\times {K}_{2}$ (also called the canonical double cover of $X$) has automorphisms that do not come from automorphisms of its factors $X$ and ${K}_{2}$. It is nontrivially unstable if it is unstable, connected, and non-bipartite, and no two distinct vertices of X have exactly the same neighbors.

We find all of the nontrivially unstable circulant graphs of valency at most $7$. (They come in several infinite families.) We also show that the instability of each of these graphs is explained by theorems of Steve Wilson. This is best possible, because there is a nontrivially unstable circulant graph of valency $8$ that does not satisfy the hypotheses of any of Wilson’s four instability theorems for circulant graphs.

Revised:

Accepted:

Published online:

Keywords: circulant, double cover, automorphism group

Hujdurović, Ademir ^{1};
Mitrović, Đorđe ^{2};
Witte Morris, Dave ^{3}

@article{ALCO_2023__6_5_1235_0, author = {Hujdurovi\'c, Ademir and Mitrovi\'c, {\DJ}or{\dj}e and Witte Morris, Dave}, title = {Automorphisms of the double cover of a circulant graph of valency at most 7}, journal = {Algebraic Combinatorics}, pages = {1235--1271}, publisher = {The Combinatorics Consortium}, volume = {6}, number = {5}, year = {2023}, doi = {10.5802/alco.303}, language = {en}, url = {https://alco.centre-mersenne.org/articles/10.5802/alco.303/} }

TY - JOUR AU - Hujdurović, Ademir AU - Mitrović, Đorđe AU - Witte Morris, Dave TI - Automorphisms of the double cover of a circulant graph of valency at most 7 JO - Algebraic Combinatorics PY - 2023 SP - 1235 EP - 1271 VL - 6 IS - 5 PB - The Combinatorics Consortium UR - https://alco.centre-mersenne.org/articles/10.5802/alco.303/ DO - 10.5802/alco.303 LA - en ID - ALCO_2023__6_5_1235_0 ER -

%0 Journal Article %A Hujdurović, Ademir %A Mitrović, Đorđe %A Witte Morris, Dave %T Automorphisms of the double cover of a circulant graph of valency at most 7 %J Algebraic Combinatorics %D 2023 %P 1235-1271 %V 6 %N 5 %I The Combinatorics Consortium %U https://alco.centre-mersenne.org/articles/10.5802/alco.303/ %R 10.5802/alco.303 %G en %F ALCO_2023__6_5_1235_0

Hujdurović, Ademir; Mitrović, Đorđe; Witte Morris, Dave. Automorphisms of the double cover of a circulant graph of valency at most 7. Algebraic Combinatorics, Volume 6 (2023) no. 5, pp. 1235-1271. doi : 10.5802/alco.303. https://alco.centre-mersenne.org/articles/10.5802/alco.303/

[1] On the normality of Cayley graphs of abelian groups, Algebra Colloq., Volume 5 (1998) no. 3, pp. 297-304 | MR | Zbl

[2] Permutation groups, Graduate Texts in Mathematics, 163, Springer-Verlag, New York, 1996, xii+346 pages | DOI | MR

[3] Canonical double covers of circulants, J. Combin. Theory Ser. B, Volume 154 (2022), pp. 49-59 | DOI | MR | Zbl

[4] Hamiltonicity of cubic Cayley graphs, J. Eur. Math. Soc. (JEMS), Volume 9 (2007) no. 4, pp. 775-787 | DOI | MR | Zbl

[5] Handbook of product graphs, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2011, xviii+518 pages (With a foreword by Peter Winkler) | DOI | MR

[6] On colour-preserving automorphisms of Cayley graphs, Ars Math. Contemp., Volume 11 (2016) no. 1, pp. 189-213 | DOI | MR | Zbl

[7] On automorphisms of the double cover of a circulant graph, Electron. J. Combin., Volume 28 (2021) no. 4, Paper no. 4.43, 25 pages | DOI | MR | Zbl

[8] The rank and size of graphs, J. Graph Theory, Volume 23 (1996) no. 2, pp. 185-189 | DOI | MR | Zbl

[9] Classifying arc-transitive circulants, J. Algebraic Combin., Volume 20 (2004) no. 3, pp. 353-358 | DOI | MR | Zbl

[10] On isomorphisms of finite Cayley graphs—a survey, Discrete Math., Volume 256 (2002) no. 1-2, pp. 301-334 | DOI | MR | Zbl

[11] Permutation groups with a cyclic regular subgroup and arc transitive circulants, J. Algebraic Combin., Volume 21 (2005) no. 2, pp. 131-136 | DOI | MR | Zbl

[12] A characterization of particular symmetric $(0,1)$ matrices, Linear Algebra Appl., Volume 119 (1989), pp. 153-162 | DOI | MR | Zbl

[13] On automorphisms of direct products of Cayley graphs on abelian groups, Electron. J. Combin., Volume 28 (2021) no. 3, Paper no. 3.5, 10 pages | DOI | MR | Zbl

[14] Stability of circulant graphs, J. Combin. Theory Ser. B, Volume 136 (2019), pp. 154-169 | DOI | MR | Zbl

[15] Bipartite double cover https://wikipedia.org/wiki/Bipartite_double_cover

[16] Unexpected symmetries in unstable graphs, J. Combin. Theory Ser. B, Volume 98 (2008) no. 2, pp. 359-383 | DOI | MR | Zbl

[17] Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math., Volume 182 (1998) no. 1-3, pp. 309-319 Graph theory (Lake Bled, 1995) | DOI | MR | Zbl

*Cited by Sources: *