Article ID Journal Published Year Pages File Type
4651042 Discrete Mathematics 2007 14 Pages PDF
Abstract

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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,