ریاضی و جامعه (Oct 2023)
Resolving sets of vertices with the minimum size in graphs
Abstract
Suppose that $G$ is a simple connected graph with vertex set $V(G)$ and edge set $E(G)$. A subset $S=\{s_1, s_2,\ldots , s_l \}$ of vertices of graph $G$ is called a doubly resolving set of $G$, if for any distinct vertices $u$ and $v$ in $G$ there are elements $x$ and $y$ in the set $S$ such that $d(u, x)-d(u, y)\ne d(v, x)-d(v, y)$. The minimum size of a doubly resolving set of the vertices of graph $G$ is denoted by ${\psi} (G)$. In this paper, we calculate the resolving sets of vertices with the minimum size for the line graph $L(C_n\circ{\overline{K}}_m)$ and graph $\left((C_n\circ{\overline{K}}_m)\square P_k\right)$, in which the symbols $\circ$ and $\square$ denote the Corona product and Cartesian product between two graphs, respectively. In particular, we show that if $n\geq 3$ and $m, k\geq 2$ are integers, then ${\psi}((C_n\circ{\overline{K}}_m)\square P_k )={\psi}(C_n\circ{\overline{K}}_m)+{\psi}(P_k )-1$, which gives a partial answer to the problem of characterizing graphs $G$ and $H$ satisfying the equality ${\psi}(G\square H)={\psi}(G)+{\psi}(H)-1$, which is recently posed in [K. Nie and K. Xu, The doubly metric dimension of cylinder graphs and torus graphs, Bull. Malays. Math. Sci. Soc., 46 (2023) 19 pp]. 1. IntroductionLet $G$ be a simple and connected graph with the set of vertices $V(G)$ and the set of edges $E(G)$. We denote the length of the shortest path between two vertices $u$ and $v$ in the graph $G$ by $d(u, v)$. We use $C_n$, $\overline{K_m}$ and $P_k$ to denote the cycle graph of order $n$, complement of the complete graph on $m$ vertices and the path graph of order $k$, respectively. Also, the line graph $G$ is denoted by $L(G)$, that the set of vertices of $L(G)$ are the same as the edges of the graph $G$, and two vertices are adjacent in the graph $L(G)$, if their corresponding edges in graph $G$ have a common vertex [6]. Our goal is to calculate some resolving sets depending on the line graph of the Corona product $C_{n}\circ \overline{K_{m}} $ and the Cartesian product $(C_{n}\circ \overline{K_{m}} )\square P_{k}$, so we give first some explanations about the Corona product and Cartesian product of graphs. Suppose $G$ and $H$ are two graphs with $n$ and $m$ vertices, respectively. If we consider $n$ copies of $H$ and for $i=1, 2,\cdots ,n$, all the vertices of the $i^{th}$ copy of $H$ are adjacent to the vertex $i$ of $G$, then the desired graph is called the Corona product of two graphs $G$ and $H$ and we denote it by $G\circ H$. Also, if $G$ and $H$ are two graphs, we denote the Cartesian product of these graphs by $G \square H$ or $G \times H$ and define in this way $V\left(G\square H\right)=V(G)\times V(H)$ and two vertices $(g, h)$ and $(g',h')$ in $G\square H$ are adjacent if and only if $g=g'$ and $hh'\in E(H)$ or $h=h'$ and $gg'\in E(G)$. For any ordered subset $S=\{ s_{1}, s_{2},\cdots,s_{k}\}$ of the vertices of graph $G$ and the vertex $v$ of $G$, representation the vertex $v$ with respect to the ordered set $S$ denoted by $r(v{|S)}$ and so it is $ r(v{|S)}=\left({d}\left(v, s_1\right),{d}\left(v, s_2\right),\ldots,{d}\left(v, s_k\right)\right)$. If all the vertices of the graph $G$ have distinct metric representations with respect to the ordered set $S$, then $S$ is called a resolving set of vertices of $G$. A resolving set of vertices of $G$ with the minimum size is called the metric dimension of the graph $G$ and it is represented by ${\beta }\left(G\right)$. The study of resolving set of vertices in graph theory dates back to the 1970s, and such concepts were first introduced in the articles [7,18]. The metric dimension of complete graphs, trees, paths, and the Cartesian product have been taken into consideration, also in the article [5] all graphs of order $n$ that have the metric dimension greater than or equal to $n-2$ are fully characterised. The subset $ S=\{s_{1},s_{2},\cdots,s_{l}\}$ of the vertices of graph $G$ is called a doubly resolving set for $G$, if for any distinct pair vertices $u$ and $v$ of $G$, there are the elements $x$ and $y$ of $S$, in which $d(u, x)-d(u, y)\ne d(v, x)-d(v, y)$. We denote the size of the minimum doubly resolving set in graph $G$ by ${\psi}\left(G\right) $. Concepts related to resolving sets and doubly resolving sets of graphs have been studied in the articles [4,5]. The graph $(C_5\circ \overline{K}_{3})$ and graph $L(C_{5}\circ \overline{K}_{3})$ are drawn in Figure 1. Also, the graph $(C_3\circ \overline{K}_{3})$ and graph $(C_{3}\circ \overline{K}_{3})\square P_{2}$ are drawn in Figure 2. 2. Main ResultsTheorem 2.1. If $n$ and $m$ are fixed positive integers, in which $n\geq 3$, $m\geq 2$, then the cardinality of minimum doubly resolving set of the line graph of graph $C_n\circ{\overline{K}}_m$ is $nm-n$. Theorem 2.2. If $n$, $m$ and $k$ are fixed positive integers, in which $n\geq 3$ and $m, k\geq 2$, then ${\beta }((C_n\circ{\overline{K}}_m)\square P_k )=nm-n+1.$ Theorem 2.3. If $n$, $m$ and $k$ are fixed positive integers, in which $n\geq 3$ and $m, k\geq 2$, then ${\psi }\left((C_n\circ \overline{K}_{m})\square P_{k}\right)={\psi } (C_n\circ \overline{K}_{m})+{\psi }(P_{k})-1.$ 3. ConclusionsConsidering the importance of the minimum resolving sets in graphs, in this paper, we first calculated some resolving sets of vertices with the minimum size for the line graph of graph $C_n\circ{\overline{K}}_m$ and graph $\left((C_n\circ{\overline{K}}_m)\square P_k\right)$. In particular, we show that if $n\geq 3$ and $m, k\geq 2$ are integers, then ${\psi}((C_n\circ{\overline{K}}_m)\square P_k )={\psi}(C_n\circ{\overline{K}}_m)+{\psi}(P_k )-1$, which gives a partial answer to the problem of characterizing graphs $G$ and $H$ satisfying the equality ${\psi}(G\square H)={\psi}(G)+{\psi}(H)-1$, which is recently posed in [15].
Keywords
