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-5PM
In 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.