Minimum degree of 3-graphs without long linear paths

DOI10.1016/J.DISC.2020.111949zbMATH Open1443.05135OpenAlexW3026569955MaRDI QIDQ776262FDOQ776262

Authors Yue Ma, Jun Gao, Xinmin Hou 

Publication date 8 July 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

minimum degreehypergraphlinear path

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Paths and cycles (05C38) Hypergraphs (05C65)

Abstract: A well known theorem in graph theory states that every graph $G$ on $n$ vertices and minimum degree at least $d$ contains a path of length at least $d$, and if $G$ is connected and $nge2d+1$ then $G$ contains a path of length at least $2d$ (Dirac, 1952). In this article, we give an extension of Dirac's result to hypergraphs. We determine asymptotic lower bounds of the minimum degrees of 3-graphs to guarantee linear paths of specific lengths, and the lower bounds are tight up to a constant.

Recommendations

• 3-minimal triangle-free graphs
• Long cycles in graphs with no subgraphs of minimal degree 3
• Minimally 3-connected graphs
• Minimal vertex degree sum of a 3-path in plane maps
• Triangle-Free Graphs with High Minimal Degrees
• A note on minimally 3-connected graphs
• Minimum 3-geodetically connected graphs
• Graphs without proper subgraphs of minimum degree 3 and short cycles
• On 3-connected graphs of path-width at most three
• Graphs of diameter 3 with the minimum number of edges

Cites work

• An Erdős-Gallai type theorem for uniform hypergraphs
• Connected graphs without long paths
• Exact solution of the hypergraph Turán problem for \(k\)-uniform linear paths
• Hypergraph extensions of the Erdős-Gallai theorem
• On maximal paths and circuits of graphs
• Path Ramsey numbers in multicolorings
• Some Theorems on Abstract Graphs
• Tight cycles and regular slices in dense hypergraphs
• Turán numbers for forests of paths in hypergraphs
• Turán problems and shadows. I: Paths and cycles

Cited in

(2)

• Crowns in linear \(3\)-graphs of minimum degree \(4\)
• Berge cycles in non-uniform hypergraphs

This page was built for publication: Minimum degree of 3-graphs without long linear paths

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