Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
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
two additional edges. Why?
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.
|
|
|
|
