ALGEBRAIC COMBINATORICS

no. 5
Automorphisms of the double cover of a circulant graph of valency at most 7
Hujdurović, Ademir1; Mitrović, Đorđe2; Witte Morris, Dave3
1 University of Primorska, UP IAM, Muzejski trg 2, 6000 Koper, Slovenia and University of Primorska, UP FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia
2 University of Primorska, UP FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia
3 Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, Alberta, T1K 3M4, Canada
Algebraic Combinatorics, Volume 6 (2023) no. 5, pp. 1235-1271.

A graph X is said to be unstable if the direct product X×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.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.303
Classification: 05C25, 05C76
Keywords: circulant, double cover, automorphism group
Hujdurović, Ademir 1; Mitrović, Đorđe 2; Witte Morris, Dave 3

1 University of Primorska, UP IAM, Muzejski trg 2, 6000 Koper, Slovenia and University of Primorska, UP FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia
2 University of Primorska, UP FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia
3 Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, Alberta, T1K 3M4, Canada
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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] Baik, Young-Gheel; Feng, Yanquan; Sim, Hyo-Seob; Xu, Mingyao On the normality of Cayley graphs of abelian groups, Algebra Colloq., Volume 5 (1998) no. 3, pp. 297-304 | MR | Zbl

[2] Dixon, John D.; Mortimer, Brian Permutation groups, Graduate Texts in Mathematics, 163, Springer-Verlag, New York, 1996, xii+346 pages | DOI | MR

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

[4] Glover, Henry; Marušič, Dragan Hamiltonicity of cubic Cayley graphs, J. Eur. Math. Soc. (JEMS), Volume 9 (2007) no. 4, pp. 775-787 | DOI | MR | Zbl

[5] Hammack, Richard; Imrich, Wilfried; Klavžar, Sandi 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] Hujdurović, Ademir; Kutnar, Klavdija; Morris, Dave Witte; Morris, Joy On colour-preserving automorphisms of Cayley graphs, Ars Math. Contemp., Volume 11 (2016) no. 1, pp. 189-213 | DOI | MR | Zbl

[7] Hujdurović, Ademir; Mitrović, Djordje; Morris, Dave Witte 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] Kotlov, Andrew; Lovász, László The rank and size of graphs, J. Graph Theory, Volume 23 (1996) no. 2, pp. 185-189 | DOI | MR | Zbl

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

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

[11] Li, Cai Heng 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] Marušič, D.; Scapellato, R.; Zagaglia Salvi, N. A characterization of particular symmetric (0,1) matrices, Linear Algebra Appl., Volume 119 (1989), pp. 153-162 | DOI | MR | Zbl

[13] Morris, Dave Witte 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] Qin, Yan-Li; Xia, Binzhou; Zhou, Sanming Stability of circulant graphs, J. Combin. Theory Ser. B, Volume 136 (2019), pp. 154-169 | DOI | MR | Zbl

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

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

[17] Xu, Ming-Yao 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: