Fast recognition of some parametric graph families

Abstract

We identify all $[1,\lambda ,8]$-cycle regular $I$-graphs and all $[1,\lambda ,8]$-cycle regular double generalized Petersen graphs. As a consequence we describe linear recognition algorithms for these graph families. Using structural properties of folded cubes we devise a $o(N\log N)$ recognition algorithm for them. We also study their $[1,\lambda ,4]$, $[1,\lambda ,6]$ and $[2,\lambda ,6]$-cycle regularity and settle the value of parameter $\lambda$.

33 pages, 11 figures