Consider all connected simple graphs with diameter $d = 2$ and maximal vertex degree $\Delta$. In my particular practical case $\Delta = 4$, but general problem is much more interesting — probably there exists a research on general case.

I know that, given $d = 2$ and $\Delta = 4$, the maximal number of vertexes in the proper graph is $V = 15$ (the corresponding graph is K3 * C5). The question is: given $V$, how can one find the proper $V$-vertex graph with *minimal* number of *edges*?

I wrote the simple brute-force program and found the answer for all $V \le 8$. But calculating it further using this approach is going to take a tremendous amount of time, so I decided to ask a community for any advices or links to researches. Thank you for any assistance.

P.S. Sorry, if my English wasn't understandable enough.