Degrees in link graphs of regular graphs

DOI10.37236/10561zbMATH Open1487.05054arXiv2106.15464OpenAlexW3174257859MaRDI QIDQ2138581FDOQ2138581

John Haslegrave, Itai Benjamini

Publication date: 12 May 2022

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 $G$ is $d$-regular and connected but not complete then some link graph of $G$ has minimum degree at most $lfloor2d/3floor-1$, and if $G$ is sufficiently large in terms of $d$ then some link graph has minimum degree at most $lfloord/2floor-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.

Full work available at URL: https://arxiv.org/abs/2106.15464

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On the Edge-Expansion of Graphs
• Extreme degrees in random subgraphs of regular graphs
• Graphs with constant link and small degree or order
• Lower connectivities of regular graphs with small diameter
• scientific article

zbMATH Keywords

connected \(d\)-regular graphsfinite regular graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07)

Cites Work

• Recurrence of distributional limits of finite planar graphs
• Processes on unimodular random networks
• Property (T) and Kazhdan constants for discrete groups
• Expanders are not hyperbolic
• Ergodic theory on stationary random graphs

Cited In (1)

• Title not available (Why is that?)

This page was built for publication: Degrees in link graphs of regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2138581)