3
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.