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.

5 pages. Minor revision, to appear in Electronic Journal of Combinatorics

References in corpus (2)

• Heat kernels are not uniform expanders
• Nonamenable Liouville Graphs