Character Sums for Cayley Graphs

Abstract

Following [1], by a Cayley digraph we mean a graph Cay(G, S) whose vertex set is a group G, and there exists a directed edge from a vertex g to another vertex h if g-1h ∈ S, where S is a generating subset of G. The graph Cay (G, S) is called a Cayley graph if S = S-1 and 1 ∉ S. In Problem 3.3 of the above cited article, the following question is proposed. Let G be a finite group, let Γ = Cay(G, S) be a Cayley digraph, v a positive integer, and (Formula Presented.) It is easy to see that the set Mv is an invariant for the Cayley digraphs if the underlying group G is abelian. Here we negatively answer the above problem. We show that for every n ≥ 4 there is a Cayley graph Γn on the symmetric group Sn so that the above set Mv is not an invariant of Γn. We also find some other groups with the latter property. © 2015, Copyright Taylor & Francis Group, LLC.