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.
1
Weizmann Institute of Science
2
University of Oxford
Itai Benjamini; John Haslegrave. Degrees in link graphs of regular graphs. The electronic journal of combinatorics, Tome 29 (2022) no. 2. doi: 10.37236/10561
@article{10_37236_10561,
author = {Itai Benjamini and John Haslegrave},
title = {Degrees in link graphs of regular graphs},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {2},
doi = {10.37236/10561},
zbl = {1487.05054},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10561/}
}
TY - JOUR
AU - Itai Benjamini
AU - John Haslegrave
TI - Degrees in link graphs of regular graphs
JO - The electronic journal of combinatorics
PY - 2022
VL - 29
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/10561/
DO - 10.37236/10561
ID - 10_37236_10561
ER -
%0 Journal Article
%A Itai Benjamini
%A John Haslegrave
%T Degrees in link graphs of regular graphs
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/10561/
%R 10.37236/10561
%F 10_37236_10561
