COMPUTING THE SECURE CONNECTED DOMINANT METRIC DIMENSION PROBLEM OF CLASSES OF GRAPHS

Abstract

This paper investigates the NP-hard problem of finding the lowest secure connected domination metric dimension of graphs. If each vertex in $G$ can be uniquely recognized by its vector of distances to the vertices in Scddim, then every vertex set Scddim of a connected graph $G=(V, E)$ resolves $G$. If the subgraph induced by Scddim is a nontrivial connected subgraph of $G$, then the resolving set Scddim of $G$ is connected. That resolving set is dominating if each vertex in $G$ that is not an element of Scddim is a neighbor of some vertices in Scddim. If there is a $v$ in $D$ such that $(D-\{v\}) \cup\{u\}$ is a dominating set for any $u$ in $V-D$, then the dominating set $D$ is secure. If for every $s \in V-R$, there exists $r \in R$ such that $(R-\{r\}) \cup\{s\}$ is a resolving set, then the resolving set $R$ is secure. These four cardinality values are the metric dimension of $G$, the connected metric dimension of $G$, the secure metric dimension of $G$, and the connected domination metric dimension of $G$, respectively. They correspond to the cardinality of the smallest resolving set of $G$, the minimal connected resolving set, the minimal secure resolving set, and the minimal connected domination resolving set. In this paper, we introduce the secure connected domination metric dimension of graphs. If each vertex in G can be uniquely recognized by its vector of distances to   the vertices in Scddim, then every vertex set Scddim of a connected graph  resolves G. If the subgraph induced by Scddim is a nontrivial connected subgraph of G, then the resolving set Scddim of G is connected. That resolving set is dominating if each vertex in G that is not an element of Scddim is a neighbor of some vertices in Scddim. If there is a v in D such that  is a dominating set for any $u$ in  then the dominating set $D$ is secure. If for every  there exists  such that  is a resolving set, then the resolving set $R$ is secure. These four cardinality values are the metric dimension of $G$, the connected metric dimension of $G$, the secure metric dimension of $G$, and the connected domination metric dimension of G, respectively. They correspond to the cardinality of the smallest resolving set of $G$, the minimal connected resolving set, the minimal secure resolving set, and the minimal connected domination resolving set. In this paper, we introduce the secure connected dominant metric dimension of some graphs such as triangular snake graph, path graph, star tree and alternate quadrilateral snake. In particular, we derive the explicit formulas for the subdivision of triangular snake graph, alternate triangular snake graph, total graph of $P_n$  cycle graph and bistar tree.

Received: September 2, 2024
Accepted: December 10, 2024