Currently displaying 1 – 3 of 3

Showing per page

Order by Relevance | Title | Year of publication

Vertex-disjoint stars in graphs

Katsuhiro Ota — 2001

Discussiones Mathematicae Graph Theory

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

Guantao ChenRonald J. GouldKen-ichi KawarabayashiKatsuhiro OtaAkira SaitoIngo Schiermeyer — 2007

Discussiones Mathematicae Graph Theory

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,...

Page 1

Download Results (CSV)