On The Simultaneous Metric Dimension Of Graph Families
On The Simultaneous Metric Dimension Of Graph Families
Mohammadesmail Nikfar1
1) Associate Professor, Ph.D. in Mathematics, Department of Mathematics, School of Hekmat 1, District 4, Tehran, Iran.
IOI Code
:
ADEZ-ACAEHB
Publication :
MS Thesis. 2016.(pre-2392277)
Abstract :
Let $G = (V, E)$ be a connected graph. A set $S \subseteq V$ is called a *resolving set* for $G$ if, for every pair of distinct vertices $x, y \in V$, there exists at least one element $v \in S$ such that $d_G(v, x) \neq d_G(v, y)$. The smallest resolving set is called a *metric basis* of $G$, and its cardinality is denoted by $\dim(G)$, known as the *metric dimension*. Consider a family of graphs $\mathcal{F} = \{G_1, G_2, \dots, G_k\}$ defined on the same vertex set $V$. A set $S \subseteq V$ is called a *simultaneous resolving set* for the family $\mathcal{F}$ if $S$ is a resolving set for every graph $G_i \in \mathcal{F}$. The smallest such set is called a *simultaneous metric basis*, and its cardinality is referred to as the *simultaneous metric dimension*. In this thesis, we derive exact bounds for the simultaneous metric dimension of graphs. We then examine specific families of graphs, providing exact values or bounds for their simultaneous metric dimension. Furthermore, we describe an algorithm to determine the simultaneous metric dimension for a given graph $G$. We also establish a lower bound for the maximum number of graphs in a family that share a common simultaneous metric basis. Finally, we investigate a family consisting of two graphs, where one is obtained from the other via an edge-shifting operation. Furthermore, the problem of determining the simultaneous metric dimension of a family of trees has been shown to be NP-hard. An exact algorithm is presented for this problem; moreover, in cases where the family is derived from an initial tree, precise upper and lower bounds are established. A sequence of edge-based transformations is also introduced.
Keywords : metric dimension simultaneous metric dimension simultaneous metric generator family of trees bound