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$

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.