Seminar on Combinatorics

主講者: | 王維凡教授(浙江師範大學) |

講題: | The Surviving Rate of Planar Graphs |

時間: | 2012-03-16 (Fri.) 14:00 - 15:30 |

地點: | 數學所 722 研討室 (台大院區) |

Abstract: | Let G be a connected graph with $n\geq 2$ vertices. Let $k\ge 1$ be an integer. Suppose that a fire breaks out at a vertex v of G. A firefighter starts to protect vertices. At each time interval, the firefighter protects k-vertices not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let $sn_k(v)$ denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The k-surviving rate$\rho_k(G)$ of G is defined to be $\Sum_{v\in V(G)}sn_k(v)/n^2$, 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 special graphs such as trees, outerplanar graphs, planar graphs of large girth, d-degenerate graphs, general planar graphs, etc. |

|| Close window || |