Largest planar graphs and largest maximal planar graphs of diameter two
- Yang, Yuansheng
- Lin, Jianhua
- Dai, Yongjie
DOIAbstract
AbstractLet 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
Add to ORKG