Degrees in link graphs of regular graphs

Journal article

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 $\mathcal{G}$ is d-regular and connected but not complete then some link graph of $\mathcal{G}$ has inimum degree at most $\mathcal{⌊2d/3⌋−1}$, and if $\mathcal{G}$ is sufficiently large in terms of d then some link graph has minimum degree at most $\mathcal{⌊d/2⌋−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.

Authors: Benjamini, I; Haslegrave, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Electronic Journal of Combinatorics
• Journal: Electronic Journal of Combinatorics
• Volume: 29
• Issue: 2
• Article number: P2.23
• Publication date: 2022-05-06
• Acceptance date: 2022-03-02
• DOI: 10.37236/10561
• EISSN: 1077-8926
• Language: English
• Keywords: 05C35; FFR; 05C07