Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #8004

Re: on a self-complementary graph problem

Cross-posted to 2 groups.

Show all headers | View raw

Daniel Bastos <dbastos@toledo.com> writes:

> I'm looking for a strategy on how to solve this problem.  I appreciate
> any direction you may give me.
>
> Problem.  A simple graph G is self-complementary if G =~ G^c.  Show if G
> is self-complementary, then v = 0 (mod 4) or v = 1 (mod 4).

Let's say G has n vertices.  G^c is K_n with the edges of G removed.
What do you know about e(G) and e(G^c)?  What does that tell you about
e(K_n)?  Now consider exercise 1.2.7.

Does that help?

> This is problem 1.2.11 item (b) in ``Graph theory with applications'' by
> J.A. Bondy and U.S.R. Murty, Department of Combinatorics and
> Optimization, University of Waterloo, Ontario, Canada.  North-Holland,
> fifth printing, 1982.  ISBN: 0-444-19451-7.

The book uses K_n for the complete simple graph with n vertices.
Exercise 1.2.7 is to show that e(G) = (v 2) if and only if G is complete
(here I'm writing (v 2) for the binomial coefficient).  =~ is graph
isomorphism.

-- 
Ben.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

on a self-complementary graph problem Daniel Bastos <dbastos@toledo.com> - 2017-09-09 15:48 -0300
  Re: on a self-complementary graph problem Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-09 21:05 +0100
    Re: on a self-complementary graph problem Daniel Bastos <dbastos@toledo.com> - 2017-09-16 11:13 -0300
      Re: on a self-complementary graph problem Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-16 16:10 +0100
        Re: on a self-complementary graph problem Daniel Bastos <dbastos@toledo.com> - 2017-09-17 07:32 -0300

csiph-web