Domknięcie i stabilność Bondy'ego-Chvátala grafów zwykłych - idee, formalizacje, uzupełnienia

• Autorzy: Paweł Najman

Warianty tytułu

Bondy-Chvátal's Closure and Stability for Simple Graphs - Ideas, Formalisation and Complement

• Języki publikacji: PL

Abstrakty

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.(abstrakt oryginalny)

EN

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.(original abstract)

Słowa kluczowe

PL

Grafy; Teoria grafów

EN

Graphs; Graph theory

• Czasopismo: Zeszyty Naukowe / Uniwersytet Ekonomiczny w Krakowie
• Rocznik: 2013
• Numer: nr 904 Metody analizy danych
• Strony: 53--69

Twórcy

autor

Paweł Najman

• Uniwersytet Ekonomiczny w Krakowie

Bibliografia

• Amar D. et al. [1995], Biclosure and Stability in Balanced Bipartite Graph, "Journal of Graph Theory", vol. 20, nr 4.
• Bauer D. et al. [1989], A Generalization of a Result of Häggkvist and Nicoghossian, "Journal of Combinatorial Theory B", vol. 47, nr 2.
• 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.
• Bondy J.A., Chvátal V. [1976], A Method in Graph Theory, "Discrete Mathematics", vol. 15, nr 2.
• 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.
• Broersma H.J., Ryjáček Z., Schiermeyer I. [2000], Closure Concepts: A Survey, "Graphs and Combinatorics", vol. 16, nr 1.
• Clark L., Entringer R.C., Jackson D.E. [1980], Minimum Graphs with Complete k-closure, "Discrete Mathematics", vol. 30, nr 2.
• Faudree R. et al. [1993], The Complete Closure of a Graph, "Journal of Graph Theory", vol. 17, nr 4.
• Fan Geng-Hua [1984], New Sufficient Conditions for Cycles in Graphs, "Journal of Combinatorial Theory B", vol. 37, nr 3.
• Gurgel M.A., Wakabayashi Y. [1986], On k-leaf-connected Graphs, "Journal of Combinatorial Theory B", vol. 41, nr 1.
• 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.
• Hendry G.R.T. [1990], Extending Cycles in Graphs, "Discrete Mathematics", vol. 85, nr 1.
• Hendry G.R.T. [1991], Extending Cycles in Bipartite Graphs, "Journal of Combinatorial Theory B", vol. 51, nr 2.
• Khuller S. [1989], On Computing Graph Closures, "Information Processing Letters", vol. 31, nr 5.
• Monti A. [1996], On the Computational Complexity of Graph Closures, "Information Processing Letters", vol. 57, nr 6.
• 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.
• Randerath B. et al. [2002], Vertex Pancyclic Graphs, "Discrete Applied Mathematics", vol. 120, nr 1-3.
• Szwarcfiter J.L. [1987], A Note on the Computation of the k-closure of a Graph, "Information Processing Letters", vol. 24, nr 4.
• 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.