[A058387] Series-Parallel Confusion

Gordon Royle gordon at csse.uwa.edu.au
Fri Nov 8 04:34:17 CET 2002

> The literature has a number of different definitions of
> "series-parallel network.  Sometimes multiple sources
> and sinks are permitted.

I agree... and now I understand a bit more.

The object that OEIS refers to as a "series parallel network" is what
I know as a "two terminal series-parallel graph" [I think graph/network
is not the distinction here, but 2-terminal is critical.]

The general term "series-parallel graph" is used (by me, at least!) to refer to 
a graph that contains no subgraph homeomorphic to K_4, a.k.a a partial 2-tree.  

I spoke to Jerry Spinrad (co-author of "Graph Classes") and he said that
they had a great deal of difficulty with the definition of "series-parallel
graph" due to inconsistent definitions in the literature... and in fact, 
re-reading their attempted definition in terms of series and parallel 
reductions, I think they have still got it wrong!

At the risk of opening a can o' worms, should the OEIS incorporate a 
glossary where the terms used are precisely defined?  

Dr. Gordon F Royle, http://www.cs.uwa.edu.au/~gordon, gordon at cs.uwa.edu.au

More information about the SeqFan mailing list