zbMATH — the first resource for mathematics

The decycling number of graphs. (English) Zbl 0994.05079
Summary: For a graph \(G\) and \(S\subset V(G)\), if \(G-S\) is acyclic, then \(S\) is said to be a decycling set of \(G\). The size of a smallest decycling set of \(G\) is called the decycling number of \(G\). The purpose of this paper is to provide a review of recent results and open problems on this parameter. Results to be reviewed include recent work on decycling numbers of cubes, grids and snakes and bounds on the decycling number of cubic graphs, and expected bounds on the decycling numbers of random regular graphs. A structural description of graphs with a fixed decycling number based on connectivity is also presented.

05C35 Extremal problems in graph theory
05C40 Connectivity
05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX Cite