Les Graphes \((-1)\)-critiques

Abstract

Given a (directed) graph \(G = (V, A)\), a subset \(X\) of \(V\) is an interval of \(G\) provided that for any \(a, b \in X\) and \(x \in V – X\), \((a, x) \in A\) if and only if \((b, x) \in A\) and \((x, a) \in A\)if and only if \((x, b) \in A\). For example, \(\emptyset\), \(\{x\}\) (\(z \in V\)), and \(V\) are intervals of \(G\), called trivial intervals. A graph, all of whose intervals are trivial, is indecomposable; otherwise, it is decomposable. A vertex \(x\) of an indecomposable graph is critical if \(G – x\) is decomposable. In 1998, J.H. Schmerl and W.T. Trotter characterized the indecomposable graphs, all of whose vertices are critical, called critical graphs. In this article, we characterize the indecomposable graphs that admit a single non-critical vertex, which we term (-1)-critical graphs, answering a question posed by Y. Boudabbous and P. Ille in a recent article studying critical vertices in indecomposable graphs.