The second eigenvalue of some normal Cayley graphs of high transitive groups

2018/08/03 by Xueyi Huang, Qiongxiang Huang, Huang, Xueyi +3 · 1 citation
Computer Science · Mathematics · #05C50 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Matrix Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.1808.01118

openalex publication_date 2018/08/03 · openalex created_date 2018/08/22 · openalex updated_date 2026/07/28

Abstract

Let Γ be a finite group acting transitively on [n]=\1,2,…,n\, and let G=Cay(Γ,T) be a Cayley graph of Γ. The graph G is called normal if T is closed under conjugation. In this paper, we obtain an upper bound for the second (largest) eigenvalue of the adjacency matrix of the graph G in terms of the second eigenvalues of certain subgraphs of G (see Theorem 2.6). Using this result, we develop a recursive method to determine the second eigenvalues of certain Cayley graphs of S_n and we determine the second eigenvalues of a majority of the connected normal Cayley graphs (and some of their subgraphs) of S_n with max_{τ∈ T}|supp(τ)|≤ 5, where supp(τ) is the set of points in [n] non-fixed by τ.

Cited by

• The Aldous property for normal Cayley graphs on symmetric groups

Related

• On the second largest eigenvalue of some Cayley graphs of the Symmetric\n Group
• On the second eigenvalue of a Cayley graph of the symmetric group
• On the spectral gap of Cayley graphs
• The second largest eigenvalue of some nonnormal Cayley graphs on symmetric groups
• Graphs with high second eigenvalue multiplicity