Bondy-Chvátal's Closure and Stability for Simple Graphs - Ideas, Formalisation and Complement
DOI:
https://doi.org/10.15678/krem.822Keywords:
Bondy-Chvátal closure, Bondy-Chvátal's stability, graph property, simple graphsAbstract
The paper looks at several results from research on the stability of different graph properties. Definitions of Bondy-Chvátal's closure and stability for simple graphs are first presented, followed by an overview of basic facts on the stability of selected simple graph properties, for which stability has been established exactly. Proofs for theorems concerning a new example are included. Papers in which closure operation or stability of graph properties have been applied are also presented.
Downloads
References
Amar D. et al. [1995], Biclosure and Stability in Balanced Bipartite Graph, „Journal of Graph Theory", vol. 20, nr 4. DOI: https://doi.org/10.1002/jgt.3190200414
Bauer D. et al. [1989], A Generalization of a Result of Häggkvist and Nicoghossian, „Journal of Combinatorial Theory B", vol. 47, nr 2. DOI: https://doi.org/10.1016/0095-8956(89)90023-3
Benhocine A., Wojda A. P. [1987], The Geng-Hua Fan Conditions for Pancyclic or Hamilton-connected Graphs, „Journal of Combinatorial Theory B", vol. 42, nr 2. DOI: https://doi.org/10.1016/0095-8956(87)90038-4
Bondy J.A., Chvátal V. [1976], A Method in Graph Theory, „Discrete Mathematics", vol. 15, nr 2. DOI: https://doi.org/10.1016/0012-365X(76)90078-9
Bondy J.A., Murthy U.S.R. [1976], Graph Theory with Applications, American Elsevier, New York.
Brandt S., Veldman H.J. [1997], Degree Sums for Edges and Cycle Lengths in Graphs, „Journal of Graph Theory", vol. 25, nr 4. DOI: https://doi.org/10.1002/(SICI)1097-0118(199708)25:4<253::AID-JGT2>3.0.CO;2-J
Broersma H.J., Ryjáček Z., Schiermeyer I. [2000], Closure Concepts: A Survey, „Graphs and Combinatorics", vol. 16, nr 1. DOI: https://doi.org/10.1007/s003730050002
Clark L., Entringer R.C., Jackson D.E. [1980], Minimum Graphs with Complete k-closure, „Discrete Mathematics", vol. 30, nr 2. DOI: https://doi.org/10.1016/0012-365X(80)90110-7
Faudree R. et al. [1993], The Complete Closure of a Graph, „Journal of Graph Theory", vol. 17, nr 4. DOI: https://doi.org/10.1002/jgt.3190170406
Fan Geng-Hua [1984], New Sufficient Conditions for Cycles in Graphs, „Journal of Combinatorial Theory B", vol. 37, nr 3. DOI: https://doi.org/10.1016/0095-8956(84)90054-6
Gurgel M.A., Wakabayashi Y. [1986], On k-leaf-connected Graphs, „Journal of Combinatorial Theory B", vol. 41, nr 1. DOI: https://doi.org/10.1016/0095-8956(86)90023-7
Harary F. [1969], Graph Theory, Addison-Wesley, Reading.
Hasratian A.S., Khachatrian N.K. [1991], Stable Properties of Graphs, „Discrete Mathematics", vol. 90, nr 2. DOI: https://doi.org/10.1016/0012-365X(91)90352-3
Hendry G.R.T. [1990], Extending Cycles in Graphs, „Discrete Mathematics", vol. 85, nr 1. DOI: https://doi.org/10.1016/0012-365X(90)90163-C
Hendry G.R.T. [1991], Extending Cycles in Bipartite Graphs, „Journal of Combinatorial Theory B", vol. 51, nr 2. DOI: https://doi.org/10.1016/0095-8956(91)90044-K
Khuller S. [1989], On Computing Graph Closures, „Information Processing Letters", vol. 31, nr 5. DOI: https://doi.org/10.1016/0020-0190(89)90082-3
Monti A. [1996], On the Computational Complexity of Graph Closures, „Information Processing Letters", vol. 57, nr 6. DOI: https://doi.org/10.1016/0020-0190(96)00027-0
Najman P. [2005], Stabilność Bondy'ego-Chvátala, praca magisterska, AGH, Wydział Matematyki Stosowanej, Kraków.
Ore O. [1960], Note on Hamilton Circuits, „American Mathematical Monthly", vol. 67, nr 1. DOI: https://doi.org/10.2307/2308928
Randerath B. et al. [2002], Vertex Pancyclic Graphs, „Discrete Applied Mathematics", vol. 120, nr 1-3. DOI: https://doi.org/10.1016/S0166-218X(01)00292-X
Szwarcfiter J.L. [1987], A Note on the Computation of the k-closure of a Graph, „Information Processing Letters", vol. 24, nr 4. DOI: https://doi.org/10.1016/0020-0190(87)90148-7
Veldman H.J. [1990], Short Proofs of Some Fan-type Results, „Ars Combinatoria", nr 29.
Zhu Y.-J., Tian F., Deng X.-T. [1991], More Powerful Closure Operations on Graphs, „Discrete Mathematics", vol. 87, nr 2. DOI: https://doi.org/10.1016/0012-365X(91)90049-8
