Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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

Vertex-disjoint stars in graphs

100%

Ota K.

Discussiones Mathematicae Graph Theory

2001

tom 21

nr 2

179-185

In this paper, we give a sufficient condition for a graph to contain vertex-disjoint stars of a given size. It is proved that if the minimum degree of the graph is at least k+t-1 and the order is at least (t+1)k + O(t²), then the graph contains k vertex-disjoint copies of a star $K_{1,t}$. The condition on the minimum degree is sharp, and there is an example showing that the term O(t²) for the number of uncovered vertices is necessary in a sense.

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 Ota K.

1 Chen G.

1 Gould R.

1 Kawarabayashi K.-i.

1 Saito A.

1 Schiermeyer I.

1 2007

1 2001

Wyniki wyszukiwania

Vertex-disjoint stars in graphs

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