Oriented Graph Saturation

Abstract

For graphs $G$ and $H$, $H$ is said to be $G$-saturated if it does not contain a subgraph isomorphic to $G$, but for any edge $e\in H^c$, the complement of $H$, $H+e$, contains a subgraph isomorphic to $G$. The minimum number of edges in a $G$-saturated graph on $n$ vertices is denoted $\text{sat}(n,G)$. While digraph saturation has been considered with the allowance of multiple arcs and $2$-cycles, we address the restriction to oriented graphs. First, we prove that for any oriented graph $D$, there exist $D$-saturated oriented graphs, and hence show that $\text{sat}(n,D)$, the minimum number of arcs in a $D$-saturated oriented graph on $n$ vertices, is well defined for sufficiently large $n$. Additionally, we determine $\text{sat}(n,D)$ for some oriented graphs $D$, and examine some issues unique to oriented graphs.