Critical and infinite directed graphs Original Research Article

Given a directed graph image, a subset X of image is an interval of G provided that for any image and image, image if and only if image, and similarly for image and image. For example, image, image image and image are intervals of G, called trivial intervals. A directed graph is indecomposable if all its intervals are trivial; otherwise, it is decomposable. An indecomposable directed graph G is then critical if for each image, image is decomposable and if there are image such that image is indecomposable. A generalization of the lexicographic sum is introduced to describe a process of construction of the critical and infinite directed graphs. It follows that for every critical and infinite directed graph G, there are image such that G and image are isomorphic. It is then deduced that if G is an indecomposable and infinite directed graph and if there is a finite subset F of image such that image and image is indecomposable, then there are image such that image is indecomposable.