Degrees in link graphs of regular graphs (Q2138581)

Summary: 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.