Applied Graph Theory
$\mathrm{T}$-irreducible extensions of directed starlike trees
A. V. Gavrikov LLC Yandeks. Market Lab, Saint Petersburg, Russia
Abstract:
A digraph
$H=(W, \beta)$ is called a
$\mathrm{T}$-irreducible extension of a digraph
${G}=(V, \alpha)$, if
$|W|=|V|+1$, there is a vertex
$w\in W$ such that
$H-w\cong G$,
$G$ is embedded into every subgraph
$H-u$ for
$u\neq w$, and no arc can be deleted from
$\beta$ without disturbing these properties.
$\mathrm{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,\alpha)$ consisting of some directed chains
$P_i=(v_0,v_{i,1},\ldots,v_{i,n_i})$,
$i=1,\ldots,k$, beginning in the root (
$v_0$) of the tree, and having no other shared vertices, the digraph
$H=(V\cup\{w\},\beta)$, where
$\alpha\subseteq\beta$,
$(v_0,w)\in\beta$,
$(w, v_{i, n_{i} - 1}) \in \beta$ for all
$i, 0 \le i \le k - 1$, $n_i>2\Rightarrow((w,v_{i,n_i-2})\in\beta,0\leq i\leq k-1, (w,v_{i,n_i-1})\in\beta, 0\leq i\leq k-1)$, $n_i>3\Rightarrow((w,v_{i,j}),(v_{i,j},w)\in\beta,0\leq i\leq k-1, 1\leq j\leq n_i-3)$, is a
$\mathrm{T}$-irreducible extension of
$G$.
Keywords:
$\mathrm{T}$-irreducible extension, directed tree, starlike tree.
UDC:
519.17
DOI:
10.17223/20710410/34/6