T-irreducible extensions of directed starlike trees | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 4(34). DOI: 10.17223/20710410/34/6

A digraph H = (W, в) is called a T-irreducible extension of a digraph G = (V, a), if | W| = | V| + 1, there is a vertex w e W such that H - w = G, G is embedded into every subgraph H - u for u = w, and no arc can be deleted from в without disturbing these properties. T-irreducible graph extensions are widely applied to synthesizing fault tolerant computing networks. In the paper, it is shown that, for any directed starlike tree G = (V, a) consisting of some directed chains P_i = (v₀, Vj,i,..., Vi,_ni), i = 1,..., k, beginning in the root (vo) of the tree, and having no other shared vertices, the digraph H = (V U {w},e), where a С в, (v₀,w) e в, (w,v_i,_ni-1) e в for all i, 0 ^ i ^ k - 1, ni > 2 ^ ((w, Vi,ni-2) e в, 0 < i < k - 1, (w, Vi,ni-1) e в, 0 < i < k - 1), n > 3 ^ ^ ((w, v_i,j), (v_i,j, w) e в, 0 ^ i ^ k - 1,1 ^ j ^ n_i - 3), is a T-irreducible extension of G.