5
$\begingroup$

According to this Wikipage series-parallel graphs are characterized like this:

2-connected series-parallel graphs are characterized by having no subgraph homeomorphic to $K_4$.

I couldn't find a similar characterization for series-parallel directed acyclic graphs (DAGs), however I think that the prohibited subgraph in this case can be a little simpler ($K_4$ minus one edge plus specific orientation):

Subgraph

Is it correct? Is it proven anywhere?

$\endgroup$
7
$\begingroup$

The two-connected series-parallel DAGs are also called 2-terminal series-parallel graphs. The graph in the figure is also known as Wheatstone graph and is known as the example graph for demonstrating Braess' paradox in algorithmic game theory.

It was shown [1, Theorem 5.3] that a DAG is 2-terminal series-parallel if and only if it does not contain a subgraph that is homeomorphic to the Wheatstone graph.

1 Pietro Cenciarelli, Daniele Gorla, Ivano Salvo: Inefficiencies in network models: A graph-theoretic perspective. Information Processing Letters 131 (2018) 44–50.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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