Diameter bounds for planar graphs

DOI10.1016/J.DISC.2010.11.006MaRDI QIDQ626784zbMATH OpenOpenAlexFDO

Authors Juan-Miguel Gracia

Publication date 18 February 2011

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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

• scientific article; zbMATH DE number 4173028 (Why is no real title available?)
• scientific article; zbMATH DE number 4108815 (Why is no real title available?)
• On diameter and inverse degree of a graph
• The extremal function for complete minors

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

Describes a project that uses

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)