What characterises vertices at fixed indices in all topological orderings?

Question

Let $G$ be a DAG with $v \in V$. Suppose that there exists some $i$ such that for all topological orderings $v_1, \ldots, v_n$ we have $v_i = v$.

What's a set of necessary and sufficient conditions about $v$ for this to occur?

Answer 1

Theorem: A given vertex $v$ always comes first, $i = 1$, iff it has no incoming edges and every other vertex has at least one incoming edge.

Right-to-left implication: no vertex other than $v$ can come first, since they all have incoming edges.

Left-to-right: for $v$ to come first it has to have in-degree 0. If some vertex $w$ has in-degree 0 with $w \neq v$ and there's a topological ordering where $w$ has a left neighbour $u$, then swapping $w$ and $u$ yields another topological ordering: the only vertices which have new relative positions are $u$ and $w$, and since $w$ has in-degree 0 no constraint is violated by putting it before $u$.

Repeatedly move the leftmost such $w$ one step to the left; this will end when one such $w$ comes first, contradicting the assumption that $v$ always comes first. Hence no $w$ exists.

QED

By a symmetric argument, a vertex always comes last if it alone has out-degree 0.

Theorem: $v$ is fixed-index iff it is comparable to every other vertex (i.e. for all $w$, either $w = v$ or there is a path from $v$ to $w$ or there is a path from $w$ to $v$).

Right-to-left: compare $v$ to all other vertices. All $w$ with a path to $v$ must come before $v$ and all $u$ with a path from $v$ to $u$ must come after $v$. That leaves only one index at which $v$ can occur.

Left-to-right: assume for the sake of contradiction that there exists some $w$ to the left of $v = v_j$ in some topological ordering, where $w$ is incomparable to $v$, i.e. there is neither a path from $v$ to $w$ nor from $w$ to $v$. Let $u = v_i$ be the rightmost among those, $i < j$.

Consider $t = v_{i+1}$. By $u$ being the rightmost incomparable vertex left of $v$, either $t = v$ or $t < v$. If $u$ were comparable to $t$ then $u$ would also be comparable to $v$ (by transitivity through $t$) so it isn't. Hence we can swap $u$ and $t$ and remain topologically ordered. Continue doing this until $u$ and $v$ get swapped, contradicting $v$ being fixed-index.

Similarly derive a contradiction from the existence of an incomparable vertex to the right of $v$. Hence there is no incomparable vertex.

QED

Some consequences:

Let a digraph $G$ be Weakly Connected if the undirected counterpart is connected; define Weakly Connected Components analogously.

Any interleaving of the topological orderings of two weakly connected components is a topological ordering of their union. In particular, one can put the entire ordering of one component immediately before or after a given vertex in the other component, so no vertex can be fixed-index (so long as both components are non-empty).

Corollary: a DAG with a fixed-index vertex is weakly connected.

A more direct and constructive proof: $path(s, v) + path(v, t) = path(s, t)$ where the precise definition of $path$ and $+$ is left as an exercise ;-)

There is no implication in the other direction: consider the complete bipartite graph on 2+2 vertices, edges left-to right, with $a, b$ on the left and $c, d$ on the right; then $a$ and $b$ come before $c$ and $d$, but $a$ and $b$ can always be swapped, and so can $c$ and $d$. This graph is weakly connected but has no fixed-index vertex.

It is also not the case that all paths from $v_i$ to $v_k$ go through $v = v_j$ when $i < j < k$. For (counter)example, $V = \{a, b, c\}$ and $E = \{(a, b), (a, c), (b, c)\}$ which has only one topological ordering. Let $(v_i, v, v_k) = (a, b, c)$; then there is a path of length 1 from $a$ to $c$ which doesn't go through $b$.