کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651042 1632443 2007 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Critical and infinite directed graphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Critical and infinite directed graphs
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issues 19–20, 28 September 2007, Pages 2415–2428
نویسندگان
, ,