×

zbMATH — the first resource for mathematics

Decycling graphs. (English) Zbl 0870.05033
The decycling number of a graph is introduced as the minimum number of vertices that must be removed in order to eliminate all cycles. This is equivalent to finding the maximum order subgraph that is an induced forest. Some general results are proved, and then some specific ones about grids and hypercubes.

MSC:
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI