Exact metric and fault-tolerant metric dimensions of hexagonal and rectangular octahedral-cell tessellation graphs

Abstract A resolving set of a connected graph assigns distinct distance vectors to all vertices, while a fault-tolerant resolving set retains this property after deletion of any one selected vertex. We determine the corresponding minimum cardinalities for four infinite families of finite tessellation graphs assembled from octahedral cells, equivalently copies of $$K_{2,2,2}$$ : $$HT^1(n)$$ , $$HT^2(n)$$ , $$RT^1(m,n)$$ , and $$RT^2(m,n)$$ . Each family is defined as an octahedral expansion of an explicitly indexed triangular cell system. We characterize all nontrivial twin classes and prove, by means of strip-endpoint distance codes, that a boundary transversal of these classes resolves the entire graph. Consequently, for $$n\\geq2$$ , $$\\dim(HT^1(n))=6n$$ and $$\\dim(HT^2(n))=12n-6.$$ For $$m,n\\geq2$$ , $$\\dim(RT^1(m,n))=2m+n-1$$ when $$m$$ is even and $$n$$ is odd, and $$2m+n$$ otherwise. The family $$RT^2(m,n)$$ is isomorphic to $$RT^1(m,n)$$ unless $$m$$ is even and $$n$$ is odd; in the exceptional case, its metric dimension is $$2m+n+1.$$ Every nontrivial twin class has cardinality two, and the resolving transversal is optimal; hence the fault-tolerant metric dimension is twice the metric dimension in all four families. The proofs provide explicit optimal bases and explain the parity-sensitive rectangular exception.