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

Sebastian M. Cioabă, Willem H. Haemers, Travis Johnston, Matt McGinnis

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Let n≥k≥2 be two integers and S a subset of {0,1,…,k−1}. The graph JS(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 JS(3k−2m−1,k) are not determined by spectrum and for m≥2, n≥4m+2 and S={0,1,…,m} the graphs JS(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.
Original languageEnglish
Pages (from-to)219-228
JournalLinear Algebra and its Applications
Volume539
DOIs
Publication statusPublished - 15 Feb 2018

Fingerprint

Association Scheme
Union
Subset
Graph in graph theory
Adjacent
Integer
Class

Keywords

  • Determined by spectrum
  • Eigenvalues
  • Godsil–McKay switching
  • Graph
  • Johnson association scheme
  • Kneser graph

Cite this

Cioabă, Sebastian M. ; Haemers, Willem H. ; Johnston, Travis ; McGinnis, Matt. / Cospectral mates for the union of some classes in the Johnson association scheme. In: Linear Algebra and its Applications. 2018 ; Vol. 539. pp. 219-228.
@article{6bfb988ba3a44013b9d77cd527fe0a89,
title = "Cospectral mates for the union of some classes in the Johnson association scheme",
abstract = "Let n≥k≥2 be two integers and S a subset of {0,1,…,k−1}. The graph JS(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 JS(3k−2m−1,k) are not determined by spectrum and for m≥2, n≥4m+2 and S={0,1,…,m} the graphs JS(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.",
keywords = "Determined by spectrum, Eigenvalues, Godsil–McKay switching, Graph, Johnson association scheme, Kneser graph",
author = "Cioabă, {Sebastian M.} and Haemers, {Willem H.} and Travis Johnston and Matt McGinnis",
year = "2018",
month = "2",
day = "15",
doi = "10.1016/j.laa.2017.11.011",
language = "English",
volume = "539",
pages = "219--228",
journal = "Linear Algebra and its Applications",
issn = "0024-3795",
publisher = "Elsevier Inc.",

}

Cospectral mates for the union of some classes in the Johnson association scheme. / Cioabă, Sebastian M.; Haemers, Willem H.; Johnston, Travis; McGinnis, Matt.

In: Linear Algebra and its Applications, Vol. 539, 15.02.2018, p. 219-228.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

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

AU - Cioabă, Sebastian M.

AU - Haemers, Willem H.

AU - Johnston, Travis

AU - McGinnis, Matt

PY - 2018/2/15

Y1 - 2018/2/15

N2 - Let n≥k≥2 be two integers and S a subset of {0,1,…,k−1}. The graph JS(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 JS(3k−2m−1,k) are not determined by spectrum and for m≥2, n≥4m+2 and S={0,1,…,m} the graphs JS(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.

AB - Let n≥k≥2 be two integers and S a subset of {0,1,…,k−1}. The graph JS(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 JS(3k−2m−1,k) are not determined by spectrum and for m≥2, n≥4m+2 and S={0,1,…,m} the graphs JS(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.

KW - Determined by spectrum

KW - Eigenvalues

KW - Godsil–McKay switching

KW - Graph

KW - Johnson association scheme

KW - Kneser graph

U2 - 10.1016/j.laa.2017.11.011

DO - 10.1016/j.laa.2017.11.011

M3 - Article

VL - 539

SP - 219

EP - 228

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

ER -