On isomorphisms of finite Cayley graphs---a survey
type: Item
instance of: scholarly article
title: On isomorphisms of finite Cayley graphs---a survey
zbMATH Open document ID: 1018.05044
DOI: 10.1016/S0012-365X(01)00438-1
author: Cai Heng Li
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: This article is a systematic survey of various research directions concerning finite (directed) graphs and groups having the Cayley isomorphism property (shortly: CI-graphs and DCI-groups). Both theorems and examples are presented in a large number (only a few of them will be emphasized in what follows). The author calls a group \(G\) an \(m\)-DCI-group if all Cayley digraphs of valency at most \(m\) are CI-graphs; this notion can be modified (i) by replacing ``at most'' by ``exactly'', and/or (ii) by restricting our attention to undirected graphs. The majority of the results stated are not proved in this paper. After introducing some notions and exposing the problems, Section 2 contains several examples. Among them, it is shown that two Cayley graphs \(\text{Cay}(G_1, S_1)\) and \(\text{Cay}(G_2, S_2)\) may be isomorphic even if \(G_1\) and \(G_2\) are non-isomorphic groups. Furthermore, the representation of \(K_{m;d}\) (the complete \(d\)-partite graph such that each part has size \(m\)) as a Cayley graph is discussed. Sections 3 and 4 are devoted to the study of CI-graphs. Let the theorem of Babai (given with proof) be sorted out from the results: \(\Gamma= \text{Cay}(G, S)\) is a CI-graph exactly if all regular subgroups of \(\text{Aut }\Gamma\) isomorphic to \(G\) are conjugate. In Section 5 connected non-CI-graphs \(\Gamma= \text{Cay}(G,S)\) are constructed so that (iii) either \(G\) is a cyclic group of prime-power order, or (iv) \(S\) is a minimal generating system of \(G\). (In an example of type (iv), \(G\) coincides with the alternating group \(A_5\).) Various graph classes are considered in Section 6, the CI-graphs are separated from the non-CI-graphs within these classes. We quote the theorem of Hirasaka and Muzychuk: All connected Cayley graphs of valency two of finite simple groups are CI-graphs. Our attention is focussed on cyclic groups and circulant digraphs in Section 7. The theorem of Muzychuk is stated, it determines the numbers \(n\) for which…
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 20B25
Mathematics Subject Classification ID: 20E99
zbMATH DE Number: 1838928
zbMATH Keywords: Cayley isomorphism property
zbMATH Keywords: CI-graphs
zbMATH Keywords: simple groups
zbMATH Keywords: cyclic group
zbMATH Keywords: open problems
reviewed by: A. Ádám
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00438-1
OpenAlex ID: W2094583082
description: scientific article; zbMATH DE number 1838928