[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