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