No Access

EXTREMAL CAYLEY GRAPHS OF FINITE CYCLIC GROUPS

JOSEPH J. LEE

Harvard School of Engineering and Applied Sciences, Harvard University, 29 Oxford St. Cambridge, MA 02138, USA

Search for more papers by this author

ELYSIA J. SHEU

Sibley School of Mechanical and Aerospace Engineering, Cornell University, 105 Upson Hall, Ithaca, NY 14853, USA

Search for more papers by this author

, and

XINGDE JIA

Department of Mathematics, Texas State University, San Marcos, TX 78666, USA

Search for more papers by this author

https://doi.org/10.1142/S0219265908002163Cited by:0 (Source: Crossref)

Abstract

Let Γ be a finite group with a nonempty subset A. The Cayley graphCay(Γ, A) of Γ generated by A is defined as the digraph with vertex set Γ and edge set {(x,y) | x^-1 y ∈ A}. Cay(Γ, A) can be regarded as an undirected graph if x^-1 ∈ A for all x ∈ A. Let denote the largest integer M so that there exists a set of integers A = {±1, ±a₂;…, ±a_k} such that the average distance between all pairs of vertices of Cay(ℤ_M,A) is at most r, where ℤ_M is the additive group of residue classes modulo M. It is proved in this paper that

It is also proved that

Keywords:

References

L. Babaiet al., On the diameter of finite groups, Thirty-first Annual Symposium on Foundations of Computer ScienceI, II (IEEE Comput. Soc. Press, 1990) pp. 857–865. Google Scholar
L. Babai, W. M. Kantor and A. Lubotzky, European Journal of Combinatorics 10, 507 (1989). Crossref, Web of Science, Google Scholar
J. C. Bermond, F. Comellas and D. F. Hsu, J. Parallel Distribut. Comput. 24, 2 (1995), DOI: 10.1006/jpdc.1995.1002. Crossref, Web of Science, Google Scholar
S. Chen and X. Jia, Networks 23, 257 (1993), DOI: 10.1002/net.3230230407. Crossref, Web of Science, Google Scholar
R. L. Graham and N. J. A. Sloane, SIAM J. Alg. Discrete Math. 1, 382 (1980), DOI: 10.1137/0601045. Crossref, Web of Science, Google Scholar
M. D. Grammatikakis , D. F. Hsu and M. Kraetzl , Parallel System Interconnections and Communications ( CRC , 2000 ) . Crossref, Google Scholar
J. L. Gross and J. Yellen , Graph theory and its applications , 2nd edn. , Discrete Mathematics and its Applications (Boca Raton) ( Chapman & Hall/CRC , Boca Raton, FL , 2006 ) . Google Scholar
F. K. Hwang, Theoretical Computer Science 299, 107 (2003), DOI: 10.1016/S0304-3975(01)00341-3. Crossref, Web of Science, Google Scholar
D. F. Hsu and X. Jia, SIAM Journal on Discrete Mathematics 7, 57 (1994), DOI: 10.1137/S0895480190184811. Crossref, Web of Science, Google Scholar
D. F. Hsu and X. Jia, Utilitas Math. 66, 61 (2004). Web of Science, Google Scholar
D. F. Hsu and X. Jia. Combinatorial Networks, under preparation, 2008 . Google Scholar
D. F. Hsu and J. Shapiro, Graph theory, combinatorics, algorithms, and applications (San Francisco, CA, 1989) (SIAM, Philadelphia, PA, 1991) pp. 254–265. Google Scholar
D. F. Hsu and J. Shapiro, J. Combin. Inform. System Sci. 16(1), 55 (1991). Web of Science, Google Scholar
X. Jia, J. Number Theory 41, 116 (1992), DOI: 10.1016/0022-314X(92)90088-7. Crossref, Web of Science, Google Scholar
X. Jia. Cayley digraphs of finite cyclic groups with minimal average distance. Interconnection networks and mapping and scheduling parallel computations, New Brunswick, NJ, 1994, 229–250, in DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 21, Amer. Math. Soc, Providence, RI, 1995 . Google Scholar
G. Salazar, Discrete Math. 302, 243 (2005), DOI: 10.1016/j.disc.2004.07.036. Crossref, Web of Science, Google Scholar
C. K. Wong and D. Coppersmith, J. Assoc. Computing Machinery 21, 392 (1974). Crossref, Web of Science, Google Scholar