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 ⁻¹ h ∈ S, where S is a generating subset of G. The graph Cay(G, S) is called a Cayley graph if S = S ⁻¹ 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, ν a positive integer, and

where χ₁, …, χ _h are all irreducible characters of G.

Is the set M _ν = {μ _i  | χ _i (1) = ν} an invariant of Γ? (Thus, does Cay(G, S) ≅ Cay(G, S′) imply ?)

It is easy to see that the set M _ν 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 S _n so that the above set M _ν is not an invariant of Γ _n . We also find some other groups with the latter property.

Key Words:

• Cayley graphs
• Irreducible characters of finite groups
• Spectra of graphs

2010 Mathematics Subject Classification:

• 20C15
• 05C50

ACKNOWLEDGEMENTS

The authors are very grateful to the referee for his/her valuable comments.

Notes

Communicated by A. Turull.