cographs

[Jon Awbrey]

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

hi eric, where is the thm? ~~ ja

Eric W. Weisstein wrote:
> 
> ---------- Forwarded message ----------
> Date: Thu, 9 Oct 2003 15:22:25 -0500 (CDT)
> From: Eric W. Weisstein <eric at weisstein.com>
> To: GRAPHNET - Graph Theory <GRAPHNET at LISTSERV.NODAK.EDU>
> Subject: Re: cographs
> 
> On Thu, 9 Oct 2003, Dr I. Sciriha wrote:
> 
> > Cographs, are the graphs belonging to the following recursively defined
> > family:
> > 1. K1 is a cograph,
> > 2. If X is a cograph, then so is its complement, and
> > 3. If X and Y are cographs, then so is their union XUY.
> >
> > Theorem: A graph is a cograph if and only if
> > it does not have the path P_4 as an induced subgraph.
> 
> I compute the counts of distinct cographs on n=1, 2, ... nodes as
> 1,2,4,10,24,66,180,522, which looks identical to
> http://www.research.att.com/projects/OEIS?Anum=A000084
> "Series-parallel networks with n unlabeled edges.
> Also called yoke-chains by Cayley and MacMahon."
> 
> Are these two sets of objects indeed isomorphic and, if so, is this known?
> 
> Cheers,
> -Eric

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o