August 1st, 2012, 08:34 AM  #1 
Newbie Joined: Jun 2012 Posts: 13 Thanks: 0  Graph Theory
Let n,k,r be positive integers with r <= k <=n and let S be a set of cardinality n. Then J(n,k,r) is the graph whose vertices are the ksubsets of S, and where two vertices are adjacent if the intersection of the two subsets to which they correspond has cardinality r. Prove that J(n,k,r) is regular and determine the degree of the vertices. Can anyone prove this, it is easy to find a formula for case where r=0 but not so easy to find general formula for any r. 
August 2nd, 2012, 11:03 AM  #2 
Senior Member Joined: Feb 2012 Posts: 628 Thanks: 1  Re: Graph Theory
It's not that hard to prove that J(n,k,r) is regular. Look at it from the point of view of an arbitrary vertex V of the graph. Let V correspond to the ksubset where the are arbitrary elements of S. Now, given r less than or equal to k, the number of vertices Q adjacent to V is given by the choice of which elements V has in common with Q, and what the other elements of Q are. There are choices for the elements V has in common with Q, and the number of possibilities for the other elements of Q is , with the exceptions of and if it cannot be calculated, in which case it should be taken to be zero. Then the degree of each vertex in J is . 

Tags 
graph, theory 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A graph problem in graph theory!  lubna_mira  Applied Math  0  January 12th, 2014 02:52 PM 
Graph theory: Linking graph characteristics and minimal cut  avnerg  Applied Math  0  September 18th, 2013 07:03 AM 
Graph theory and number theory  proglote  Number Theory  3  October 30th, 2011 05:20 PM 
graph theory  social networks and reverting the graph  johnyjj2  Applied Math  0  December 28th, 2010 03:49 PM 
Graph theory  4 stroke graph  kec11494  Applied Math  0  December 14th, 2010 07:01 PM 