# How to create a dense graph, when each node has a limited number of edges?

I am working on an application that needs to connect $n$ disconnected nodes, where each node can have at most $m$ edges, such that when traveling from the $ith$ node in graph to the $jth$ node, the highest number of edges covered is minimum and mapping cost is also minimum.

For example: If $n=5$ and $m=3$, there are 2 possible graphs that are the solution

In both the graphs, the longest path from one node to another is of length 2

For example: If $n=6$ and $m=3$, there are 2 possible graphs that are the solution (and I've added one more, to show the incorrect graph)

In all three graphs, the longest path from one node to another is of length 2. However, if you were to add up the number of edges traveled, you'd get 22, but the graphs on left and right add up to 21, i.e., even though the longest distance between 2 nodes is of 2 edges, the total cost of mapping the graph is more than the optimal solution.

(mapping cost = sum of distances between nodes $a-b, a-c...a-f, b-c, b-d...b-f$ and so on till $e-f$)

I'd like to know if there is a way to create such a graph layout mathematically (or programmatically) for givel values of $n$ and $m$, because drawing graphs by hand and testing is impossible?

• Did you have a question? – Perry Elliott-Iverson Oct 30 '15 at 15:44
• question updated. I'd like to know if there is a way to create such a graph layout mathematically (or programmatically) for givel values of nn and mm, because drawing graphs by hand and testing is impossible? – zhirzh Oct 30 '15 at 15:51