1
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ This is series-parallel graph (which is undirected, but can be uniquely made directed). $\endgroup$
    – Yuzhou Gu
    Commented Sep 28, 2017 at 11:22
  • $\begingroup$ Worth pointing out: if $D$ is a foo-digraph, then the free category generated by $G$ is a confluent category. I have not looked into the question if and how the converse holds. $\endgroup$
    – Peter Heinig
    Commented Sep 28, 2017 at 17:59
  • $\begingroup$ One can probably characterize this as follows: 'a digraph $D$ is a foo-digraph if and only if it is (the downwards orientation of) a *Hasse diagram of a finite poset with both a greatest and a least element and property $P$', where I am unsure at the moment what the right $P$ is. $\endgroup$
    – Peter Heinig
    Commented Sep 28, 2017 at 18:10
  • $\begingroup$ @PeterHeinig: triangles are allowed, I think. $\endgroup$
    – Martin Rubey
    Commented Sep 28, 2017 at 20:48
  • $\begingroup$ @MartinRubey: you are right in saying that triangles are allowed by goblin, more precisely, goblin allows one to construct a transitive tournaments on three vertices, and $\text{ therefore Hasse diagrams are irrelevant here}$ (please note I only said 'probably'). How to get a transitive triangle from goblin's axioms: start with two copies of a directed path, glued at their endvertices (= 'oriented dipole' ), then apple goblin's second axiom to replace one of the constituent 2-vertex paths by a 3-vertex directed path. $\endgroup$
    – Peter Heinig
    Commented Sep 29, 2017 at 5:32

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .