What is known about the number of labeled regular graphs on n vertices? The sequence does not appear to be in the OEIS.

For fixed $k$, the problem of counting $k$regular labeled graphs is not intractable at all; the counting sequence is Precursive, so in principle the sequence is (up to a constant factor) as easy to compute as it could be. (But the complexity grows quickly with $k$.) For $k\le 5$, see I. P. Goulden and D. M. Jackson, Labelled graphs with small vertex degrees and Precursiveness. SIAM J. Algebraic Discrete Methods 7 (1986), 6066. and for Precursiveness in the general case see my paper Ira M. Gessel, Symmetric functions and Precursiveness. J. Combin. Theory Ser. A 53 (1990), 257285. 

