Graphs with mixed metric dimension three and related algorithms

Abstract

Let $ G = (V, E) $ be a simple connected graph. A vertex $ x\in V(G) $ resolves the elements $ u, v\in E(G)\cup V(G) $ if $ d_G(x, u)\neq d_G(x, v) $. A subset $ S\subseteq V(G) $ is a mixed metric resolving set for $ G $ if every two elements of $ G $ are resolved by some vertex of $ S $. A set of smallest cardinality of mixed metric generator for $ G $ is called the mixed metric dimension. In this paper trees and unicyclic graphs having mixed dimension three are classified. The main aim is to investigate the structure of a simple connected graph having mixed dimension three with respect to the order of graph, maximum degree of basis elements and distance partite sets of basis elements. In particular to find necessary and sufficient conditions for a graph to have mixed metric dimension 3. Moreover three separate algorithms are developed for trees, unicyclic graphs and in general for simple connected graph $ J_{n}\ncong P_{n} $ with $ n\geq 3 $ to determine "whether these graphs have mixed dimension three or not?". If these graphs have mixed dimension three, then these algorithms provide a mixed basis of an input graph.

Keywords

• metric dimension
• fractional metric dimension
• modified prism networks