The forest number of (n,m)-Graphs

Abstract

Let G = (V,E) be a graph and F ⊆ V. Then F is called an induced forest of G if G[F] is acyclic. The forest number, denoted by f(G), of G is defined by f(G) := max {|F| : F is an induced forest of G}. We proved that if G runs over the set of all graphs of order n and size m, then the values f(G) completely cover a line segment [x,y] of positive integers. Let ς(n,m) be the set of all graphs of order n and size m and Cς(n, m) be the subset of consisting of all connected graphs. We are able to obtain the extremal results for the forest number in the class ς(n, m) and Cς(n, m). © 2008 Springer Berlin Heidelberg.