Cospectral mates for the union of some classes in the Johnson association scheme

2017/01/30 by Cioabă, Sebastian M., Haemers, Willem H., Johnston, Travis +1
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1701.08747

Abstract

Let n≥ k≥ 2 be two integers and S a subset of \0,1,…,k-1\. The graph J_S(n,k) has as vertices the k-subsets of the n-set [n]=\1,…,n\ and two k-subsets A and B are adjacent if |A∩ B|∈ S. In this paper, we use Godsil-McKay switching to prove that for m≥ 0, k≥ max(m+2,3) and S = \0, 1, ..., m\, the graphs J_S(3k-2m-1,k) are not determined by spectrum and for m≥ 2, n≥ 4m+2 and S = \0,1,...,m\ the graphs J_S(n,2m+1) are not determined by spectrum. We also report some computational searches for Godsil-McKay switching sets in the union of classes in the Johnson scheme for k≤ 5.

Related

• Cospectral mates for generalized Johnson and Grassmann graphs
• Walk Matrix-Based Upper Bounds on Generalized Cospectral Mates
• The graphs which are cospectral with the generalized pineapple graph
• Godsil-McKay switchings for gain graphs
• A Note on a Construction by Pavese and Smaldore