Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #8004
| Path | csiph.com!aioe.org!.POSTED!not-for-mail |
|---|---|
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
| Newsgroups | alt.algebra.help, comp.programming |
| Subject | Re: on a self-complementary graph problem |
| Date | Sat, 09 Sep 2017 21:05:05 +0100 |
| Organization | Aioe.org NNTP Server |
| Lines | 26 |
| Message-ID | <87zia3fxji.fsf@bsb.me.uk> (permalink) |
| References | <86h8wbemis.fsf@toledo.com> |
| NNTP-Posting-Host | wz2xIpMgzcNFB6/TmMn2fg.user.gioia.aioe.org |
| Mime-Version | 1.0 |
| Content-Type | text/plain |
| X-Complaints-To | abuse@aioe.org |
| X-Notice | Filtered by postfilter v. 0.8.2 |
| Cancel-Lock | sha1:MysgPmxy2HRg3961V+zsfh39fOo= |
| Xref | csiph.com alt.algebra.help:4990 comp.programming:8004 |
Cross-posted to 2 groups.
Show key headers only | 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
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