Diameter bounds for planar graphs

DOI10.1016/J.DISC.2010.11.006zbMATH Open1222.05034arXiv1006.2493OpenAlexW2160297724MaRDI QIDQ626784FDOQ626784

Authors: Juan-Miguel Gracia 

Publication date: 18 February 2011

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1006.2493

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

zbMATH Keywords

diameterinverse degreeplanar graphdiameter boundconjecture-generating programsurgery argument

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Connectivity (05C40)

Cites Work

• The extremal function for complete minors
• Title not available (Why is that?)
• Title not available (Why is that?)
• On diameter and inverse degree of a graph

Cited In (13)

• On diameter and inverse degree of chemical graphs
• Diameter determination on restricted graph families
• On diameter and inverse degree of a graph
• Computing the Inverse Geodesic Length in Planar Graphs and Graphs of Bounded Treewidth
• Existential closure in line graphs
• Approximating the Diameter of Planar Graphs in Near Linear Time
• Steiner diameter of 3, 4 and 5-connected maximal planar graphs
• On the diameter and inverse degree.
• Distances in graphs of girth 6 and generalised cages
• The Plancherel measure for polygonal graphs
• The plane-width of graphs
• Title not available (Why is that?)
• Distances and cuts in planar graphs

Uses Software

• GRAFFITI

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)