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.

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