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:
What I'm a little disturbed by is the bolded claim I make above  namely that the complement of a kregular graph is an (nk1) 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 nk1. 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 'kpartite' 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) = nk1. 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 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A sets complement  WWRtelescoping  Algebra  3  February 18th, 2014 12:15 PM 
Question on isomorph Graphs and their complement Graphs  MageKnight  Applied Math  0  January 17th, 2013 11:38 PM 
p (B intersect (A complement))  finalight  Algebra  1  March 27th, 2012 01:34 PM 
complement of sets  Ben92  Applied Math  1  February 7th, 2011 08:19 AM 
orthonogonal complement  tinynerdi  Linear Algebra  1  May 3rd, 2010 08:53 AM 