Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Toida’s Conjecture is True"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Toida’s Conjecture is True | Toida s Conjecture is True Edward Dobson Department of Mathematics and Statistics PO Drawer MA Mississippi State MS 39762 U.S.A. dobson@math.msstate.edu Joy Morris Department of Mathematics and Computer Science University of Lethbridge Lethbridge Alberta Canada T1K 3M4 morris@cs.uleth.ca Submitted January 31 2000 Accepted March 31 2002. MR Subject Classifications 05C25 20B25 Abstract Let S be a subset of the units in zn. Let r be a circulant graph of order n a Cayley graph of zn such that if ij 2 E r then i j mod n 2 S. Toida conjectured that if rz is another circulant graph of order n then r and rz are isomorphic if and only if they are isomorphic by a group automorphism of zn. In this paper we prove that Toida s conjecture is true. We further prove that Toida s conjecture implies Zibin s conjecture a generalization of Toida s conjecture. In 1967 Adam conjectured 1 that two Cayley graphs of Zn are isomorphic if and only if they are isomorphic by a group automorphism ofZn. Although this conjecture was disproved by Elspas and Turner three years later 7 the problem and its generalizations have subsequently aroused considerable interest. Much of this interest has been focused on the Cayley Isomorphism Problem which asks for necessary and sufficient conditions for two Cayley graphs on the same group to be isomorphic. Particular attention has been paid to determining which groups G have the property that two Cayley graphs of G are isomorphic if and only if they are isomorphic by a group automorphism of G. Such a group is called a CI-group CI stands for Cayley Isomorphism . One major angle from which the Cayley Isomorphism problem was considered was the question of which cyclic groups are in fact CI-groups. The problem raised by Adam s conjecture has now been completely solved by Muzychuk 15 and 16 . He proves that a cyclic group of order n is THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2002 R35 1 a CI-group if and only if n k 2k or 4k where k is odd and square-free. The .