Bounds on the Metric Dimensions for Families of Planar Graphs

Overview

The concept of metric dimension has applications in a variety of fields, such as chemistry, robotic navigation, and combinatorial optimization. Three bounds on the metric dimensions for different families of planar graphs based on the number of vertices are discussed. The first two results concern outerplanar graphs: Hamiltonian outerplanar graphs have a metric dimension of at most half the number of vertices, and outerplanar graphs in general have a metric dimension of at most two-thirds the number of vertices. The final result deals with maximal planar graphs, which have a metric dimension of at most three-fourth the number of vertices. It is conjectured that the metric dimension of maximal planar graphs in general is at most two-fifth the number of vertices. Applications of the results in various fields are discussed.

Awards (1)

• Second Award of $2,000 $2,000

Competition history

• ISEF 2017 Mathematics · Entry MATH025T

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.