Ádám's conjecture is true in the square-free case
type: Item
instance of: scholarly article
title: Ádám's conjecture is true in the square-free case
zbMATH Open document ID: 0833.05063
DOI: 10.1016/0097-3165(95)90031-4
published in: Journal of Combinatorial Theory. Series A
publication date: 1996-03-11T00:00:00Z
review text: The reviewer [J. Comb. Theory 2, 393 (1967); see also Acta Cybern. 3, 187-214 (1977; Zbl 0374.94037)] conjectured that two circulant directed graphs having \(n\) vertices are isomorphic only if a certain special isomorphism (by means of a number \(r\) relatively prime to \(n\)) can be established between them. Partial results and incomplete attempts, due to several authors, are crowned in the present article: a full proof of the conjecture is achieved in the case of a square-free \(n\). Involved algebraic discussions are carried out, using techniques from the theory of permutation groups and the theory of Schur rings. The basic idea is to analyze the 2-closed permutation groups \(G\) fulfilling \(C_n\leq G\leq {\mathfrak S}(C_n)\), where \(C_n\) is the cyclic group of order \(n\) and \(n\) is supposed to be square-free. It turns out that any two regular cyclic subgroups of \(G\) are then conjugate. (This is shown in three steps: (i) \(G\) is primitive, (ii) the number \(k\) of elements of the imprimitivity system is prime, (iii) \(k\) is composite.) Hence, the truth of the conjecture follows from a theorem of \textit{L. Babai} [Acta. Math. Acad. Sci. Hungar. 29, 329-336 (1977; Zbl 0378.05035)]. It is worthy being noticed that the conjecture is known to be false if \(n\) is divisible by 8 or by the square of an odd prime, and it is (in general) undecided in the remaining case (i.e. when \(n/4\) is a square- free odd integer).
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 20B25
Mathematics Subject Classification ID: 20C05
zbMATH DE Number: 802352
zbMATH Keywords: Ádám's conjecture
zbMATH Keywords: circulant directed graphs
zbMATH Keywords: square-free
zbMATH Keywords: permutation groups
zbMATH Keywords: Schur rings
author: Mikhail Muzychuk
reviewed by: A. Ádám
MaRDI profile type: Publication
full work available at URL: 0097-3165(95)90031-4
OpenAlex ID: W2031171110
Wikidata QID: Q123267658
cites work: Isomorphism of circulant graphs and digraphs
cites work: Isomorphism problem for a class of point-symmetric structures
cites work: Isomorphism problem for a special class of graphs
cites work: Q3885795
cites work: Graphs with circulant adjacency matrices
cites work: Q3253828
cites work: Q3205264
cites work: On the structure of basic sets of Schur rings over cyclic groups
cites work: On regular pronormal subgroups of symmetric groups
cites work: Isomorphism problem for relational structures with a cyclic automorphism
cites work: Q3663508
cites work: Q5512231
Recommended article: The isomorphism problem for circulant graphs via Schur ring theory
Recommended article: Isomorphisms of circulant digraphs of degree 3
Recommended article: Non-Cayley-isomorphic self-complementary circulant graphs
Recommended article: Q3469128
Recommended article: Isomorphism testing for circulant graphs \(C_n (a, b)\)
Recommended article: Corrigendum to: On Ádám's conjecture for circulant graphs
Recommended article: Q3722531
Recommended article: Q4373397
Recommended article: Isomorphisms of circulant digraphs
Recommended article: Q3317154
description: scientific article; zbMATH DE number 802352