Description of the Triangle-free Prime Graphs Having at Most Two Non-Critical Vertices
Imed Boudabbous and Walid Marweni
In a graph G = (V, E), a module is a vertex subset M 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. We generalize this definition. A prime graph G = (V, E) is X-critical, where X is a subset of V, if for each x ∈ X, x is a critical vertex. Moreover, G is (−k)-critical, where 0 ≤ k ≤ |V|, if G is (V\X)-critical for some subset X of V such that |X| = k. In 1993, J.H. Schmerl and W.T. Trotter characterized the V-critical graphs, called critical graphs with vertex set V. Recently, H. Belkhechine, I. Boudabbous and M.B. Elayech characterized the (−1)-critical graphs. In this paper, we characterize the (−k)-critical graphs within the family of triangle-free graphs where k ≤ 2.
Keywords: Graphs, prime, module, critical vertex, partially critical