2024/01/20 by Preez, Brandon Du · 1 citation
#05C12 (Primary) 05C10 #05C35 (Secondary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2401.11187
The degree-diameter problem consists of finding the maximum number of vertices n of a graph with diameter d and maximum degree Δ. This problem is well studied, and has been solved for plane graphs of low diameter in which every face is bounded by a 3-cycle (triangulations), and plane graphs in which every face is bounded by a 4-cycle (quadrangulations). In this paper, we solve the degree diameter problem for plane graphs of diameter 3 in which every face is bounded by a 5-cycle (pentagulations). We prove that if Δ≥ 8, then n ≤ 3Δ- 1 for such graphs. This bound is sharp for Δ odd.