On the stability for pancyclicity
Discussiones Mathematicae Graph Theory (2001)
- Volume: 21, Issue: 2, page 223-228
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topIngo Schiermeyer. "On the stability for pancyclicity." Discussiones Mathematicae Graph Theory 21.2 (2001): 223-228. <http://eudml.org/doc/270367>.
@article{IngoSchiermeyer2001,
abstract = {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).},
author = {Ingo Schiermeyer},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {pancyclic graphs; stability; stable property},
language = {eng},
number = {2},
pages = {223-228},
title = {On the stability for pancyclicity},
url = {http://eudml.org/doc/270367},
volume = {21},
year = {2001},
}
TY - JOUR
AU - Ingo Schiermeyer
TI - On the stability for pancyclicity
JO - Discussiones Mathematicae Graph Theory
PY - 2001
VL - 21
IS - 2
SP - 223
EP - 228
AB - 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).
LA - eng
KW - pancyclic graphs; stability; stable property
UR - http://eudml.org/doc/270367
ER -
References
top- [1] J.A. Bondy, Pancyclic graphs, in: R.C. Mullin, K.B. Reid, D.P. Roselle and R.S.D. Thomas, eds, Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium III (1971) 167-172. Zbl0291.05109
- [2] J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111-135, doi: 10.1016/0012-365X(76)90078-9. Zbl0331.05138
- [3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan Press, 1976). Zbl1226.05083
- [4] R. Faudree, O. Favaron, E. Flandrin and H. Li, Pancyclism and small cycles in graphs, Discuss. Math. Graph Theory 16 (1996) 27-40, doi: 10.7151/dmgt.1021. Zbl0879.05042
- [5] U. Schelten and I. Schiermeyer, Small cycles in Hamiltonian graphs, Discrete Applied Math. 79 (1997) 201-211, doi: 10.1016/S0166-218X(97)00043-7.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.