|
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.
Citation:
A. V. Gavrikov, “$\mathrm{T}$-irreducible extensions of directed starlike trees”, Prikl. Diskr. Mat., 2016, no. 4(34), 74–80
Linking options:
https://www.mathnet.ru/eng/pdm560 https://www.mathnet.ru/eng/pdm/y2016/i4/p74
|
Statistics & downloads: |
Abstract page: | 125 | Full-text PDF : | 57 | References: | 33 |
|