Tamara Koledin, Zoran Stanic: Notes on Johnson and Hamming signed graphs, 303-315

Abstract:

We consider relations between symmetric association schemes and strongly regular signed graphs. Our results include constructions of new examples of such signed graphs, relations between their structure and spectrum, and their classification into the known classes. We also propose definitions of Johnson signed graphs and Hamming signed graphs, compute their eigenvalues, and provide necessary and sufficient conditions for their strong regularity. Some constructions of strongly regular Johnson signed graphs with five eigenvalues are provided - according to our knowledge, these are the first examples of strongly regular signed graphs with more than four eigenvalues.

Key Words: Strongly regular signed graph, symmetric association scheme, Johnson graph, Hamming graph, spectrum.

2010 Mathematics Subject Classification: Primary 05C50; Secondary 05C22.

Download the paper in pdf format here.