1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Self Complementary Graph Proof

  1. Mar 23, 2012 #1
    1. The problem statement, all variables and given/known data
    Suppose [itex]G \cong\bar{G}[/itex] and that [itex]n = |V(G)|=4k+1[/itex] for some [itex]k \ge 1[/itex]. Suppose that the degree sequence of G is [itex]d_{1}\ge d_{2} \ge ... \ge d_{n} [/itex]

    Prove that [itex]d_{i}+d_{n-i+1}=n-1[/itex] for each [itex]i=1, 2,...,n[/itex]


    2. Relevant equations
    I don't think there are any.


    3. The attempt at a solution
    I put the question in terms of k [itex]d_{i}+d_{4k-i+2}=n-1[/itex]
    and found the number of edges, since the graph has to have exactly half the maximum.
    [itex]|E(G)| = \frac{n(n-1)}{4}=\frac{(4k+1)(4k)}{4}=4k^{2}+4 [/itex]
    I'm not sure that help's, but I thought it might be useful. I need something about the degree sequence, and how it will look, but I'm not sure where to get that.
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?



Similar Discussions: Self Complementary Graph Proof
  1. A proof! (Replies: 0)

Loading...