Journal article

### 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 $\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 ...

Publication status:
Published
Peer review status:
Peer reviewed

### Access Document

Files:
• (Version of record, 208.9KB)
Publisher copy:
10.37236/10561

### Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Role:
Author
Publisher:
Electronic Journal of Combinatorics Publisher's website
Journal:
Electronic Journal of Combinatorics Journal website
Volume:
29
Issue:
2
Article number:
P2.23
Publication date:
2022-05-06
Acceptance date:
2022-03-02
DOI:
EISSN:
1077-8926
Language:
English
Keywords:
Pubs id:
1249581
Local pid:
pubs:1249581
Deposit date:
2022-04-06