Combinatorics Seminar 2018

Speaker: Leonid Shalaginov, Chelyabinsk State University

Date: Wed, May 09, 2018

Time: 10:30 - 11:30

Venue: Large Meeting Room

Title: Dual Seidel switching and Deza graphs


Permuting the rows (and not the columns) of the adjacency matrix of a graph is called dual Seidel switching. This operation was introduced in [H84] as a possible way to construct strongly regular graphs with $\lambda = \mu$ from the existing ones.

A $k$-regular graph $G$ on $v$ vertices is a Deza graph with parameters $(v, k, b, a)$, where $v > k\geq b\geq a\geq 0$, if the number of common neighbours of two distinct vertices takes on one of two values $a$ or $b$, not necessarily depending on the adjacency of the two vertices. A Deza graph is called a strictly Deza graph if it has diameter 2 and is not strongly regular. In [EFHHH99], the dual Seidel switching was adopted to obtain strictly Deza graphs from strongly regular graphs.

In this talk we give a survey of results on Deza graphs obtained by the dual Seidel switching. This is joint work in progress with Sergey Goryainov and Vladislav V. Kabanov.


[H84] Haemers W. H., Dual Seidel switching. Eindhoven: Technical University Eindhoven. 1984. P. 183--191.

[EFHHH99] Erickson M., Fernando S., Haemers W. H., Hardy D. and Hemmeter J., Deza graphs: a generalization of strongly regular graphs. J. Comb. Designs. 1999. V. 7. P. 359--405.

[KS10] Kabanov V. V., Shalaginov L. V., On Deza graphs with parameters of lattice graphs. Trudy Inst. Mat. Mekh. UrO RAN. 2010. V. 3. P. 117--120.

[S11] Shalaginov L. V., On Deza graphs with parameters of triangular graphs. Trudy Inst. Mat. Mekh. UrO RAN. 2011. V. 1. P. 294--298.

[GS13] Goryainov S. V., Shalaginov L. V., On Deza graphs with triangular and lattice graph complements as parameters. J. Appl. Industr. Math. 2013. V. 3. P. 355--362.

Slides: View slides