Some resolving parameters with the minimum size for two specific graphs

Abstract

A resolving set for a graph $G$ is a set of vertices $Q=\{q_1,...,q_k\}$ such that, for all $p\in V(G)$ the $k$-tuple $(d(p,q_1),...,d(p,q_k))$ uniquely determines $p$, where $d(p,q_i)$ is considered as the minimum length of a shortest path from $p$ to $q_i$ in graph $G$. In this paper, we consider the computational study of some resolving sets with the minimum size for the $m$-cylinder graph $(C_n\square P_k)\square P_m$. The Boolean lattice $B{L}_n$, $n\ge 1$, is the graph whose vertex set is the set of all subsets of $[n]=\{1,2,...,n\}$, where two subsets $X$ and $Y$ are adjacent if their symmetric difference has precisely one element. In the graph $B{L}_n$, the layer $L_i$ is the family of $i$-subsets of $[n]$. The subgraph $B{L}_n(i,i+1)$ is the subgraph of $B{L}_n$ induced by layers $L_i$ and $L_{i+1}$. Usually the graph $B{L}_n(1,2)$ is denoted by $H(n)$. We study the minimum size of a resolving set, doubly resolving set and strong resolving set for the graph $L(n)$, which is the line graph of $H(n)$.

For personal reasons, Professor Liu asked us not to mention his name in the article and to thank him only in the acknowledgments section