Largest planar graphs and largest maximal planar graphs of diameter two

作者:

Highlights:

摘要

Let fk(Δ) be the maximum number of vertices in a planar graph with diameter k and maximum degree Δ. Let gk(Δ) be the maximum number of vertices in a maximal planar graph with diameter k and maximum degree Δ. Seyffarth has shown that g2(Δ)=⌊3Δ/2+1⌋ for Δ⩾8. Hell and Seyffarth have shown that f2(Δ)=⌊3Δ/2+1⌋ for Δ⩾8. We compute the exact maximum number of vertices in a planar graph and a maximal planar graph with diameter two and maximum degree Δ, for Δ<8.

论文关键词:Maximum degree,Planar graph,Maximal planar graph

论文评审过程:Received 11 January 2001, Revised 25 May 2001, Available online 31 October 2001.

论文官网地址:https://doi.org/10.1016/S0377-0427(01)00572-6