Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
From MaRDI portal
Publication:2277468
\textit{V. Chvátal} and \textit{P. Erdős} [Discrete Math. 2, 111-113 (1972; Zbl 0233.05123)] proved that a graph is hamiltonian if its independence number is not more than its connectivity, i.e., \(\alpha\leq k(\geq 2)\). The authors survey the extensive literature that has grown around this theorem during the past twenty years. Their survey, though restricted to results and conjectures that involve both independence number and connectivity, covers more than fifty such instances. These involve systems of disjoint paths, path coverings, cycle coverings, hamiltonicity, and pancyclicity in both graphs and digraphs.
Recommendations
Cites work
- A Chvátal-Erdős condition for (1,1)-factors in digraphs
- A Chvátal-Erdős condition for (t,t)-factors in digraphs using given arcs
- A Chvátal-Erdős condition for Hamilton cycles in digraphs
- A new sufficient condition for hamiltonian graphs
- A note on Hamiltonian circuits
- A remark on Hamiltonian cycles
- An Ore-type condition implying a digraph to be pancyclic
- Circuits through specified edges
- Diconnected Orientations and a Conjecture of Las Vergnas
- Every finite strongly connected digraph of stability 2 has a Hamiltonian path
- Existence of Dlambda-cycles and Dlambda-paths
- scientific article; zbMATH DE number 3150485 (Why is no real title available?)
- scientific article; zbMATH DE number 3165195 (Why is no real title available?)
- scientific article; zbMATH DE number 3841894 (Why is no real title available?)
- scientific article; zbMATH DE number 3869359 (Why is no real title available?)
- scientific article; zbMATH DE number 4160763 (Why is no real title available?)
- scientific article; zbMATH DE number 3908470 (Why is no real title available?)
- scientific article; zbMATH DE number 3910427 (Why is no real title available?)
- scientific article; zbMATH DE number 4066925 (Why is no real title available?)
- scientific article; zbMATH DE number 3506739 (Why is no real title available?)
- scientific article; zbMATH DE number 3630799 (Why is no real title available?)
- scientific article; zbMATH DE number 3893240 (Why is no real title available?)
- scientific article; zbMATH DE number 3353327 (Why is no real title available?)
- Long Cycles in Digraphs
- Longest Cycles in 2-Connected Graphs with Prescribed Maximum Degree
- On a conjecture of Bondy
- Structure Des Graphes De Connexite k ≥ 2 Et De Stabilite α = k + 2
- The Chvátal-Erdős condition and pancyclic line-graphs
- The Theory of Round Robin Tournaments
- Une condition suffisante d'existence d'un circuit Hamiltonien dans un graphe oriente
- Über Hamiltonsche Kreise und unabhängige Ecken in Graphen
Cited in
(39)- A Chvátal-Erdős condition for (1,1)-factors in digraphs
- A Chvátal-Erdős condition for Hamilton cycles in digraphs
- The Chvátal-Erdős condition and pancyclic line-graphs
- Hamiltonian properties and the bipartite independence number
- Pancyclic BIBD block-intersection graphs
- A note on pancyclism of highly connected graphs
- A short proof of the Chen-Manalastas theorem
- The Chvátal-Erdös condition for cycles in triangle-free graphs
- An extension of the Win theorem: counting the number of maximum independent sets
- Graph methods for solving the unconstrained and constrained optimal assignment problem for locomotives on a single-line railway section
- A Chvátal-Erdős condition for the existence of a cycle intersecting specified connected subgraphs
- An extension of the Chvátal-Erdős theorem: counting the number of maximum independent sets
- Berge's conjecture on directed path partitions -- a survey
- Hamilton-connected, vertex-pancyclic and bipartite holes
- On the Thomassen's conjecture
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Chvátal-Erdös condition and pancyclism
- Hamiltonicity, independence number, and pancyclicity
- A survey on Hamilton cycles in directed graphs
- A 2‐factor with two components of a graph satisfying the Chvátal‐Erdös condition
- Star subdivisions and connected even factors in the square of a graph
- Cycles of many lengths in Hamiltonian graphs
- Chvátal–Erdős Theorem: Old Theorem with New Aspects
- Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
- Antidirected Hamiltonian paths and cycles of digraphs with \(\alpha_2\)-stable number 2
- Chvátal-Erdős condition for pancyclicity
- Trails, paths and cycles of digraphs with _2-stable number 2
- A generalization of the Chvátal-Erdős theorem
- A generalization of Bondy's pancyclicity theorem
- Antidirected spanning trail of digraphs with _2-stable number 3
- Chvátal-Erdős condition for pancyclicity (extended abstract)
- A generalization of Bondy's pancyclicity theorem (extended abstract)
- Berge pancyclic hypergraphs
- On the pancyclicity of 2-connected \([5, 3]\)-graphs
- Pancyclicity of Hamiltonian graphs
- A Chvátal-Erdős condition for (t,t)-factors in digraphs using given arcs
- Paths partition with prescribed beginnings in digraphs: A Chvátal-Erdős condition approach
- Pancyclicity of Hamiltonian and highly connected graphs
- The Chvàtal-Erdős condition for supereulerian graphs and the Hamiltonian index
This page was built for publication: Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277468)
