1
$\begingroup$

1) How many nodes does a ball of radius $r$ in the Johnson graph $J(n,k)$ contain (Volume)?

2) How many nodes $v$ does a ball with center $x$ of radius $r$ in the Johnson graph $J(n,k)$ contain such that $d(x,v)=r$ (Surface)?

The Jonhson Graph is defined here:

https://en.wikipedia.org/wiki/Johnson_graph

Any reference to this question would be very nice.

$\endgroup$
5
$\begingroup$

The number of vertices $p_r$ which satisfy $d(x,v)=r$ in a distance regular graph can be computed from the intersection array:

$p_r=\frac{b_1b_2...b_r}{c_1c_2...c_r}$

For Johnson graphs, $p_r=(^k_r)(^{n-k}_{ r})$.

$\endgroup$
  • $\begingroup$ thank you for your answer $\endgroup$ – orgesleka Jul 28 '19 at 11:25
  • $\begingroup$ does that mean that for the volume it is just the sum for i=0...r? $\endgroup$ – orgesleka Jul 28 '19 at 17:27
  • $\begingroup$ Yes. For $i=0$, $p_r$ shoudl be taken as $1$. $\endgroup$ – LeechLattice Jul 29 '19 at 3:19
  • $\begingroup$ What does "intersection array" mean? $\endgroup$ – user2679290 Aug 5 '19 at 23:38
  • $\begingroup$ @user2679290 See the general definition and that of Johnson graphs. $\endgroup$ – LeechLattice Aug 6 '19 at 4:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.