Skip to main content
2 of 2
added graphs with arrows (since they are "directed")

Is there a name for these especially simple directed acyclic graphs, and are any decent characterizations known?

Define the notion of a "foo digraph" recursively as follows.

  • If we take any finite number of directed path graphs each of which has at least $2$ vertexes, and glue them at the start and end vertexes, the result is a foo digraph.

  • If we take any foo digraph and replace an edge in that digraph with a foo digraph pointing `in the correct direction,' the result is a foo digraph.

  • Nothing else is a foo digraph.

For example:

enter image description here

is a foo digraph, where the arrows implicitly point down.

So basically, we're talking about directed acyclic graphs that equal their own transitive reductions, subject to some constraints saying that certain subgraphs like

enter image description here

can't appear, and some completeness conditions saying that there's a start vertex $\top$, and end vertex $\bot$, and that each vertex $v$ must correspond to another vertex $v'$ such that the out-degree of $v$ equals the in degree of $v'$, and the set of paths from $\top$ to $\bot$ that pass through $v$ equals the set of paths from $\top$ to $\bot$ that pass through $v'$.

The above may not be a complete characterization.

Question. Is there a name for what I'm calling foo digraphs, and are any decent graph-theoretic characterizations known?

goblin GONE
  • 3.8k
  • 18
  • 39