On minimal vertex 1-extensions of path orientation | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2017. № 38. DOI: 10.17223/20710410/38/6

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 и + k vertices, where и is the number of vertices in G, and G^* has the minimum number of edges among all k-vertex extensions of graph G with и + k vertices. In the paper, the upper and lower bounds for the number of additional arcs ec(^^_n) of a minimal vertex 1-extension of an oriented path ~iPn are obtained. For the oriented path ~iPn with ends of different types which is not isomorphic to Hamiltonian path, we have [(и + 1)/6] +2 @ ec(~P_n) @ и + 3. For the oriented path ~iPn with ends of equal types, we have [(и + 1)/4] +2 @ ec(jP_n) @ @ и + 3.