Primality, criticality and minimality problems in trees.

In a graph G = (V , E) , a module is a vertex subset M of V such that every vertex outside M is adjacent to all or none of M. For example, ∅ , { x } (x ∈ V) and V are modules of G , called trivial modules. A graph, all the modules of which are trivial, is prime; otherwise, it is decomposable. A vertex x of a prime graph G is critical if G − x is decomposable. Moreover, a prime graph with k noncritical vertices is called (− k) -critical graph. A prime graph G is k -minimal if there is some k -vertex set X of vertices such that there is no proper induced subgraph of G containing X is prime. From this perspective, Boudabbous proposes to find the (− k) -critical graphs and k -minimal graphs for some integer k even in a particular case of graphs. This research paper attempts to answer Boudabbous's question. First, we describe the (− k) -critical tree. As a corollary, we determine the number of nonisomorphic (− k) -critical tree with n vertices where k ∈ { 1 , 2 , ⌊ n 2 ⌋ }. Second, we provide a complete characterization of the k -minimal tree. As a corollary, we determine the number of nonisomorphic k -minimal tree with n vertices where k ≤ 3. [ABSTRACT FROM AUTHOR]