1
$\begingroup$

I would like to ask a very fundamental question regarding distance-regular graphs. Denote $d(u,v)$ as the distance between node $u$ and $v$. Distance-regular graphs are graphs such that for any pair of vertices $u,v$ with $d(u,v)=i$, there are always $b_i$ neighbors $w$ of $u$ with $d(w,v)=i+1$ and $c_i$ neighbors $w$ of $u$ with $d(w,v)=i-1$. Therefore, distance-regular graphs are characterized by the intersection array $(b_0,\cdots,b_{D-1};c_1,\cdots,c_D)$ where $D$ is the dimension of the graph.

However, I wonder if it can be described using only the valency $k_i$, which is the number of nodes $v$ with $d(u,v)=i$ given an arbitrary node $u$. Clearly, the intersection array $(b_0,\cdots,b_{D-1};c_1,\cdots,c_D)$ uniquely determines $(k_1,\cdots,k_D)$. I would like to ask whether the converse also holds: $(k_1,\cdots,k_D)$ unique determines the intersection array $(b_0,\cdots,b_{D-1};c_1,\cdots,c_D)$. Thank you!

$\endgroup$
0

1 Answer 1

1
$\begingroup$

It seems that I have found such pair of distance-regular graphs, which are illustrated below. They both have 20 vertices.

The first graph is the Desargues Graph and the second is the Dodecahedron. enter image description here enter image description here

$\endgroup$

Your Answer

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

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