Connected Decycling Number of P_m× P_n*

Introduction. Let be a graph, where represents the vertex set and edge set of graph respectively. In this paper, we allowed only connected simple graphs and for the standard terminologies and notations of graph theory, we simply referred to Wilson at el. (1996). Furthermore, the minimum number of edges whose removal eliminate all cycles in a given graph has been known as cycle rank and this parameter has a simple expression . Where is the number of components in and on the other hand, the corresponding problem to eliminate all cycles by mean of deletion of vertices goes back at least to the work of Kirchhoff at el. (1847) on spanning tree. In addition, this is not a simple problem it is quite difficult for some simple graphs such as planner graphs, bipartite graph etc. Suppose that be an independent set of vertices in , and is a tree, then is said to be the connected decycling set (or CDS in short) of . The maximum size of connected decycling set of is called the connected decycling number (or CDN in short) and it is denoted by A connected decycling set of this size is called . To determine the CDN of graph is equivalent to finding the maximum order of an induce tree, the sum of two numbers equals to the order of graph where is the order of the largest induced tree. The connected decycling set problem has various applications in area such as combinatorial circuit design by Focardi at el. (2000), an operating system task, that is, consider the typical operating system task of allocation resources to processors while preventing deadlock this task can carried out by using vertex-removing operation on dependence graph. Suppose that a vertex represents a processor and each edge the request of processor for a resource already allocated to processor . If the graph contains a cycle, then a deadlock has occurred and therefore processors will indefinitely wait for the requested resources. This may be solved by moving into a waiting queue the minimum number of processors so that the new dependence graph becomes deadlock free Wang at el. (1985), this technique may also be very useful for the artificial intelligence to the constraint satisfaction problem and to Bayesian inference Festa at el. (1999). Ofcouse CDN has very nice contribution in Chemical graph theory, for example to breakdown the molecular structures of compounds, and make it cycle free. Such as the enumeration problems in which molecules are regarded as being constructed from larger building blocks, than individual atoms. Those molecules constructed from benzene rings (called “benzenoid condensed polycyclic system” or “polyhexes”) provide a wealth of combinatorial problems. Again, the connected acyclic member of this set (which have been said “tree-like polyhexes”) are comparatively easy to enumerate Robald at el. (1996). Erdӧs at el. (1986) gives an important concept about the maximum induced tree. They explicitly investigated the relationship of maximum size of a subset of vertices of graph that induces a tree to other parameters associated with by Festa at el. (1999). Therefore, many graph theorist paying their attention on the decycling number of graphs (or, minimum feedback vertex) to obtain an induced forest, this problem has been well investigated ( Bau & Beinke 2002; Beinke & Vandell 1997; Caragainnnis at el 2002; Festa at el 1999; Focardi at el. 2000; Madelain & Stewwart 2008 and Ren at el. 2017). As a matter of this fact, the program of solution in this paper, is to compute the connected decycling set of size , in such a way that the resultant graph be a maximum induced tree (i.e. ). Now, we have to carefully exercise on the vertex removal operation on the basses of two strict conditions. (1) All the removal vertices in essentially independent. (2) The deletion of an independent vertices cannot isolate any vertex in . In this paper, the removal vertices and induced tree are exemplified in figures by black dots “•” and red bold bars respectively. This paper is broken up into two three sections. The first of which served as basic terminologies and notations of graph theory, the second part demonstrate the main result and discussion and third part present conclusion of paper. Results and Discussion As promised in the introduction we compute the connected decycling number of , for . The classical labeling for the grids of path is the graph with vertex set and edge set respectfully . The margin number of connected decycling set can be define as , where are, respectively, the number of components of and the number of incident edges on . In fact, the margin number is very useful to measure a gap between the connected decycling set in and Theorem 1. be a 2- dimensional grids graph with maximum degree and be a connected decycling set for .Suppose that is a fixed natural number with Where, , Then . . Proof (i). Let e a connected decycling set of . Then has vertices, components and edges. If is removed from , then, edges are also removed. Therefore, we must have { . . . Proved. Proof (ii). Let be a connected decycling set of and theorem 1. (i) implies that . . . Corollary 2. Let be a 2-dimensional grids graph with maximum degree , which has such that each vertex of this set has degree and . Then , represents the degree Corollary 3. If a graph contains the connected decycling set of order . Then, . Proof. Theorem.1 (ii), implies that, if Then . . . . . Theorem 4. If Proof. To show, by the definition of cycle rank . And corollary 2 implies that . Let be the connected decycling set of , and follows theorem 1. (b), we get . Lemma 5. Let with If is connected decycling set of , then contains at least one vertex of degree 3 or 2 and this vertex necessarily nonadjacent with interior independent vertices of . Proof. Suppose that . Then the connected subgraph induced by first two columns contains each of them have a vertex in . Moreover, an independent set of interior vertices in has at least vertices in , and the vertices are definitely independent with the boundary vertex (see Fig.3 and Fig.5a). In order to find optimal result, we have to proof all subcases of grids graph. For this purpose, we need the following lemm