Name for Number of Ancestors/Descendants of Vertex in Directed Acyclic Graph

Question

Let $G = (V, E)$ be a directed acyclic graph. For each vertex $v \in V$, define the ancestors of $v$ to be the set of vertices $u \in V$ such that there exists a directed path from $u$ to $v$. Similarly, define the descendants of $v$ to be the set of vertices $w \in V$ such that there exists a directed path from $v$ to $w$. What are the standard names for the number of ancestors and descendants for a given vertex? (They would be analogous to the indegree and outdegree of a vertex.)

Answer 1

Since no one immediately answered this question, I suspect that there are no standard terms for the number of descendants or the number of ancestors of a given node in a directed acyclic graph (DAG). But remember that the point of writing is just to clearly convey an idea to the reader, so you should feel free to invent terms as you need them, just so long as the terms you invent are sensible. I'll compile a few suggestions for you.

• My first thought is to think of the DAG as a partially ordered set (poset). Letting $V$ be the set of nodes of our DAG, we can define a partial ordering $\leq$ on $V$ such that $\forall a,b \in V$, $a \leq b$ if there exists a (potentially empty) path from $a$ to $b$. Then we can sensibly define $a<b$ if $a$ is an ancestor of $b$ (or equivalently if $b$ is a descendant of $a$). Using this we can denote the set of ancestors of a node $x$ as $A_x$ and the set descendants of a node $x$ as $D_x$, where $$ A_x = \{y \in V \mid y<x\} \qquad D_x = \{y \in V \mid y>x\}\;. $$ Then we can represent the number of ancestors and descendants symbolically with this mathematical notation as $|A_x|$ and $|D_x|$.

• Following this line of thought, we can also just expand the notion of indegree and outdegree. Let $G$ be a DAG with the partial ordering defined above. Let $G'$ be the DAG induced by completing the partial ordering on $G$ by expanding it from a node being reachable to a node being adjacent. More specifically, $G'$ is the graph with the same vertex set as $G$ where $a \to b$ is an edge of $G'$ if and only if there exists some path from $a$ to $b$ in $G$. So we are just adding the necessary edges to $G$ to make vertex adjacency transitive. Now we note that the indegree and outdegree of a node $x$ in $G'$ is exactly the number of ancestors and descendants respectively of the node $x$ in $G$. So thinking this way, you could refer to the number of ancestors or the number of descendants of a given node $x$ respectively as the induced indegree and the induced outdegree of $x$.

• Or of course you just be use a new word or term, like

  • ancestor-count and descendant-count
  • lesser-count and greater-count
  • the support of $x$ and the load of $x$
  • absolute indegree and absolute outdegree
  • total indegree and total outdegree