Bounds on the Metric Dimensions for Families of Planar Graphs
ISEF · 2017 Mathematics Second Award
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
Resources
Related projects
ISEF · 2014
The Speeds of Families of Intersection Graphs
ISEF · 2016
Graph Rigidity in L1 and Kusner's Conjecture
ISEF · 2023
Extremal Problems on the Steiner k-Distance and the Steiner k-Wiener Index
ISEF · 2017
A 6-Chromatic Unit Distance Graph in Space
ISEF · 2022
Minimal Number of Monochromatic Edges in Bicolored Graphs
ISEF · 2017
On the Distortion of Embedding Perfect Binary Trees into Low-Dimensional Euclidean Spaces
ISEF · 2020
On the Properties of Knots and Links Constructed from Plane Graphs
ISEF · 2020
Generalizing the Formulae for the Wiener Indices of the Double Vertex Graphs of Certain Families of Graphs
Closest projects by meaning, across every fair and year in the corpus.
Browse more like this
Source: Regeneron International Science and Engineering Fair