My Math Forum Graph Theory

 Applied Math Applied Math Forum

 August 1st, 2012, 07: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 k-subsets 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, 10: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 k-subset $s_1, s_2, ..., s_k$ where the $s_n$ 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 ${k \choose r}$ choices for the elements V has in common with Q, and the number of possibilities for the other elements of Q is ${n-k \choose k-r}$, with the exceptions of $k= r$ 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 ${k \choose r} \cdot {n-k \choose k-r}$.

 Tags graph, theory

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post lubna_mira Applied Math 0 January 12th, 2014 01:52 PM avnerg Applied Math 0 September 18th, 2013 06:03 AM proglote Number Theory 3 October 30th, 2011 04:20 PM johnyjj2 Applied Math 0 December 28th, 2010 02:49 PM kec11494 Applied Math 0 December 14th, 2010 06:01 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top