- Tytuł:
- The Chvátal-Erdős condition and 2-factors with a specified number of components
- Autorzy:
-
Chen, Guantao
Gould, Ronald
Kawarabayashi, Ken-ichi
Ota, Katsuhiro
Saito, Akira
Schiermeyer, Ingo - Powiązania:
- https://bibliotekanauki.pl/articles/743407.pdf
- Data publikacji:
- 2007
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
Chvátal-Erdös condition
2-factor
hamiltonian cycle
Ramsey number - Opis:
- Let G be a 2-connected graph of order n satisfying α(G) = a ≤ κ(G), where α(G) and κ(G) are the independence number and the connectivity of G, respectively, and let r(m,n) denote the Ramsey number. The well-known Chvátal-Erdös Theorem states that G has a hamiltonian cycle. In this paper, we extend this theorem, and prove that G has a 2-factor with a specified number of components if n is sufficiently large. More precisely, we prove that (1) if n ≥ k·r(a+4, a+1), then G has a 2-factor with k components, and (2) if n ≥ r(2a+3, a+1)+3(k-1), then G has a 2-factor with k components such that all components but one have order three.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2007, 27, 3; 401-407
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki