A refinement of theorems on vertex-disjoint chorded cycles

DOI10.1007/S00373-016-1749-0MaRDI QIDQ2361086zbMATH OpenOpenAlexFDO

Authors Theodore Molla, Michael Santana, Elyse Yeager

Publication date 29 June 2017

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

chorded cyclesdisjoint cyclesminimum degreeOre-degree

Mathematics Subject Classification ID

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

Abstract: In 1963, Corr'adi and Hajnal settled a conjecture of ErdH{o}s by proving that, for all $kgeq1$, any graph $G$ with $|G|geq3k$ and minimum degree at least $2k$ contains $k$ vertex-disjoint cycles. In 2008, Finkel proved that for all $kgeq1$, any graph $G$ with $|G|geq4k$ and minimum degree at least $3k$ contains $k$ vertex-disjoint chorded cycles. Finkel's result was strengthened by Chiba, Fujita, Gao, and Li in 2010, who showed, among other results, that for all $kgeq1$, any graph $G$ with $|G|geq4k$ and minimum Ore-degree at least $6k-1$ contains $k$ vertex-disjoint cycles. We refine this result, characterizing the graphs $G$ with $|G|geq4k$ and minimum Ore-degree at least $6k-2$ that do not have $k$ disjoint chorded cycles.

Recommendations

• Disjoint chorded cycles in graphs with high Ore-degree
• Disjoint cycles and chorded cycles in a graph with given minimum degree
• Vertex-disjoint chorded cycles in a graph
• On the maximum number of disjoint chorded cycles in graphs.
• Disjoint chorded cycles in graphs

Cites work

• A note on neighborhood unions and independent cycles.
• Disjoint chorded cycles in graphs
• Independet cycles and chorded cycles in graphs
• Multiply chorded cycles
• Neighborhood unions and disjoint chorded cycles in graphs
• On a sharp degree sum condition for disjoint chorded cycles in graphs
• On independent doubly chorded cycles
• On the Corrádi-Hajnal theorem and a question of Dirac
• On the existence of disjoint cycles in a graph
• On the maximal number of independent circuits in a graph
• On the maximum number of independent cycles in a graph
• On the number of independent chorded cycles in a graph
• Sharpening an ore-type version of the Corrádi-Hajnal theorem
• Some Results Concerning the Structure of Graphs
• The \((2k-1)\)-connected multigraphs with at most \(k-1\) disjoint cycles

Cited in

(13)

• An extension of a theorem on cycles containing specified independent edges
• Sharpening an ore-type version of the Corrádi-Hajnal theorem
• Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
• Spanning cyclic subdivisions of vertex-disjoint cycles and chorded cycles in graphs
• Results and problems on chorded cycles: a survey
• Disjoint cycles and chorded cycles in a graph with given minimum degree
• Disjoint chorded cycles in graphs with high Ore-degree
• On the number of independent chorded cycles in a graph
• On the maximum number of disjoint chorded cycles in graphs.
• scientific article; zbMATH DE number 5016710 (Why is no real title available?)
• Strengthening Theorems of Dirac and Erdős on Disjoint Cycles
• Vertex-disjoint chorded cycles in a graph
• Sharp minimum degree conditions for disjoint doubly chorded cycles

This page was built for publication: A refinement of theorems on vertex-disjoint chorded cycles

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