Degrees in link graphs of regular graphs
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...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Electronic Journal of Combinatorics
2022
|
| _version_ | 1797107284905558016 |
|---|---|
| author | Benjamini, I Haslegrave, J |
| author_facet | Benjamini, I Haslegrave, J |
| author_sort | Benjamini, I |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T07:13:55Z |
| format | Journal article |
| id | oxford-uuid:7a7d6b50-3b06-4b5b-b324-4378e0a6805e |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:13:55Z |
| publishDate | 2022 |
| publisher | Electronic Journal of Combinatorics |
| record_format | dspace |
| spelling | oxford-uuid:7a7d6b50-3b06-4b5b-b324-4378e0a6805e2022-07-19T17:16:19ZDegrees in link graphs of regular graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7a7d6b50-3b06-4b5b-b324-4378e0a6805eEnglishSymplectic ElementsElectronic Journal of Combinatorics2022Benjamini, IHaslegrave, JWe 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. |
| spellingShingle | Benjamini, I Haslegrave, J Degrees in link graphs of regular graphs |
| title | Degrees in link graphs of regular graphs |
| title_full | Degrees in link graphs of regular graphs |
| title_fullStr | Degrees in link graphs of regular graphs |
| title_full_unstemmed | Degrees in link graphs of regular graphs |
| title_short | Degrees in link graphs of regular graphs |
| title_sort | degrees in link graphs of regular graphs |
| work_keys_str_mv | AT benjaminii degreesinlinkgraphsofregulargraphs AT haslegravej degreesinlinkgraphsofregulargraphs |