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

Prikl. Diskr. Mat., 2008 Number 1(1), Pages 116–119 (Mi pdm19)

This article is cited in 7 papers

Applied Graph Theory

Minimal primitive extensions of oriented graphs

V. N. Salii

Saratov State University named after N. G. Chernyshevsky

Abstract: (Oriented) graph $G=(V,\alpha)$ is called primitive if there exists an integer $r\ge 1$ such that every two vertices can be connected by a route of length $r$. A graph $G'=(V,\alpha)$ is said to be a primitive extension of $G$ if $G'$ is primitive and $\alpha\subseteq\alpha'$. Primitive extensions with a minimal possible number of additional arcs are constructed for some acyclic graphs (trees, linear and polygonal graphs).

UDC: 519.17



© Steklov Math. Inst. of RAS, 2024