Saturation and semisaturation of oriented graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.18600
curl -X POST /api/v1/records/arxiv/2610.18600/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.18600/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'