6-22吴文俊数学重点实验室组合图论系列讲座之一百零五【王维凡】

发布者:系统管理员发布时间:2017-06-15浏览次数:31

报告题目:The Surviving Rate of a Graph 
报告人:Wang Weifan 浙江师范大学
报告时间:6月22日10:00-11:00
地点:1518

摘要: Let G be a connected graph with n ≥ 2 vertices. Let k ≥ 1 be an integer. Supposethat a fire breaks out at a vertex v of G. A firefighter starts to protect vertices. Ateach time interval, the firefighter protects k vertices not yet on fire. At the end of eachtime interval, the fire spreads to all the unprotected vertices that have a neighbour onfire. Let snk(v) denote the maximum number of vertices in G that the firefighter cansave when a fire breaks out at vertex v. The k-surviving rate ρk(G) of G is defied tobe Pv∈Vsnk(v)/n2, which is the average proportion of saved vertices.In this talk, we give a chief survey on this direction and related problems. In particular,we consider the firefighter problems for some graphs such as trees, outerplanargraphs, planar graphs, d-degenerate graphs, etc