Applied Graph Theory

On minimal vertex $1$-extensions of path orientation

M. B. Abrosimov^a, O. V. Modenova<sup>b

a</sup> Saratov State University, Saratov, Russia
^b SEC "Erudit"', Saratov, Russia

Abstract: 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, path orientation.

UDC: 519.17

DOI: 10.17223/20710410/38/6

Bibliographic databases:

•