Largest planar graphs of diameter $3$ and fixed maximum degree -- connection with fractional matchings

Abstract

The degree diameter problem asks for the maximum possible number of vertices in a graph of maximum degree $\hat{I}”$ and diameter $D$. In this paper, we focus on planar graphs of diameter $3$. Fellows, Hell and Seyffarth (1995) proved that for all $\hat{I}”\ge 8$, the maximum number ${\mathrm{np}}_{\hat{I}”,D}$ of vertices of a planar graph with maximum degree at most $\hat{I}”$ and diameter at most 3 satisfies $\frac{9}{2}\hat{I}”-3\le {\mathrm{np}}_{\hat{I}”,3}\le 8\hat{I}”+12$. We show that the lower bound they gave is optimal, up to an additive constant, by proving that there exists $c>0$ such that ${\mathrm{np}}_{\hat{I}”,3}\le \frac{9}{2}\hat{I}”+c$ for every $\hat{I}”\ge 0$. Our proof consists in a reduction to the fractional maximum matching problem on a specific class of planar graphs, for which we show that the optimal solution is $\frac{9}{2}$, and characterize all graphs attaining this bound.

42 pages, 18 figures