Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: producing a self complementary graph
Replies: 8   Last Post: Feb 2, 2012 11:00 PM

 Messages: [ Previous | Next ]
 divcurl@europe.com Posts: 60 Registered: 8/16/10
Re: producing a self complementary graph
Posted: Jan 31, 2012 10:47 PM

On Jan 30, 12:16 am, Butch Malahide <fred.gal...@gmail.com> wrote:
> On Jan 29, 6:42 pm, divcurl <divc...@europe.com> wrote:
>
>
>
>
>
>
>
>
>

> > Suppose I let H and K be self complementary graphs where K has
> > an order that is even, say, m. And if I produce another graph
> > F from H and K by joining a vertex from K only when the vertex
> > is of degree less than m/2 to every vertex of H, then how
> > would this make F self complementary also?

>
> > If K has even order m and is self complementary, then its size
> > will be (m*(m-1))/4 but what can I say about H other than
> > it is also self complementary by hypothesis? and how can I use
> > the idea that any vertex in K of degree < m/2 is joined to
> > every vertex of H will lead to the construction of a self
> > complementary graph F?

>
> > A degree of a vertex in K is < n/2 or
> > it is less than n/2 in its complement?

>
> > Any insight appreciated.
>
> I answered your last two graph theory questions and got no response.
> This one is even easier than those were. Try thinking about it.

I had shelved this one but I am looking at it again.
Where I was stuck was in discovering why for all vertices
of degree less than n/2 in K, linking said vertex to every
vertex in H would form a self-complementary graph.

An observation: taking H to be single vertex
and K to be P_4, then two verticesi n P_4
need to be linked to the vertex in H; this is

Let the vertices in general in H be p and
the number of vertices in K be q, then if
they are both self-complementary we have
that the number of edges for each will be:
p*(p-1)/4 and q*(q-1)/4 while in a graph
with p+q vertices we have (p+q)(p+q-1)/4
which multiplying out gives us an additional
term: 2pq/4 or pq/2 edges need to be added.

Now I'm not sure how to link this to
the idea that for each vertex in K of degree
< n/2 we add an edge to all vertices of H but
these statements are related in some way.