Abstract:
We compute the exact maximum size of a planar graph with diameter 2 and fixed maximum degree $\Delta\leq7$. To find the solution of the problem we use the irrelevant path method. It is proved that the known graphs with size $2\Delta+1$ ($3\leq\Delta\leq4$) and $\Delta+5$ ($5\leq\Delta\leq7$) are the largest possible ones. This result completes the analysis of the degree–diameter problem for planar graphs of diameter 2. In the case $\Delta\leq6$, we found also the largest graphs of diameter 2 that are embedded into the projective plane and into the torus.