On the maximum number of independent cycles in a graph (Q1301840)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1334685
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the maximum number of independent cycles in a graph |
scientific article; zbMATH DE number 1334685 |
Statements
On the maximum number of independent cycles in a graph (English)
0 references
8 May 2000
0 references
\textit{K. Corrádi} and \textit{A. Hajnal} [Acta Math. Acad. Sci. Hung. 14, 423-439 (1963.; Zbl 0118.19001)] proved that a graph of order at least \(3k\) with minimum degree \(\geq 2k\) contains \(k\) vertex-disjoint cycles. In 1989, \textit{D. Justesen} [Ann. Discrete Math. 41, 299-305 (1989; Zbl 0673.05065)] improved this theorem by relaxing the degree condition to \(d(x)+d(y) \geq 4k\) for every pair of non-adjacent vertices \(x\) and \(y\). This paper sharpens the result by reducing the requirement to \(d(x)+d(y) \geq 4k-1\).
0 references
vertex-disjoint cycles
0 references
0.8886354565620422
0 references
0.8729859590530396
0 references
0.870880663394928
0 references
