RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2016 Number 4(34), Pages 74–80 (Mi pdm560)

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



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025