Space efficient representation of Regular graphs
No.  Even ignoring the requirement to answer queries, you can't store such a graph in $o(nk)$ space, assuming each word is $\Theta(\lg n)$ bits long (i.e., each word has space to store the index of a single vertex).

In particular, there are ${n-1 \choose k}$ ways to choose $k$ neighbors of a single vertex, so there are ${n-1 \choose k}^n$ possible $k$-regular graphs.  Now

$$\lg {n-1 \choose k}^n = n \lg {n-1 \choose k} = kn \lg(n/k) + \Theta(kn) = \Omega(kn \lg(n/k)).$$

Thus, information-theoretically, you need at least $\Omega(kn \lg(n/k))$ bits to store such a graph, or equivalently, at least $\Omega(kn \lg(n/k)/\lg n)$ words.  Notice that for $k=O(\log n)$, we have $\lg(n/k)/\lg n = \Theta(1)$.

Therefore, we find that we need at least $\Omega(kn)$ words just to represent all possible $k$-regular graphs, so there is no hope for a data structure with space complexity $o(kn)$, even if you ignore the query time requirement.