Using Symbolic Computation to Prove Nonexistence of Distance-Regular Graphs

  • Janoš Vidali University of Ljubljana, Faculty of Mathematics and Physics
Keywords: Distance-regular graphs, Krein parameters, Triple intersection numbers, Nonexistence, Symbolic computation


A package for the Sage computer algebra system is developed for checking feasibility of a given intersection array for a distance-regular graph. We use this tool to show that there is no distance-regular graph with intersection array

$$\{(2r+1)(4r+1)(4t-1), 8r(4rt-r+2t), (r+t)(4r+1); 1, (r+t)(4r+1), 4r(2r+1)(4t-1)\}  (r, t \geq 1),$$

$\{135,\! 128,\! 16; 1,\! 16,\! 120\}$, $\{234,\! 165,\! 12; 1,\! 30,\! 198\}$ or $\{55,\! 54,\! 50,\! 35,\! 10; 1,\! 5,\! 20,\! 45,\! 55\}$. In all cases, the proofs rely on equality in the Krein condition, from which triple intersection numbers are determined. Further combinatorial arguments are then used to derive nonexistence.

Article Number