Loading...
research article
Diameter Bounds for Planar Graphs
2011
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(vertical bar V vertical bar - 1) - vertical bar E vertical bar)/3 and 4 vertical bar V vertical bar(2)/3 vertical bar E vertical bar on the diameter (for connected planar graphs), which are also tight. (C) 2010 Elsevier B.V. All rights reserved.
Loading...
Name
diam.pdf
Access type
openaccess
Size
224.45 KB
Format
Adobe PDF
Checksum (MD5)
b4e0563008cd24c33619dac98a4ebcff