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?

  • 1
    $\begingroup$ Might be related that McKay's "nauty" can enumerate non-isomorphic k-regular graphs on n vertices. $\endgroup$ – joro Sep 1 '15 at 11:34

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.

  • $\begingroup$ Thank you! The paper of Ding and Chen looks very interesting. I came to the problem through a geometric question where 4-regular simple graphs were examples of the relevant class of graphs. I realised I could give a result generating 4-regular simple graphs, but found a better characterisation was already known. So I wondered if it was worth trying to adapt my technique to 5- or 6-regular. Since my application requires simplicity I will leave the question open, for a while, in case anyone can help with that. $\endgroup$ – user62562 Sep 1 '15 at 14:49
  • 1
    $\begingroup$ @user62562 : See my addition. $\endgroup$ – Brendan McKay Sep 2 '15 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.