Bounds for regular induced subgraphs of strongly regular graphs

Abstract

Given feasible strongly regular graph parameters $(v,k,\lambda ,\mu )$ and a non-negative integer $d$, we determine upper and lower bounds on the order of a $d$-regular induced subgraph of any strongly regular graph with parameters $(v,k,\lambda ,\mu )$. Our new bounds are at least as good as the bounds on the order of a $d$-regular induced subgraph of a $k$-regular graph determined by Haemers. Further, we prove that for each non-negative integer $d$, our new upper bound improves on Haemers' upper bound for infinitely many strongly regular graphs.

Added reference to Greaves, Koolen and Park. Corrected name of Chi Hoi Yip in acknowledgements