Geodesic
$\mathrm{T}$-irreducible extensions of directed starlike trees
Prikladnaâ diskretnaâ matematika, no. 4 (2016), pp. 74-80.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{PDM_2016_4_a5,
     author = {A. V. Gavrikov},
     title = {$\mathrm{T}$-irreducible extensions of directed starlike trees},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {74--80},
     publisher = {mathdoc},
     number = {4},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2016_4_a5/}
}
TY  - JOUR
AU  - A. V. Gavrikov
TI  - $\mathrm{T}$-irreducible extensions of directed starlike trees
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2016
SP  - 74
EP  - 80
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2016_4_a5/
LA  - ru
ID  - PDM_2016_4_a5
ER  - 
%0 Journal Article
%A A. V. Gavrikov
%T $\mathrm{T}$-irreducible extensions of directed starlike trees
%J Prikladnaâ diskretnaâ matematika
%D 2016
%P 74-80
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2016_4_a5/
%G ru
%F PDM_2016_4_a5
A. V. Gavrikov. $\mathrm{T}$-irreducible extensions of directed starlike trees. Prikladnaâ diskretnaâ matematika, no. 4 (2016), pp. 74-80. http://geodesic.mathdoc.fr/item/PDM_2016_4_a5/

[1] Bogomolov A. M., Salii V. N., Algebraic Foundations of the Discrete Systems Theory, Nauka Publ., M., 1997 (in Russian) | MR

[2] Kurnosova S. G., “T-irreducible extension for some classes of graphs”, Teoreticheskie Problemy Informatiki i ee Prilozheniy, SGU Publ., Saratov, 2004, 113–125 (in Russian)

[3] Kurnosova S. G., “T-irreducible extension of complete binary trees”, J. TSU. Supplement, 2005, no. 14, 158–160 (in Russian)

[4] Gavrikov A. V., “T-irreducible extension of unions of some types orgraphs”, Prikladnaya Diskretnaya Matematika, 2013, no. 4(22), 47–56 (in Russian)

[5] Gavrikov A. V., “T-irreducible extension of polygonal digraphs”, Izv. Vyssh. Uchebn. Zaved. Mat., 2016, no. 2, 18–23 (in Russian) | Zbl

[6] Salii V. N., “Zero-knowledge proofs in problems on extensions on graphs”, J. TSU. Supplement, 2003, no. 6, 63–65 (in Russian)

[7] Abrosimov M. B., “Some questions about the minimum extensions on graphs”, Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 6:1/2 (2006), 86–90 (in Russian)

[8] Hayes J. P., “A graph model for fault-tolerant computing systems”, IEEE Trans. Computers, S-26:9 (1976), 875–884 | DOI | MR

[9] Abrosimov M. B., “On the complexity of some problems related to graph extensions”, Mat. Zametki, 88:5 (2010), 643–650 (in Russian) | DOI | MR | Zbl