Quines, Carl Joshua (School: Blackebergs Gymnasium)
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.
Second Award of $2,000