A property P defined on all graphs of order n is said to be k-stable if for any graph of order n that does not satisfy P, the fact that uv is not an edge of G and that G + uv satisfies P implies $d_G(u) + d_G(v) < k$. Every property is (2n-3)-stable and every k-stable property is (k+1)-stable. We denote by s(P) the smallest integer k such that P is k-stable and call it the stability of P. This number usually depends on n and is at most 2n-3. A graph of order n is said to be pancyclic if it contains cycles of all lengths from 3 to n. We show that the stability s(P) for the graph property "G is pancyclic" satisfies max(⎡6n/5]⎤-5, n+t) ≤ s(P) ≤ max(⎡4n/3]⎤-2,n+t), where t = 2⎡(n+1)/2]⎤-(n+1).
We first show that if a 2-connected graph G of order n is such that for each two vertices u and v such that δ = d(u) and d(v) < n/2 the edge uv belongs to E(G), then G is hamiltonian. Next, by using this result, we prove that a graph G satysfying the above condition is either pancyclic or isomorphic to $K_{n/2,n/2}$.
For a graph G of order n we consider the unique partition of its vertex set V(G) = A ∪ B with A = {v ∈ V(G): d(v) ≥ n/2} and B = {v ∈ V(G):d(v) < n/2}. Imposing conditions on the vertices of the set B we obtain new sufficient conditions for hamiltonian and pancyclic graphs.
The well-known Chvátal-Erdős theorem states that if the stability number α of a graph G is not greater than its connectivity then G is hamiltonian. In 1974 Erdős showed that if, additionally, the order of the graph is sufficiently large with respect to α, then G is pancyclic. His proof is based on the properties of cycle-complete graph Ramsey numbers. In this paper we show that a similar result can be easily proved by applying only classical Ramsey numbers.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.