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 acyclic digraphs with a unique source and a unique sink , 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, the following counts identify networks under reordering of subnetworks in either series or parallel. Equivalently, their read-once Boolean functions agree up to a permutation of the variables. This equivalence is broader than graph isomorphism (Golinelli 1997, p. 2). Multiple edges are allowed. The networks are classified 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.

For a positive integer , define as the number of series-parallel networks on indistinguishable edges and as the number of essentially series networks, with by convention. Then

(1)

For , is obtained by enumerating the partitions of . Let be the multiplicity of the part , so

(2)

The number of essentially series networks with this partition is . Hence

(3)

where the summation is over all partitions of with at least two parts, excluding the partition with and all other (Golinelli 1997, pp. 3-4). This gives a recurrence relation for computing from which can be computed as above.

In addition, the sequence satisfies the formal power series identity

(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 finite partially ordered set is series-parallel iff its comparability graph is a cograph.