On minimal vertex $1$-extensions of path orientation

M. B. Abrosimov ; O. V. Modenova

Prikladnaâ diskretnaâ matematika, no. 4 (2017), pp. 89-94

Résumé

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$.

Détail

Keywords: minimal vertex extension, node fault tolerance
Mots-clés : path orientation.