Domknięcie i stabilność Bondy'ego-Chvátala grafów zwykłych - idee, formalizacje, uzupełnienia
DOI:
https://doi.org/10.15678/krem.822Słowa kluczowe:
domknięcie Bondy'ego-Chvátala, stabilność Bondy'ego-Chvátala, własność grafów, grafy zwykłeAbstrakt
W artykule zaprezentowano wyniki badań związanych ze stabilnością wybranych własności grafów zwykłych. Przedstawiono genezę i definicję k-domknięcia oraz stabilności Bondy'ego-Chvátala, a następnie rezultaty dotyczące stabilności własności grafów zwykłych, dla których stabilność została dokładnie ustalona. Podano także przykłady prac, w których wykorzystano pojęcie domknięcia lub stabilności.Pobrania
Bibliografia
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
