TOPICS
Search

Series-Parallel Graph


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 n 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 n>1, the number of networks in n edges is twice the number of essentially series networks. For n=1, the number of networks is 1.

Define a_n as the number of series-parallel networks on n indistinguishable edges and b_n as the number of essentially series networks. Then

 a_n={1   if n=1; 2b_n   otherwise.
(1)

b_n can be found out by enumerating the partitions of n. Consider a partition {p_i} of n, i.e.,

 sum_(i)ip_i=n.
(2)

Then the number of essentially series networks can be computed as product_(i)(b_i+p_i-1; i). Hence

 b_n=sum_(p_i)product_(i)(b_i+p_i-1; i),
(3)

where the summation is over all partitions p_i of n excluding the trivial partition {0,0,...,n}. This gives a recurrence for computing b_n from which a_n can be computed as above.

In addition, the sequence satisfies

 product_(k=1)^infty1/((1-x^k)^(b_k))=1+sum_(k=1)^inftya_kx^k,
(4)

or more explicitly,

 1/(1-x)product_(k=2)^infty1/((1-x^k)^(a_k))=1+sum_(k=1)^inftya_kx^k.
(5)

The first few values of a_n for n=1, 2, ... are 1, 2, 4, 10, 24, 66, 180, 522, 1532, 4624, ... (OEIS A000084), and for b_n 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.


See also

Cograph

Portions of this entry contributed by Rajsekar

Explore with Wolfram|Alpha

References

Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications I: The Tutte Polynomial." 28 Jun 2008. http://arxiv.org/abs/0803.3079.Eppstein, D. "Parallel Recognition of Series-Parallel Graphs." Information and Computation 98, 41-55, 1992.Finch, S. "Series-Parallel Networks." July 7, 2003. http://algo.inria.fr/bsolve/.Sloane, N. J. A. Sequences A000084 and A000669 in "The On-Line Encyclopedia of Integer Sequences."Valdes, J. "Parsing Flowcharts and Series-Parallel Graphs." Ph.D. thesis. Also technical report STAN-CS-78-682, Computer Science Department. Stanford, CA: Stanford University, 1978.

Cite this as:

Rajsekar and Weisstein, Eric W. "Series-Parallel Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Series-ParallelGraph.html

Subject classifications