Abstract
The degree diameter problem asks for the maximum possible number of vertices in a graph of maximum degree ∆ and diameter D. In this paper, we focus on planar graphs of diameter 3. Fellows, Hell and Seyffarth (1995) proved that for all ∆ ⩾ 8, the maximum number np ∆,D of vertices of a planar graph with maximum degree at most ∆ and diameter at most 3 satisfies 9∆/2 -3 ⩽ np ∆,3 ⩽ 8∆ + 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 np ∆,3 ⩽ 9∆/2 + c for every ∆ ⩾ 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 9/2 , and characterize all graphs attaining this bound.