Applied Math Applied Math Forum

April 24th, 2012, 10:39 AM   #1
Newbie

Joined: Apr 2011

Posts: 7
Thanks: 0

Complement of regular graphs

Hi all,
Been working on some homework, had a quick question.
Quote:
 So let G be a regular graph, and let H be the complement of G (and ?(G) represents the vertex coloring of a graph, G): Prove that ?(G)+?(H)<=n+1.
It's pretty straight forward stuff - we know that both ?(G) and ?(H) are upper bounded by [?(G)+1] and [?(H)+1], respectively (where ? is the max degree of the graph). Since G is regular, every node is k-connected, and since H is the complement of G, ?(H)=(n-?(G)-1), and then with a little algebraic massage we end up with ?(G)+?(H)<= ?(G)+1+(n-?(G)-1) + 1 = n + 1, and there you have it.

What I'm a little disturbed by is the bolded claim I make above - namely that the complement of a k-regular graph is an (n-k-1) regular graph. I missed a day of class, and while the notes I borrowed have this statement in them, they don't explain why this is the case. I've thought about it, and I'm kinda running into a wall, and strangely I can't seem to find anything about it on the internet? I'd really appreciate an explanation (or even a nudge in the right direction!)
Thanks,
Geliot April 24th, 2012, 11:02 AM #2 Newbie   Joined: Apr 2011 Posts: 7 Thanks: 0 Re: Complement of regular graphs Sorry, can't find the edit button! But I've been thinking about it a little more, think I might be headed in the right direction but still don't know how to wrap it up. So obviously if G is a connected, regular graph then of course the complement is just going to be a 0 connected graph, which is nicely expressed by n-k-1. It gets a little trickier when G is not connected. The way I think about it, the complement of a disconnected, regular graph can be thought of as a 'k-partite' graph, where k is the number of disconnected subgraphs within G, which is to say every one of these subgraphs connects to each node in all other subgraphs, but not to nodes within its own subgraph (so just a generalized bipartite graph). Then it stands to reason that each node will have the same degree (since all subgraphs are identical) and thus the complement is indeed connected. We know each node will NOT be connected to each node it was connected to in G, which is just the regularity, k, of G. Since each node also does not connect to itself, we subtract an additional 1, so we end up with delta(complement) = n-k-1. Looks like typing that out actually did the trick for me, but I'll leave the answer up here since it doesn't seem to pop up on a simple google search at the moment. Tags complement, graphs, regular ,

,

,

,

,

,

,

,

,

,

# a graph is regular if its complement is regular

Click on a term to search for related topics.
 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post WWRtelescoping Algebra 3 February 18th, 2014 12:15 PM MageKnight Applied Math 0 January 17th, 2013 11:38 PM finalight Algebra 1 March 27th, 2012 01:34 PM Ben92 Applied Math 1 February 7th, 2011 08:19 AM tinynerdi Linear Algebra 1 May 3rd, 2010 08:53 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top      