  A network topology with low average shortest path length (ASPL) provides
efficient data transmission while the number of nodes and the number of links
incident to each node are often limited due to physical constraints. In this
paper, we consider the construction of low ASPL graphs under these constraints
by using stochastic local search (SLS) algorithms. Since the ASPL cannot be
calculated efficiently, the ASPL is not suitable for the evaluation function of
SLS algorithms. We first derive an equality and bounds for the ASPL of graphs
of diameter 3. Then, we propose use the simpliest upper bound represented by
the number of triangles and squares in the graph as an evaluation function for
graphs of diameter 3. We show that the proposed evaluation function can be
evaluated in O(1) time as the number of nodes and the maximum degree tend to
infinity by using some data tables. By using the simulated annealing with the
proposed evaluation function, we construct low ASPL regular graphs of diameter
3 with 10 000 nodes.
