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?



Are constructive characterisations of k-regular (simple) graphs known?
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](https://www.math.uni-bielefeld.de/sfb343/preprints/pr94004.ps.gz) ; 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.


