Geodesic
On minimal vertex $1$-extensions of path orientation
Prikladnaâ diskretnaâ matematika, no. 4 (2017), pp. 89-94.

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

In 1976, J. Hayes proposed a graph theoretic model for the study of system fault tolerance by considering faults of nodes. In 1993, the model was expanded to the case of failures of links between nodes. A graph $G^*$ is a $k$-vertex extension of a graph $G$ if every graph obtained by removing $k$ vertex from $G^*$ contains $G$. A $k$-vertex extension $G^*$ of graph $G$ is said to be minimal if it contains $n+k$ vertices, where $n$ is the number of vertices in $G$, and $G^*$ has the minimum number of edges among all $k$-vertex extensions of graph $G$ with $n+k$ vertices. In the paper, the upper and lower bounds for the number of additional arcs $ec(\overrightarrow P_n)$ of a minimal vertex $1$-extension of an oriented path $\overrightarrow P_n$ are obtained. For the oriented path $\overrightarrow P_n$ with ends of different types which is not isomorphic to Hamiltonian path, we have $\lceil({n+1})/6\rceil+2\leq ec(P_n)\leq n+3$. For the oriented path $\overrightarrow P_n$ with ends of equal types, we have $\lceil({n+1})/4\rceil+2\leq ec(P_n)\leq n+3$.
Keywords: minimal vertex extension, node fault tolerance
Mots-clés : path orientation. 
@article{PDM_2017_4_a5,
     author = {M. B. Abrosimov and O. V. Modenova},
     title = {On minimal vertex $1$-extensions of path orientation},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {89--94},
     publisher = {mathdoc},
     number = {4},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2017_4_a5/}
}
TY  - JOUR
AU  - M. B. Abrosimov
AU  - O. V. Modenova
TI  - On minimal vertex $1$-extensions of path orientation
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2017
SP  - 89
EP  - 94
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2017_4_a5/
LA  - ru
ID  - PDM_2017_4_a5
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%A O. V. Modenova
%T On minimal vertex $1$-extensions of path orientation
%J Prikladnaâ diskretnaâ matematika
%D 2017
%P 89-94
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2017_4_a5/
%G ru
%F PDM_2017_4_a5
M. B. Abrosimov; O. V. Modenova. On minimal vertex $1$-extensions of path orientation. Prikladnaâ diskretnaâ matematika, no. 4 (2017), pp. 89-94. http://geodesic.mathdoc.fr/item/PDM_2017_4_a5/

[1] Hayes J. P., “A graph model for fault-tolerant computing system”, IEEE Trans. Comput., C-25:9 (1976), 875–884 | DOI | MR

[2] Harary F., Hayes J. P., “Node fault tolerance in graphs”, Networks, 27 (1996), 19–23 | 3.0.CO;2-H class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[3] Harary F., Hayes J. P., “Edge fault tolerance in graphs”, Networks, 23 (1993), 135–142 | DOI | MR | Zbl

[4] Abrosimov M. B., “On the complexity of some problems related to graph extensions”, Math. Notes, 88:5–6 (2010), 619–625 | DOI | DOI | MR | Zbl

[5] Kireeva A. V., “Fault tolerance of functional graphs”, Uporyadochennye mnozhestva i reshetki, 11, SSU Publ., Saratov, 1995, 32–38 (in Russian)

[6] Sung T. Y., Lin C. Y., Chuang Y. C., Hsu L. H., “Fault tolerant token ring embedding in double loop networks”, Inform. Process. Lett., 66 (1998), 201–207 | DOI | MR | Zbl

[7] Bogomolov A. M., Salii B. K., Algebraic Foundations of the Theory of Discrete Systems, Nauka Publ., Moscow, 1997, 368 pp. (in Russian) | MR

[8] Abrosimov M. B., Graph Models for Fault Tolerance, SSU Publ., Saratov, 2012, 192 pp. (in Russian)

[9] Abrosimov M. B., “Minimal vertex extensions of directed stars”, Diskr. Math., 23:2 (2011), 93–102 (in Russian) | DOI | MR

[10] Abrosimov M. B., Modenova O. V., “Characterization of graphs with a small number of additional arcs in a minimal 1-vertex extension”, Izv. Saratov Univ. (N.S.) Ser. Math. Mech. Inform., 13:2, part. 2 (2013), 3–9 (in Russian) | Zbl

[11] Abrosimov M. B., Modenova O. V., “Characterization of graphs with three additional edges in a minimal 1-vertex extension”, Prikladnaya Diskretnaya Matematika, 2013, no. 3, 68–75 (in Russian)