Isomorphism of circulant graphs and digraphs |
| |
Authors: | Brian Alspach TD Parsons |
| |
Institution: | Simon Fraser University, Burnaby, B.C. V5A 1S6, Canada;Pennsylvania State University, University Park, PA 16802, U.S.A. |
| |
Abstract: | Let S? {1, …, n?1} satisfy ?S = S mod n. The circulant graph G(n, S) with vertex set {v0, v1,…, vn?1} and edge set E satisfies vivj?E if and only if j ? i ∈ S, where all arithmetic is done mod n. The circulant digraph G(n, S) is defined similarly without the restriction S = ? S. Ádám conjectured that if and only if S = uS′ for some unit u mod n. In this paper we prove the conjecture true if n = pq where p and q are distinct primes. We also show that it is not generally true when n = p2, and determine exact conditions on S that it be true in this case. We then show as a simple consequence that the conjecture is false in most cases when n is divisible by p2 where p is an odd prime, or n is divisible by 24. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|