DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 21(1) (2001) 223-228
DOI: 10.7151/dmgt.1145

ON THE STABILITY FOR PANCYCLICITY

Ingo Schiermeyer

Fakultät für Mathematik und Informatik
Technische Universität Bergakademie Freiberg
D-09596 Freiberg, Germany
e-mail: schierme@math.tu-freiberg.de

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 dG(u)+dG(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.

2000 Mathematics Subject Classification: 05C35, 05C38, 05C45.

References

[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.
[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.
[3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan Press, 1976).
[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.
[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.

Received 15 November 2000
Revised 2 April 2001