Title: The isoperimetric problem in Johnson graphs
Abstract: It has been recently proved that the connectivity of distance regular graphs is the degree of the graph. We study the Johnson graphs $J(n,m)$, which are not only distance regular but distance transitive, with the aim to analyze deeper connectivity properties in this class.
The vertex $k$-connectivity of a graph $G$ is the minimum number of vertices that have to be removed in order to separate the graph into two sets of at least $k$ vertices in each one. The isoperimetric function $\mu_G(k)$ of a graph $G$ is the minimum boundary among all subsets of vertices of fixed cardinality $k$. We give the value of the isoperimetric function of the Johnson graph $J(n,m)$ for values of $k$ of the form ${t\choose m}$, and provide lower and upper bounds for this function for a wide range of its parameter. The computation of the isoperimetric function is used to study the $k$-connectivity of the Johnson graphs as well. We will see that the $k$-connectivity grows very fast with $k$, providing much sensible information about the robustness of these graphs than just the ordinary connectivity.
In order to study the isoperimetric function of Johnson graphs we use combinatorial and spectral tools. The combinatorial tools are based on compression techniques, which allow us to transform sets of vertices without increasing their boundary. In the compression process we will show that sets of vertices that induce Johnson subgraphs are optimal with respect to the isoperimetric problem. Upper bounds are obtained by displaying nested families of sets which interpolate optimal ones. The spectral tools are used to obtain lower bounds for the isoperimetric function. These tools allow us to display completely the isoperimetric function for Johnson graphs $J(n,3)$. . Distance regular graphs form a structured class of graphs which include well-known families, as the n-cubes. Isoperimetric inequalities are well understood for the cubes, but for the general class of distance regular class it has only been proved that the connectivity of these graphs equals the degree. As another test case, the project suggests to study the family of so-called Johnson graphs, which are not only distance regular but also distance transitive. Combinatorial and spectral techniques to analyze the problem are available.
Publication Year: 2013
Publication Date: 2013-11-01
Language: en
Type: dissertation
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot