Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Vertex-disjoint copies of K¯₄

100%

Kawarabayashi K.-i.

Discussiones Mathematicae Graph Theory

2004

tom 24

nr 2

249-262

Let G be a graph of order n. Let K¯ₗ be the graph obtained from Kₗ by removing one edge. In this paper, we propose the following conjecture: Let G be a graph of order n ≥ lk with δ(G) ≥ (n-k+1)(l-3)/(l-2)+k-1. Then G has k vertex-disjoint K¯ₗ. This conjecture is motivated by Hajnal and Szemerédi's [6] famous theorem. In this paper, we verify this conjecture for l=4.

The Chvátal-Erdős condition and 2-factors with a specified number of components

39%

Chen G., Gould R., Kawarabayashi K.-i., Ota K., Saito A., Schiermeyer I.

Discussiones Mathematicae Graph Theory

2007

tom 27

nr 3

401-407

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.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Kawarabayashi K.-i.

1 Chen G.

1 Gould R.

1 Ota K.

1 Saito A.

1 Schiermeyer I.

1 2007

1 2004

Wyniki wyszukiwania

Vertex-disjoint copies of K¯₄

The Chvátal-Erdős condition and 2-factors with a specified number of components