EUDML

Currently displaying 1 – 4 of 4

Order by Relevance | Title | Year of publication

2-factors in claw-free graphs

Guantao Chen; Jill R. Faudree; Ronald J. Gould; Akira Saito — 2000

Discussiones Mathematicae Graph Theory

We consider the question of the range of the number of cycles possible in a 2-factor of a 2-connected claw-free graph with sufficiently high minimum degree. (By claw-free we mean the graph has no induced $K_{1, 3}$ .) In particular, we show that for such a graph G of order n ≥ 51 with δ(G) ≥ (n-2)/3, G contains a 2-factor with exactly k cycles, for 1 ≤ k ≤ (n-24)/3. We also show that this result is sharp in the sense that if we lower δ(G), we cannot obtain the full range of values for k.

Chvátal-Erdös type theorems

Jill R. Faudree; Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson; Colton Magnant — 2010

Discussiones Mathematicae Graph Theory

The Chvátal-Erdös theorems imply that if G is a graph of order n ≥ 3 with κ(G) ≥ α(G), then G is hamiltonian, and if κ(G) > α(G), then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-k)/(k+1),...