A two-terminal directed series-parallel graph is a graph with distinguished source 
and target 
constructed recursively from a single directed edge by series and parallel composition.
In a series composition, the target of one two-terminal series-parallel graph is
identified with the source of another. In a parallel composition, their two sources
are identified, as are their two targets. The undirected definition uses the same
operations on graphs with two distinguished terminal vertices.
If each edge has a distinct label, series composition corresponds to multiplication and parallel composition to addition in the s-t path polynomial. The recursive construction therefore gives a read-once path expression in which every edge label occurs exactly once. This expression has minimum possible length (Bein et al. 1992). For two-terminal acyclic digraphs, an equivalent characterization is the absence of a subgraph homeomorphic to the directed Wheatstone bridge (Burns and Steiner 1981, Bein et al. 1992).
In combinatorial mathematics, the series-parallel networks problem asks for the number of networks that can be formed using a given number of edges. The edges can be distinguishable or indistinguishable.
When the edges are indistinguishable, consider the problem of enumerating the number of topologically different networks on 
edges, where multiple edges are allowed. The idea is to break-down
the problem by classifying the networks as essentially series and essentially parallel
networks.
1. An "essentially series network" is a network which can be broken down into two or more "subnetworks" in series.
2. An "essentially parallel network" is a network which can be broken down into two or more "subnetworks" in parallel.
By the duality of networks, it can be proved that the number of essentially series networks is equal to the number of essentially parallel networks. Thus for all 
, the number of networks in 
edges is twice the number of essentially
series networks. For 
, the number of networks is 1.
Define 
as the number of series-parallel networks on 
indistinguishable edges and 
as the number of essentially series networks. Then
 |
(1)
|
can be found out by enumerating the partitions of 
. Consider a partition 
of 
, i.e.,
 |
(2)
|
Then the number of essentially series networks can be computed as 
. Hence
 |
(3)
|
where the summation is over all partitions 
of 
excluding the trivial partition 
. This gives a recurrence for computing 
from which 
can be computed as above.
In addition, the sequence satisfies
 |
(4)
|
or more explicitly,
 |
(5)
|
The first few values of 
for 
, 2, ... are 1, 2, 4, 10, 24, 66, 180, 522, 1532, 4624, ...
(OEIS A000084), and for 
are 1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, ... (OEIS A000669).
Valdes (1978) showed that a partially ordered set is series-parallel iff its comparability graph is a cograph.
