Are constructive characterisations of k-regular (simple) graphs known? By a constructive characterisation I mean a theorem giving a list of base graphs and a list of operations such that every graph in a given class is generated from the base graphs by applying some sequence of these operations and every intermediate graph is also in the class.
For 3-regular graphs I found the paper "Inductive classes of cubic graphs" by V Batagelj in 1981. http://vlado.fmf.uni-lj.si/vlado/papers/cubicEger.pdf
For 4-regular graphs there is a paper in French: "Construction of 4-regular graphs" by Bories and Jolivet in 1983.
I have been unable to find corresponding results for 5-regular graphs or 6-regular graphs or higher. It seems like a quite natural question, so I'd be surprised if nothing was known but I haven't been able to find any references myself.
Are there known constructive characterisations of k-regular (simple) graphs for any integer $k\geq 5$?
If not, can anyone give some intuition for why such results would be hard? Any interesting applications?
 A: It's a good question for someone with a better memory than mine!
There are two papers giving such constructions for regular multigraphs without loops.  One is Ding and Chen, Generating r-regular graphs, Discrete Applied Mathematics 129 (2003) 329–343.  The other is a preprint of Carstens and Steffen, see here ; I don't know if it was published.
Ding and Chen discuss the (much) more difficult case of simple regular graphs, but don't solve it. I don't recall if anyone else did either.
If you just need to generate simple regular graphs of high degree, a program of Markus Meringer is good. I can give it to you if you ask privately (bdm AT cs.anu.edu.au).
ADDED: The simplest construction operation for simple quartic graphs is to pinch together the middles of two non-adjacent edges to make a new vertex. The irreducible graphs are easy to characterise.  This has been rediscovered a number of times and my student Narjess Afzaly  made a very fast program from it (not published yet).  The same idea, using more edges, can work in principle for any even degree but I don't know if anyone figured out the irreducible graphs for degrees greater than 4.  I think the number of irreducible graphs will explode.
