Two vertex-disjoint cycles in a graph (Q1906862)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Two vertex-disjoint cycles in a graph |
scientific article; zbMATH DE number 837844
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Two vertex-disjoint cycles in a graph |
scientific article; zbMATH DE number 837844 |
Statements
Two vertex-disjoint cycles in a graph (English)
0 references
13 February 1996
0 references
The author proves that any graph \(G\) of order \(n\geq 6\) and degree at least \(\lceil(n+ 1)/2\rceil\) contains two cycles---of lengths \(s\) and \(t\), when \(s+ t\leq n\) and \(s\geq 3\), \(t\geq 3\) unless \(s\), \(t\) and \(n\) are odd and \(G\) is isomorphic to \(K_{(n- 1)/2,(n- 1)/2}+ K_1\). Similarly, if \(n\geq 8\) is even, and the minimum degree is at least \(n/2\), then \(G\) contains two vertex-disjoint cycles with any given even lengths \(s\) and \(t\) provided that \(s+ t\leq n\), \(s\geq 4\), \(t\geq 4\).
0 references
vertex-disjoint cycles
0 references