Circulant graphs can be used to realize the $\lfloor n\Delta/2 \rfloor$ bound in a large number of cases, and in the other cases, we can modify them slightly to achieve this bound.
- When $n$ is even and $\Delta$ is even (so $\Delta \leq n-2$), we pick a set of distances comprising $\Delta/2$ distances in $\{1,2,\ldots,n/2-1\}$.
For example, when $n=10$ and $\Delta=6$, we can take the distances $\{1,2,3\}$, which gives:
![$n=10$ and $\Delta=6$ case](https://i.stack.imgur.com/ONYoF.png)
- When $n$ is even and $\Delta$ is odd, we pick a set of distances comprising $(\Delta-1)/2$ distances in $\{1,2,\ldots,n/2-1\}$ and $n/2$.
For example, when $n=10$ and $\Delta=5$, we can take the distances $\{1,2,5\}$, which gives:
![$n=10$ and $\Delta=5$ case](https://i.stack.imgur.com/YWOEo.png)
- When $n$ is odd and $\Delta$ is even we pick a set of distances comprising $\Delta/2$ distances in $\{1,2,\ldots,(n-1)/2\}$.
For example, when $n=11$ and $\Delta=6$, we can take the distances $\{2,3,4\}$, which gives:
![$n=11$ and $\Delta=6$ case](https://i.stack.imgur.com/r8jRX.png)
Finally, when $n$ is odd and $\Delta$ is odd (so $\Delta \leq n-2$), $n\Delta/2$ is not an integer, so we can't achieve the maximum with circulant graphs. The best we could possibly do is $\lfloor n\Delta/2 \rfloor$. To achieve this:
We take a $(\Delta-1)$-regular graph as above, but do not take distance $1$ edges (we need to take at most $(\Delta-1)/2 \leq (n-3)/2$ distances, so this is possible).
We observe that the edges of distance $1$ form a Hamilton cycle in the complement of the graph. We pick $(n-1)/2$ disjoint edges from this Hamilton cycle (i.e., no two edges share an endpoint), and add them to our construction.
For example, when $n=11$ and $\Delta=7$, we can take the above $6$-regular graph and add in edges around the outside as follows:
![$n=11$ and $\Delta=7$ case](https://i.stack.imgur.com/uOORG.png)
This gives $\lfloor n\Delta/2 \rfloor$ edges in every case (as expected).
Best Answer
An upper bound is $\frac 13{m \choose 2}=\frac {m(m-1)}6$ because at the most you can choose any two edges and have one triangle, then each triangle gets counted $3$ times.