Abstract:
A graph $G^*$ is $k$-edge extension of graph $G$ if every graph obtained by removing any $k$ edges(arcs) from $G^*$ contains $G$. $k$-edge extension of graph $G$ with $n$ vertices is called minimal if among all $k$-edge extensions of graph $G$ with $n$ vertices it has the minimum possible number of edges (arcs). Oriented star is obtained from unoriented star by replacing edges with arcs. We provide the complete description of minimal $k$-edge extensions for oriented stars.