# Generalizing series-parallel digraphs with feedback

There are common definitions of series-parallel (SP) graphs and digraphs: the basic idea is as follows. A SP graph (or digraph) has two distinguished vertices $s$ ("source") and $t$ ("target"). The graph with a single edge is SP by definition. Identifying the target of one SP graph with the source of another gives a "series" construction of a new SP graph. Identifying both sources and targets of two SP graphs gives a "parallel" construction of a new SP graph.

For digraphs we might consider a third operation, in which the source of one graph is identified with the target of a second and vice versa ("feedback"), with (say) the first graph's source and target becoming those of the feedback graph. Is there a reference in which such digraphs are discussed?

Note that since $K_4$ (undirected) is not SP, the above-mentioned class of digraphs must be nontrivial.

## 1 Answer

A slightly more general class is discussed in

Dan Dougherty, Claudio Gutiérrez. Normal Forms and Reduction for Theories of Binary Relations. LNCS 1833, pp 95-109 (2000) (http://link.springer.com/chapter/10.1007/10721975_7)

In Definition 4 they introduce four operations:

1. parallel composition
2. series composition
3. converse: interchange source and target (without changing edge directions)
4. branching: set the target to be equal to the source