Advertisement
Help Keep Boards Alive. Support us by going ad free today. See here: https://subscriptions.boards.ie/.
If we do not hit our goal we will be forced to close the site.

Current status: https://keepboardsalive.com/

Annual subs are best for most impact. If you are still undecided on going Ad Free - you can also donate using the Paypal Donate option. All contribution helps. Thank you.
https://www.boards.ie/group/1878-subscribers-forum

Private Group for paid up members of Boards.ie. Join the club.

Graph Theory question

  • 01-12-2008 08:10PM
    #1
    Closed Accounts Posts: 90 ✭✭


    Hi can anyone help with this exam question....

    A (p, q) graph G is said to be self complementary if G is isomorphic to G

    (a) Prove that if G is a self-complementary (p, q) graph, p is of the form 4k or 4k+1

    (b) Find examples of self-complementary graphs of order 8 and 9.


Comments

  • Registered Users, Registered Users 2 Posts: 1,595 ✭✭✭MathsManiac


    I think you left out a "prime" symbol there: (G is to be isomorphic to G').

    First part: G and G' together give the complete graph of order p, which has pC2 = p(p-1)/2 edges. So, if G is isomorphic to G', G must have p(p-1)/4 edges. Since one of p and (p-1) must be odd, then the even one must be divisible by 4.

    Second part: can't see an obvious way to do it, but messing around in some systematic way with graphs with 8 vertices and 14 edges must be the key. The problem is how to mess about in a sufficiently insightful manner! (Similarly for 9 vertices and 18 edges.)

    The following link indicates that there are 10 distinct answers in the case of (8,14) and 36 in the case of (9,18): http://www.research.att.com/~njas/sequences/A000171


  • Closed Accounts Posts: 90 ✭✭deathronan


    Cheers mate, appreciate it!


Advertisement