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 4V^2/3E on the diameter (for connected planar graphs), which are also tight.
Recommendations
- Approximating the Diameter of Planar Graphs in Near Linear Time
- Approximating the diameter of planar graphs in near linear time
- Sharp Bounds on the Diameter of a Graph
- Diameters of finite upper half plane graphs
- Diameter Bounds for Graph Extensions
- On the diameter of random planar graphs
- On the diameter of random planar graphs
- scientific article; zbMATH DE number 7587174
- scientific article; zbMATH DE number 3878961
- Diameter bounds for geometric distance-regular graphs
Cites work
Cited in
(13)- The Plancherel measure for polygonal graphs
- On diameter and inverse degree of chemical graphs
- Computing the Inverse Geodesic Length in Planar Graphs and Graphs of Bounded Treewidth
- scientific article; zbMATH DE number 1262798 (Why is no real title available?)
- Existential closure in line graphs
- On the diameter and inverse degree.
- Distances in graphs of girth 6 and generalised cages
- The plane-width of graphs
- Approximating the Diameter of Planar Graphs in Near Linear Time
- Distances and cuts in planar graphs
- Diameter determination on restricted graph families
- Steiner diameter of 3, 4 and 5-connected maximal planar graphs
- On diameter and inverse degree of a graph
This page was built for publication: Diameter bounds for planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q626784)
