1
$\begingroup$

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?

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

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Sep 1, 2015 at 14:49
  • 1
    $\begingroup$ @user62562 : See my addition. $\endgroup$
    – Brendan McKay
    Commented Sep 2, 2015 at 0:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .