My Math Forum  

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

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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 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.
sulonski is offline  
 
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 k-subset 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 .
icemanfan is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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





Copyright © 2018 My Math Forum. All rights reserved.