pith. sign in

arxiv: 1905.00239 · v1 · pith:KKDT7Y6Wnew · submitted 2019-05-01 · 🧮 math.CO

An Ore-type condition for existence of two disjoint cycles

classification 🧮 math.CO
keywords conditiondegreecyclesdisjointcontainsel-zaharexistencefrac
0
0 comments X
read the original abstract

Let $n_{1}$ and $n_{2}$ be two integers with $n_{1},n_{2}\geq3$ and $G$ a graph of order $n=n_{1}+n_{2}$. As a generalization of Ore's degree condition for the existence of Hamilton cycle in $G$, El-Zahar proved that if $\delta(G)\geq \left\lceil\frac{n_{1}}{2}\right\rceil+\left\lceil\frac{n_{2}}{2}\right\rceil$ then $G$ contains two disjoint cycles of length $n_{1}$ and $n_{2}$. Recently, Yan et. al considered the problem by extending the degree condition to degree sum condition and proved that if $d(u)+d(v)\geq n+4$ for any pair of non-adjacent vertices $u$ and $v$ of $G$, then $G$ contains two disjoint cycles of length $n_{1}$ and $n_{2}$. They further asked whether the degree sum condition can be improved to $d(u)+d(v)\geq n+2$. In this paper, we give a positive answer to this question. Our result also generalizes El-Zahar's result when $n_{1}$ and $n_{2}$ are both odd.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.