کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651042 | 1632443 | 2007 | 14 صفحه PDF | دانلود رایگان |

Given a directed graph G=(V(G),A(G))G=(V(G),A(G)), a subset X of V(G)V(G) is an interval of G provided that for any a,b∈Xa,b∈X and x∈V(G)-Xx∈V(G)-X, (a,x)∈A(G)(a,x)∈A(G) if and only if (b,x)∈A(G)(b,x)∈A(G), and similarly for (x,a)(x,a) and (x,b)(x,b). For example, ∅∅, {x}{x}(x∈V(G))(x∈V(G)) and V(G)V(G) 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 x∈V(G)x∈V(G), G(V(G)-{x})G(V(G)-{x}) is decomposable and if there are x≠y∈V(G)x≠y∈V(G) such that G(V(G)-{x,y})G(V(G)-{x,y}) 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 x≠y∈V(G)x≠y∈V(G) such that G and G(V(G)-{x,y})G(V(G)-{x,y}) 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 V(G)V(G) such that |F|⩾2|F|⩾2 and G(V(G)-F)G(V(G)-F) is indecomposable, then there are x≠y∈V(G)x≠y∈V(G) such that G(V(G)-{x,y})G(V(G)-{x,y}) is indecomposable.
Journal: Discrete Mathematics - Volume 307, Issues 19–20, 28 September 2007, Pages 2415–2428