2
$\begingroup$

I'm trying to find undirected random graphs $G(V,E)$ with $|V|$ = $d^2$ for $d \in \mathbb{N}$ such that $\forall v \in V: deg(v) = d$.

For $d \in 2\mathbb{N} +1$ this trivially is impossible as no such graph exists: The number of incidences (connections between vertices and edges) is given by $|V|\cdot d = d^3 = 8k^3 + 12k^2 + 6k + 1$ (for some $k$). As the number of incidences is always double the number of edges $|E| = d^3/2$ is a contradiction.

This argument however, doesn't work for $d \in 2\mathbb{N}$.

My first guess was just constructing a random graph would do, however, this can get stuck in a local maximum. For instance in $d = 2$:

+---+    example for
|  /     an incomplete
| /      graph that
|/       cannot be
+   +    completed

A similar example can be constructed for $d = 4$ leaving up to two unconnectable vertices (essentially by using a 4-HyperCube).

I strongly suspect that for each $d$ the number of valid graphs significantly outweigh the number of incomplete graphs, but I would like to know how likely it is to end up with an incomplete graph. And if there is a better way to find these graphs than the random algorithm above (which could perhaps be fixed by breaking apart incomplete graphs, but that would not be guaranteed to terminate).

$\endgroup$
  • $\begingroup$ Do you mean degree or edge-degree? it seems from your post that you mean degree. If so such a graph is called a regular graph. Also there is a mistake when you insert d=2k+1, it should say $8k^3$ $\endgroup$ – Martin Vatshelle Jul 1 '15 at 6:41
  • $\begingroup$ @MartinVatshelle: Yes, you're right, I meant regular graphs. Also fixed the 8. $\endgroup$ – bitmask Jul 1 '15 at 8:18
  • $\begingroup$ google.fr/… $\endgroup$ – Lamine Jul 1 '15 at 11:04
  • $\begingroup$ @Lamine, what is the point of the link? I see several research papers (as well as blog posts, etc), but no way to tell the most up-to-date or definitive answer to the question.... $\endgroup$ – usul Jul 1 '15 at 15:48
2
$\begingroup$

The standard simple way of generating random regular graphs is:

  • while the degree < d
    • choose a random perfect matching from the edges still possible to add to the graph
    • If no matching is possible, restart the process.

The problem with this is that the higher edge degree you want, the more likely it is for the algorithm to get stuck. I see many papers limiting themself to $|V|>d^3$, so I don't know if this process will work for you.

$\endgroup$
  • 1
    $\begingroup$ After thinking more about the problem I think I found a $n^2$-time and -space non-probabilistic algorithm that should work for all $d$ iff $|V|\cdot d$ is even and always terminates (even with an adversarial random number generator). I might post it after more scrutiny. $\endgroup$ – bitmask Jul 1 '15 at 16:11

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.