Chvátal–Erdős Theorem: Old Theorem with New Aspects

DOI10.1007/978-3-540-89550-3_21zbMath1162.05331OpenAlexW1796505807MaRDI QIDQ5302754

Akira Saito

Publication date: 13 January 2009

Published in: Computational Geometry and Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-89550-3_21

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Related Items (6)

A Chvátal-Erdős condition for the existence of a cycle intersecting specified connected subgraphs ⋮ On Saito's conjecture and the Oberly-Sumner conjectures ⋮ Degree conditions for the existence of vertex-disjoint cycles and paths: a survey ⋮ An extension of the Win theorem: counting the number of maximum independent sets ⋮ An extension of the Chvátal-Erdős theorem: counting the number of maximum independent sets ⋮ A condition on Hamilton-connected line graphs

Cites Work

• Unnamed Item
• Pancyclism in Chvátal-Erdős' graphs
• On a \(k\)-tree containing specified leaves in a graph
• A note on distance-dominating cycles
• On a conjecture of Las Vergnas concerning certain spanning trees in graphs
• Spanning trees with bounded degrees
• A remark on two sufficient conditions for Hamilton cycles
• On the existence of disjoint cycles in a graph
• Cycles in graphs with prescribed stability number and connectivity
• Advances on the Hamiltonian problem -- a survey
• Cycles within specified distance from each vertex.
• Long cycles in triangle-free graphs with prescribed independence number and connectivity
• The Chvátal-Erdös condition for cycles in triangle-free graphs
• Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
• Pancyclic graphs. I
• A note on Hamiltonian circuits
• The independence number condition for the existence of a spanning f-tree
• Note on Hamilton Circuits
• Chvátal Erdős condition and 2-factors with a specyfied number of components
• Chvátal-Erdös condition and pancyclism
• Hamilton cycles in claw-free graphs
• Existence of Δλ-cycles and Δλ-paths
• Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
• Updating the hamiltonian problem—A survey
• Degree conditions for 2-factors
• A 2‐factor with two components of a graph satisfying the Chvátal‐Erdös condition

This page was built for publication: Chvátal–Erdős Theorem: Old Theorem with New Aspects