3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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
    Commented Nov 29, 2011 at 17:44
  • $\begingroup$ @Chris this is not a hw. Corrected! $\endgroup$
    – user16007
    Commented Nov 29, 2011 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
    Commented Nov 29, 2011 at 18:41

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Nov 29, 2011 at 23:53
3
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\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
    Commented Nov 29, 2011 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
    Commented Nov 29, 2011 at 22:01
  • $\begingroup$ $5=6{}{}{}{}{}$? $\endgroup$
    – Gerry Myerson
    Commented Nov 29, 2011 at 22:07
  • 2
    $\begingroup$ It is the limit as $5\rightarrow 6.$ $\endgroup$
    – Igor Rivin
    Commented Nov 30, 2011 at 4:16
  • $\begingroup$ Sorry for the typo. Edited it. $\endgroup$
    – Robert Israel
    Commented Dec 1, 2011 at 5:17

You must log in to answer this question.

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