×

zbMATH — the first resource for mathematics

Ádám’s conjecture is true in the square-free case. (English) Zbl 0833.05063
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 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).

MSC:
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures
20C05 Group rings of finite groups and their modules (group-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ádám, A, Research problem 2-10, J. combin. theory, 2, 393, (1967)
[2] Alspach, B; Parsons, T.D, Isomorphism of circulant graphs and digraphs, Discrete math., 25, 97-108, (1979) · Zbl 0402.05038
[3] Babai, L, Isomorphism problem for a class of point-symmetric structures, Acta math. acad. sci. hungar., 29, 329-336, (1977) · Zbl 0378.05035
[4] Djoković, D.Ź, Isomorphism problem for a special class of graphs, Acta math. acad. sci. hungar., 21, 267-270, (1970)
[5] Egorov, V.N; Markov, A.I, On ádám’s conjecture for graphs with circulant adjacency matrices, Soviet math. dokl., 20, 1292-1296, (1979), [In Russian] · Zbl 0443.05058
[6] Elspas, B; Turner, J, Graphs with circulant adjacency matrices, J. combin. theory, 9, 297-307, (1970) · Zbl 0212.29602
[7] Ganushkin, A.G, Schur rings over cyclic groups of order pqr, (), 15, [in Russian]
[8] Gol’fand, Y.Y; Gol’fand, Y.Y, On the subring structure of V(sp1 x … x spm), (), 65-76, Soviet Series
[9] Hall, M, Group theory, (1959), MacMillan New York
[10] Klin, M, Schur rings over cyclic groups and automorphism groups of circulant graphs, (), 12, Tagungsbericht
[11] \scM. H. Klin, M. E. Muzychuk, and A. Woldar, Circulant graphs via Schur rings theory, I, mass. in preparation.
[12] Klin, M.H; Pöschel, R, The König problem, the isomorphism problem for cyclic graphs and the method of Schur rings, (), 405-434 · Zbl 0416.05044
[13] Muzychuk, M, On the structure of basic sets of Schur rings over cyclic groups, J. algebra, 162, 2, 665-678, (1994) · Zbl 0810.20005
[14] Pálfy, P.P, On regular pronormal subgroups of symmetric groups, Acta math. acad. sci. hungar., 34, 287-292, (1979) · Zbl 0437.20003
[15] Pálfy, P.P, Isomorphism problem for relational structures with a cyclic automorphism, Europ. J. combin., 8, 35-43, (1987) · Zbl 0614.05049
[16] Tyškevič, R.I, Pronormal regular subgroups of finite symmetric groups, Zap. nauch. sem. leningrad. otdel. mat. inst. Steklov, 103, 132-139, (1980), [in Russian] · Zbl 0516.20005
[17] Wielandt, H, Finite permutation groups, (1964), Akademische Press Berlin · Zbl 0138.02501
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.