Minimum Metric Dimension of Iliac Networks

Abstract

Let $M=\{v_1,v_2,\dots ,v_n\}$ be an ordered set of vertices in a graph $G$. Then, $(d(u,v_1),d(u,v_2),\dots ,d(u,v_n))$ is called the $M$-coordinates of a vertex $u$ of $G$. The set $M$ is called a $metricbasis$ if the vertices of $G$ have distinct $M$-coordinates. A minimum metric basis is a set $M$ with minimum cardinality. The cardinality of a minimum metric basis of $G$ is called the minimum metric dimension. This concept has wide applications in motion planning and robotics. In this paper, we solve the minimum metric dimension problem for Illiac networks.