My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
April 24th, 2012, 10:39 AM   #1
Joined: Apr 2011

Posts: 7
Thanks: 0

Complement of regular graphs

Hi all,
Been working on some homework, had a quick question.
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!)
geliot is offline  
April 24th, 2012, 11:02 AM   #2
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.
geliot is offline  

  My Math Forum > College Math Forum > Applied Math

complement, graphs, regular

Search tags for this page
Click on a term to search for related topics.
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

Copyright © 2019 My Math Forum. All rights reserved.