Degrees in Link Graphs of Regular Graphs

Abstract

We analyse an extremal question on the degrees of the link graphs of a finite regular graph, that is, the subgraphs induced by non-trivial spheres. We show that if $G$ is $d$-regular and connected but not complete then some link graph of $G$ has minimum degree at most $\lfloor{2d/3}\rfloor-1$, and if $G$ is sufficiently large in terms of $d$ then some link graph has minimum degree at most $\lfloor{d/2}\rfloor-1$; both bounds are best possible. We also give the corresponding best-possible result for the corresponding problem where subgraphs induced by balls, rather than spheres, are considered.

We motivate these questions by posing a conjecture concerning expansion of link graphs in large bounded-degree graphs, together with a heuristic justification thereof.