Diameter bounds for planar graphs |
| |
| Authors: | Radoslav Fulek Filip Mori? David Pritchard |
| |
| Affiliation: | aEcole Polytechnique Fédérale de Lausanne, SB IMB DCG, MA C1 567, Station 8 - Bâtiment MA, CH-1015 Lausanne, Switzerland;bEcole Polytechnique Fédérale de Lausanne, SB IMB DCG, Station 8 - Bâtiment MA, CH-1015 Lausanne, Switzerland;cEcole Polytechnique Fédérale de Lausanne, SB IMA DISOPT, Station 8, CH-1015 Lausanne, Switzerland |
| |
| Abstract: | The inverse degree of a graph is the sum of the reciprocals of the degrees of its vertices. We prove that in any connected planar graph, the diameter is at most 5/2 times the inverse degree, and that this ratio is tight. To develop a crucial surgery method, we begin by proving the simpler related upper bounds (4(|V|−1)−|E|)/3 and 4|V|2/3|E| on the diameter (for connected planar graphs), which are also tight. |
| |
| Keywords: | Planar graph Diameter Inverse degree Conjecture-generating program Surgery argument Diameter bound |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
