| 总结: | 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.
<br>
We motivate these questions by posing a conjecture concerning expansion of link graphs in large bounded-degree graphs, together with a heuristic justification thereof.
|
|---|