Resolvability in Wheel Related Graphs and Nanostructures

Abstract

Resolvability in graphs has appeared in numerous applications of graph theory, e.g. in pattern recognition, image processing, robot navigation in networks, computer sciences, combinatorial optimization, mastermind games, coin-weighing problems, etc. It is well known fact that computing the metric dimension for an arbitrary graph is an NP-complete problem. Therefore, a lot of research has been done in order to compute the metric dimension of several classes of graphs. Apart from calculating the metric dimension of graphs, it is natural to ask for the characterization of graph families with respect to the nature of their metric dimension. In this thesis, we study two important parameters of resolvability, namely the metric dimension and partition dimension. Partition dimension is a natural generalization of metric dimension as well as a standard graph decomposition problem where we require that distance code of each vertex in a partition set is distinct with respect to the other partition sets. The main objective of this thesis is to study the resolving properties of wheel related graphs, certain nanostructures and to characterize these classes of graphs with respect to the nature of their metric dimension. We prove that certain wheel related graphs and convex polytopes generated by wheel related graphs have unbounded metric dimension and an exact value of their metric dimension is determined in most of the cases. We also study the metric dimension and partition dimension of 2-dimensional lattices of certain nanotubes generated by the tiling of the plane and prove that these 2-dimensional lattices of nanotubes have discrepancies between their metric dimension and partition dimension. We also compute the exact value of metric dimension for an infinite class of generalized Petersen networks denoted by P(n; 3) by giving answer to an open problem raised by Imran et al. in 2014, which complete the study of metric dimension for the class of generalized Petersen networks P(n; 3).