On the minimal doubly resolving sets of Harary graph

Main Article Content

Ali Ahmad Martin Bača Saba Sultan


Consider a simple connected undirected graph $G=(V_{G},E_{G})$, where $V_{G}$ represents the vertex set and $E_{G}$ represents the edge set respectively. A subset $B\subseteq V_{G}$ is called a resolving set if for every two distinct vertices $x,y$ of $G$, there is a vertex $v$ in set $B$ such that$d(x,v)\neq d(y,v)$. The resolving set of minimum cardinality is called metric basis of graph $G$. This minimal cardinality of metric basis is denoted by $\beta(G)$, and is called metric dimension of G. A subset $D$ of $V$ is called doubly resolving set if for every two vertices $x,y$ of $G$, there are two vertices $u,v\in D$ such that $d(u,x)-d(u,y)\neq d(v,x)-d(v,y)$. A doubly resolving set with minimum cardinality is called minimal doubly resolving set. This minimum cardinality is denoted by $\psi(G)$.\par Borchert and Gosselin et al. solved the problem of finding metric dimension for Harary graph $H_{4,n}$, $n\geq 8$. In this paper, we find the minimal doubly resolving set for Harary graph $H_{4,n}$, $n\geq 8$.
We prove that $\psi(H_{4,n})=\beta(H_{4,n})=\begin{cases} 3,\ if\ n \not\equiv 1(mod\ 4);\\ 4,\ otherwise.\end{cases}$

Article Details

How to Cite
Ahmad, A., Bača, M., & Sultan, S. (2019). On the minimal doubly resolving sets of Harary graph. Acta Mathematica Universitatis Comenianae, 89(1), 123-129. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1032/795