کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4653740 1632782 2014 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Indecomposability graph and indecomposability recognition
ترجمه فارسی عنوان
نمودار عدم انطباق و تشخیص غیر قابل انعطاف
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Given a digraph G=(V,A), a subset X of V is an interval of G if for a,b∈X and v∈V∖X, (a,v)∈A if and only if (b,v)∈A, and similarly for (v,a) and (v,b). For instance, 0̸, V and {v}, v∈V, are intervals of G called trivial. A digraph is indecomposable if all its intervals are trivial. Let G=(V,A) be a digraph. Given v∈V, v is an indecomposability vertex of G if G[V∖{v}] is indecomposable. The indecomposability graph I(G) of G is defined on V as follows. Given v≠w∈V, {v,w} is an edge of I(G) if G[V∖{v,w}] is indecomposable. The following is proved for an indecomposable digraph G=(V,A). For every digraph H=(V,B), if G and H have the same indecomposability vertices and if dI(G)(v)=dI(H)(v) for each v∈V, then H is indecomposable. We also study other types of indecomposability recognition.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 37, April 2014, Pages 32-42
نویسندگان
, , ,