On Decycling Numbers Of Some Product Graphs

Let G = (V(G),E(G)) be a finite, simple, undirected graph. If S(?)V(G) and G-S is acyclic, then S is said to be a decycling set ofG. The decycling number of G, denoted byφ(G), is defined to be thecardinality of a minimum decycling set of G, i.e., the minimum number of vertices that must be removed in order to eliminate all the cycles in G.In this paper, we discuss the decycling numbers of some product graphs. In Chapter 1, we introduce some notions, notations and some known results related to the decycling problem.Chapter 2 discusses the decycling number of Cartesian product graphK_t□G. More specifically, the decycling numbers of K_t□T, K_t□C_n,K_t□K_n and K_t□K_m,n are determined, respectively.In Chapter 3, we study the decycling number of the cross product P_m×C_n of a path and a cycle. The main results are as follows:1. For an arbitrary path P_m and an arbitrary cycle C_n, a sharp lower bound of the decycling number of P_m×C_n is established.2. For some special path P_m and cycle C_n, the decycling numbers ofP_m×C_n are determined .