Maximum Induced Forests of Product Graphs.

The forest number f(G) of a graph G is max { | S | : S ⊆ V (G) and G[S] contains no cycle } . In this paper, we investigate the forest number of several kinds of products of two graphs G and H, such as cartesian product G □ H , direct product G × H and lexicographic product G[H]. The sharp bounds are given for Cartesian product and direct product of two graphs. However, characterizing all graphs attaining these bounds is difficult. Among other things, it is shown that (1) for any connected nontrivial graph G of order n with α (G) = 2 , and any nontrivial forest H, f (G □ H) = α (G) f (H) + 1 if and only if G ≅ K n - e and H ∈ { P 3 , P 4 } , or δ (G) = n - 2 and H ≅ K 2 . (2) f (G × K 2) = m + 1 for any graph G of order m with δ (G) ≥ m 2 + 1 . (3) For two nonempty graphs G and H, f (G [ H ]) = α (G) f (H) . In addition, a number of related conjectures are proposed. [ABSTRACT FROM AUTHOR]