Als monotone Grapheigenschaft oder monotone Grapheneigenschaft bezeichnet man in der Graphentheorie eine Eigenschaft von Graphen, die für jeden Teilgraphen eines Graphen gilt, sobald der Graph selbst diese Eigenschaft hat.
Beispiele monotoner Eigenschaften Planarität Bipartitheit Dreiecksfreiheit
Eigenschaften Nach dem Satz von Bollobás besitzt jede monotone Grapheneigenschaft eine Schwellenfunktion.
Literatur Béla Bollobás: Hereditary and Monotone Properties of Graphs. doi:10.1007/978-3-642-60406-5_7 Ehud Friedgut, Gil Kalai: Every monotone graph property has a sharp threshold Noga Alon, Asaf Shapira: Every monotone graph property is testable B. Bollobás, A. G. Thomason: Threshold functions. In: Combinatorica. Band 7, Nr. 1, 1. März 1987, , S. 35–38, doi:10.1007/BF02579198
Einzelnachweise
Kategorie:Graphentheorie