Minimum degree of 3-graphs without long linear paths

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

Authors: Yue Ma, Jun Gao, Xinmin Hou 

Publication date: 8 July 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

minimum degreehypergraphlinear path

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

• 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)