On degree sum conditions for 2-factors with a prescribed number of cycles

DOI10.1016/J.DISC.2018.06.045zbMATH Open1393.05164arXiv1705.02819OpenAlexW2964041938MaRDI QIDQ1660281FDOQ1660281

Authors: Shuya Chiba 

Publication date: 15 August 2018

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

Abstract: For a vertex subset $X$ of a graph $G$, let $Delt{a}_t(X)$ be the maximum value of the degree sums of the subsets of $X$ of size $t$. In this paper, we prove the following result: Let $k$ be a positive integer, and let $G$ be an $m$-connected graph of order $nge5k-2$. If $Delt{a}_2(X)gen$ for every independent set $X$ of size $lceilm/kceil+1$ in $G$, then $G$ has a 2-factor with exactly $k$ cycles. This is a common generalization of the results obtained by Brandt et al. [Degree conditions for 2-factors, J. Graph Theory 24 (1997) 165-173] and Yamashita [On degree sum conditions for long cycles and cycles through specified vertices, Discrete Math. 308 (2008) 6584-6587], respectively.

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

Recommendations

• On the difference between Hamilton cycles and 2-factors with a prescribed number of cycles
• scientific article; zbMATH DE number 1926044
• Degree conditions for 2-factors
• Toughness, degrees and 2-factors
• A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs

zbMATH Keywords

Hamilton cyclesvertex-disjoint cycles2-factorsdegree sum conditions

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Connectivity (05C40)

Cites Work

• Graph theory
• Note on Hamilton Circuits
• A note on Hamiltonian circuits
• On the existence of disjoint cycles in a graph
• On the Corrádi-Hajnal theorem and a question of Dirac
• On degree sum conditions for long cycles and cycles through specified vertices
• Degree conditions for 2-factors
• An improvement of fraisse's sufficient condition for hamiltonian graphs
• Degree sum conditions and vertex-disjoint cycles in a graph
• Hamiltonicity for K_{1, r}‐free graphs
• Hamilton cycles in claw-free graphs
• A remark on two sufficient conditions for Hamilton cycles
• A 2‐factor with two components of a graph satisfying the Chvátal‐Erdös condition
• Chvátal Erdős condition and 2-factors with a specyfied number of components
• The existence of a 2-factor in a graph satisfying the local Chvátal-Erdős condition
• Degree conditions for the existence of vertex-disjoint cycles and paths: a survey

Cited In (4)

• Title not available (Why is that?)
• Disjoint cycles and \(2\)-factors with Fan-type condition in a graph
• Toughness, degrees and 2-factors
• On the difference between Hamilton cycles and 2-factors with a prescribed number of cycles

This page was built for publication: On degree sum conditions for 2-factors with a prescribed number of cycles

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