Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653740 | European Journal of Combinatorics | 2014 | 11 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
A. Boussaïri, A. Chaïchaâ, P. Ille,