How many non-isomorphic classes of regular graphs on $(2n+1)^{m}$ vertices with $m(2n+1)^{m}$ edges with vertex degree $2m$, where $n,m \in \mathbb{N}$ are there? Is there a classification known? Can there can be more than one such class (that is are they all isomorphic)?

Is there an example of such non-isomorphic graphs if there are any?

  • $\begingroup$ Since for regular graphs, number of vertices times degree is twice the number of edges, your condition implies $m=1$? Either there is a typo or this looks like homework. $\endgroup$ – Chris Godsil Nov 29 '11 at 17:44
  • $\begingroup$ @Chris this is not a hw. Corrected! $\endgroup$ – user16007 Nov 29 '11 at 17:52
  • $\begingroup$ If you don't assume connected, then there are many non-isomorphic examples. For example, for $m=1$ and $n=3$ the 7-cycle and the disjoint union of a 4-cycle and a 3-cycle are not isomorphic. $\endgroup$ – Tony Huynh Nov 29 '11 at 18:41

The asymptotic number of $m$-regular graphs on $N$ vertices is well understood and can be found, for example, in Bollobas' Random Graphs (the argument uses Bollobas' "configuration model"). With probability $1$ a graph has no automorphisms, so this is also the number of isomorphism classes as long as $N$ is large. In your case $N=(2n+1)^m.$ So, for a reasonably sized $n$ (since yours is a natural number, $n>0$ should be fine), if you pick two random graphs, they will be non-isomorphic.

  • 4
    $\begingroup$ Degree at least 3 is needed. Also, you might like to divide by $N!$ to convert the asymptotic number of labelled graphs into the asymptotic number of isomorphism classes. This is ok since the number of graphs grows faster than $N!$. In my answer at mathoverflow.net/questions/77730 I surveyed what is known about this enumeration problem. $\endgroup$ – Brendan McKay Nov 29 '11 at 23:53

For the connected case see http://oeis.org/A068934.

For example, there are two non-isomorphic connected 3-regular graphs with 6 vertices.

alt text

  • $\begingroup$ I am interested in seeing the 5-vertex example you mention, primarily because I don't think one exists. Gerharrd "Ask Me About System Design" Paseman, 2011.11.29 $\endgroup$ – Gerhard Paseman Nov 29 '11 at 21:58
  • $\begingroup$ Also, the pictures you have above suggest how to build two connected 12,4 examples. Gerhard "Ask Me About System Design" Paseman, 2011.11.29 $\endgroup$ – Gerhard Paseman Nov 29 '11 at 22:01
  • $\begingroup$ $5=6{}{}{}{}{}$? $\endgroup$ – Gerry Myerson Nov 29 '11 at 22:07
  • 2
    $\begingroup$ It is the limit as $5\rightarrow 6.$ $\endgroup$ – Igor Rivin Nov 30 '11 at 4:16
  • $\begingroup$ Sorry for the typo. Edited it. $\endgroup$ – Robert Israel Dec 1 '11 at 5:17

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.