Geodesic
On the stability for pancyclicity
Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 223-228

Voir la notice de l'article provenant de la source Library of Science

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).
Keywords: pancyclic graphs, stability 
@article{DMGT_2001_21_2_a6,
     author = {Schiermeyer, Ingo},
     title = {On the stability for pancyclicity},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {223--228},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2001},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a6/}
}
TY  - JOUR
AU  - Schiermeyer, Ingo
TI  - On the stability for pancyclicity
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2001
SP  - 223
EP  - 228
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a6/
LA  - en
ID  - DMGT_2001_21_2_a6
ER  - 
%0 Journal Article
%A Schiermeyer, Ingo
%T On the stability for pancyclicity
%J Discussiones Mathematicae. Graph Theory
%D 2001
%P 223-228
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a6/
%G en
%F DMGT_2001_21_2_a6
Schiermeyer, Ingo. On the stability for pancyclicity. Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 223-228. http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a6/