My Math Forum  

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

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
August 1st, 2012, 07:34 AM   #1
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, 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 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  

  My Math Forum > College Math Forum > Applied Math

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 01:52 PM
Graph theory: Linking graph characteristics and minimal cut avnerg Applied Math 0 September 18th, 2013 06:03 AM
Graph theory and number theory proglote Number Theory 3 October 30th, 2011 04:20 PM
graph theory - social networks and reverting the graph johnyjj2 Applied Math 0 December 28th, 2010 02:49 PM
Graph theory - 4 stroke graph kec11494 Applied Math 0 December 14th, 2010 06:01 PM

Copyright © 2018 My Math Forum. All rights reserved.