-4
$\begingroup$

Is there currently an algorithm that given the number of vertices / nodes n, and the number of edges per node l, output all graph edges?

If not, is there an algorithm that can tell if such graph is possible?

In both cases, this is an undirected, loop-free graph.

$\endgroup$

closed as off-topic by Mark Sapir, Alexey Ustinov, Henry.L, Chris Godsil, Stefan Kohl Jul 5 '17 at 15:22

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Mark Sapir, Alexey Ustinov, Henry.L, Chris Godsil, Stefan Kohl
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Such a graph is not unique, not even up to isomorphism. Thus, it would be hard to find an algorithm to generate "the graph". Take for example two triangles and a circle on six points: In both graphs, you have six points and every point has degree two. $\endgroup$ – Dirk Jun 29 '17 at 10:20
  • 1
    $\begingroup$ Is it then possible to generate a graph with such properties? Just any graph. Thanks! $\endgroup$ – DaKnOb Jun 29 '17 at 10:21
  • 1
    $\begingroup$ Possible: Yes, this is a finite problem. However, I don't know of an algorithm to do it, so you either have to wait for someone else to come up with one or design one yourself. $\endgroup$ – Dirk Jun 29 '17 at 10:30
  • 1
    $\begingroup$ So far I've figured a way to make this work with a given l, but n must be restricted to (multiples of) 2^l. Thanks a lot of the help. Let's wait and see. $\endgroup$ – DaKnOb Jun 29 '17 at 10:36
  • $\begingroup$ Use a circulant graph: en.wikipedia.org/wiki/Circulant_graph which works for every $\ell,n$ such that $0\le\ell\le n-1$ and $\ell n$ is even. If $\ell n$ is odd, no graph exists. $\endgroup$ – Brendan McKay Jun 29 '17 at 14:50
3
$\begingroup$

From the comments, you want every node to have the same weight. This is of course only possible if $n \geq \ell + 1$. Now assume we have such parameters. Pick $\ell+1$ vertices and form a complete graph on them. Continue, until you only have $k \leq \ell$ vertices left. Now there are two cases:

  1. $\ell - k$ is odd. Then form a complete graph on the remaining $k$ vertices, now every remaining is still missing $\ell - k-1$ edges, an even number. Remove an edge $(v,w)$ from the previous graphs and connect a remaining vertex to both $v$ and $w$, until everyone has the desired degree. You will have to remove $$\frac{k(\ell - k)}{2}$$ edges, which is possible, as each complete graph generated before contains $$\frac{\ell(\ell+1)}{2}$$ edges.
  2. $\ell - k$ is even. Then do not form the complete graph but rather connect every vertex directly to $\ell$ vertices by removing edges. Once again, there are enough edges to remove. This only works if $\ell$ is even, but we can assume $\ell$ even due to the handshaking lemma, which states that if $\ell$ and $n$ are both odd, then such a graph does not exist.
$\endgroup$

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