Degrees in link graphs of regular graphs

DOI10.37236/10561MaRDI QIDQ2138581zbMATH OpenOpenAlexFDO

Authors Itai Benjamini, John Haslegrave

Publication date 12 May 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

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

zbMATH Keywords

connected \(d\)-regular graphsfinite regular graph

Mathematics Subject Classification ID

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

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.

Review text

Summary: 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.

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 DE number 3869382

Cites work

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

Cited in

(1)

• scientific article; zbMATH DE number 3972885 (Why is no real title available?)

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)