On the Spectra of Certain Graphs Arising from Finite Fields

✍ Scribed by Nancy Tufts Allen

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 560 KB
• Volume: 4
• Category: Article
• ISSN: 1071-5797
• DOI: 10.1006/ffta.1998.0226

✦ Synopsis

Cayley graphs on a subgroup of G¸(3, p), p'3 a prime, are defined and their properties, particularly their spectra, studied. It is shown that these graphs are connected, vertex-transitive, nonbipartite, and regular, and their degrees are computed. The eigenvalues of the corresponding adjacency matrices depend on the representations of the group of vertices. The ''1-dimensional'' eigenvalues can be completely described, while a portion of the ''higher dimensional'' eigenfunctions are discrete analogs of Bessel functions. A particular subset of these graphs is conjectured to be Ramanujan and this is verified for over 2000 graphs. These graphs follow a construction used by Terras on a subgroup of G¸ (2, p). This method can be extended further to construct graphs using a subgroup of G¸(n, p) for n54. The 1-dimensional eigenvalues in this case can be expressed in terms of the 1-dimensional eigenvalues of graphs from G¸(2, p) and G¸ (3, p); this part of the spectra alone is sufficient to show that for n54, the graphs from G¸(n, p) are not in general Ramanujan.

1998 Academic Presss *The results of this paper were first derived for the author's Ph.D. thesis at the University of California, Santa Cruz. The author thanks her Ph.D. advisor Solomon Friedberg for all of his help and encouragement and also Audrey Terras for her support.