Saturation and semisaturation of oriented graphs

Source abstract

We consider a natural extension of the classical saturation problem to oriented graphs, defined as the minimum number of edges in an oriented graph $H$ on $n$ vertices that avoids a fixed oriented graph $G$, but adding any missing edge to $H$ creates a copy of $G$. Our main result shows that saturation functions of oriented graphs attain at least four distinct orders of magnitude. In particular, if $G$ is acyclic, then its saturation function is bounded if and only if $G$ contains an isolated edge; otherwise, it is linear. Certain tournaments together with an isolated edge give further infinite examples of bounded and linear saturation functions. Two additional orders of magnitude are $Θ(n \sqrt{\log n})$ and $Θ(n \log n)$. For these two, the lower bounds are obtained by adapting a recently developed approach for the saturation problem in edge-ordered graphs, while the matching upper bounds are constructive. Finally, we study the semisaturation problem, in which we require only that adding any missing edge to $H$ creates a copy of $G$. We completely characterize the possible orders of magnitude: the semisaturation function is either bounded, linear, or $Θ(n \log n)$.