RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2010 supplement № 3, Pages 67–68 (Mi pdm181)

Mathematical Foundations of Reliability of Computing and Control Systems

On minimal edge $k$-extensions of oriented stars

M. B. Abrosimov

Saratov State University, Saratov

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.

UDC: 519.17



© Steklov Math. Inst. of RAS, 2024