Article ID Journal Published Year Pages File Type
4653740 European Journal of Combinatorics 2014 11 Pages PDF
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
, , ,