On connectivity problems in distance-regular and strongly regular graphs

Jack Koolen

Department of Mathematics, POSTECH, Pohang, Korea

Department of Mathematics, POSTECH, Pohang, Korea

2012/4/24

*Tue*4PM-5PMIn this talk I will discuss two problems of Andries Brouwer.

In the first one he asked whether the minimal number of vertices you need to delete from a strongly regular graph with valency k and intersection numbers λ, μ, in order to disconnect it and such that each resulting component has at least two vertices is 2k-2-λ. We will show that there are strongly where you can use a smaller number of vertices to disconnect it in this way, but we also will give some positive results.

The second question we discuss is how connected a distance-regular graph is far from a fixed vertex.

This is joint work with Sebastian Cioaba and Kijung Kim.

In the first one he asked whether the minimal number of vertices you need to delete from a strongly regular graph with valency k and intersection numbers λ, μ, in order to disconnect it and such that each resulting component has at least two vertices is 2k-2-λ. We will show that there are strongly where you can use a smaller number of vertices to disconnect it in this way, but we also will give some positive results.

The second question we discuss is how connected a distance-regular graph is far from a fixed vertex.

This is joint work with Sebastian Cioaba and Kijung Kim.

Tags: JackKoolen