Computing locating-total domination number in some rotationally symmetric graphs

Abstract

Let $G=(V,E)$ be a connected graph. A locating-total dominating set in a graph G is a total dominating set S of a G, for every pair of vertices $i,j\in V(G)\mathrm{\setminus }S$ , such that $N(i){\cap }^S\ne N(j){\cap }^S$ . The minimum cardinality of a locating-total dominating set is called locating-total domination number and represented as ${\gamma }_t^L$ . In this paper, locating-total domination number is determined for some cycle-related graphs. Furthermore, some well-known graphs of convex polytopes from the literature are also considered for the locating-total domination number.

Introduction

All graphs studied in this paper are simple, finite, and undirected. The concept of total domination (TD) plays a vital role when it appears to place the devices for observation purposes such that every site in a system is adjacent to an observer, and it can be designed by TD in graphs. If something goes wrong within the system, its location can be uniquely identified by the set of observers placed. Let G be the graph having the vertex set as $V(G)$ , and the edge set be $E(G)$ . For a vertex $v\in V(G)$ the open and close neighborhoods of v are denoted by $N_G(v)=\{u\in V|(uv)\in E\}$ , $N_G[v]=\{u\in V|(uv)\in E\}{\cup }^{\{}v\}$ , respectively.

A set S of vertices in G is a dominating set, so that for any vertex in $V(G)\mathrm{\setminus }S$ , it is adjacent to some vertex in S. The domination number of G is denoted as $\gamma (G)$ . The set S is a total dominating set of G if every vertex $V(G)$ is adjacent to some vertex of S. The minimum cardinality of such a set S is called the TD number of G, and it is denoted as ${\gamma }_t(G)$ . The concept of domination problem examines the minimum cardinality of all the dominating sets in graph G. Likewise, the TD problem determines the minimum cardinality of such sets in G. A set S is locating-dominating set of G, if every pair of vertices u and v which belongs to $u,v\in V(G)\mathrm{\setminus }S$ must satisfy this condition $N(u){\cap }^S\ne N(v){\cap }^S$ . The minimum cardinality of the locating-dominating set S of G is called the locating-domination number, and is denoted by ${\gamma }^{LD}(G)$ as studied by Haynes et al. ¹ A locating-total dominating set in a graph G is the total dominating set S of G such that every pair of distinct vertices $u,v\in V(G)\mathrm{\setminus }S$ holds $N(u){\cap }^S\ne N(v){\cap }^S$ . The minimum cardinality of a locating-total dominating set of G is called the locating-TD number, and it is denoted as ${\gamma }_t^L(G)$ by Haynes et al. ¹ A vertex set $S\subseteq V(G)$ is an open locating-dominating set, an OLD-set for G, such that for each vertex $u\in V(G)$ there is at least one vertex v in $S{\cap }^N(u)$ , and for every pair of vertices $u,v\in V(G)$ , holds $N(u){\cap }^S\ne N(v){\cap }^S$ . The open locating-dominating number is the minimum cardinality of an OLD-set for G, and it is denoted as ${\gamma }^{\mathrm{old}}(G)$ by Seo and Slater. ² The following relation holds:

$${\gamma }^{LD}(G)\le {\gamma }_t^L(G)\le {\gamma }^{\mathrm{old}}(G)$$

For the sake of simplicity and a better understanding of the definitions for the locating-dominating set, locating-total dominating set, and open locating-dominating set. The graphical representation is depicted in Figure 1.

Figure 1.

$(a)$ Vertices in locating dominating set of G are circled, $(b)$ Vertices in locating-total dominating set of $G^{\mathrm{\prime }}$ are circled, $(c)$ Vertices in open locating dominating set of H are circled.

The problem of locating-total domination is considered for locating and differentiating-TD in trees by Chellali. ³ The bounds for the locating-TD of trees by Chen and Sohn. ⁴ Furthermore, the bounds for the locating-TD of trees by Wang et al. ⁵ The locating-TD number for the grid, cubic graphs, and claw-free cubic graphs by Henning and Rad ⁶ and Henning and Lŏwenstein, ⁷ also for the corona and composition of graphs by Omamalin et al.. ⁸ Now we present the lower bounds in terms of locating-TD number of the graphs. In this paper, we utilize these results to find the exact values of the studied graphs.

Theorem 1

⁹ Let G be a graph of order $n\ge 3$ , and maximum degree $\mathrm{\Delta }\ge 2$ , with no vertex isolated, then

$${\gamma }_t^L(G)\ge \lceil {\displaystyle \frac{2n}{\mathrm{\Delta }+2}\rceil .}$$

Miller et al. ¹⁰ in their study improved the already existing result and presented the lower bound for the regular graphs.

Theorem 2

¹⁰ Let G be a regular graph of degree $d$ , then

$${\gamma }_t^L(G)\ge \lceil {\displaystyle \frac{2n}{d+2}\rceil .}$$

In this paper, we study the locating-TD number of some cycle-related graphs. Furthermore, we will consider the graphs of convex polytopes and determine the locating-TD among them.

Cycle-related graphs

Cycle graphs

The locating-TD number for the cycle graph was presented as an observation in the paper by Henning and Rad. ⁶

Observation. For a cycle graph of order $n\ge 3$ , the locating-TD is given as ${\gamma }_t^L(C_n)={\gamma }_t(C_n)=\lfloor n/2\rfloor +\lceil n/4\rceil -\lfloor n/4\rfloor$ .

We will utilize Theorem 2, as the cycle is a $2$ -regular graph. The locating-TD number for the cycle graphs.

$${\gamma }_t^L(C_n)=\{\begin{array}{cc}\lceil {\displaystyle \frac{n}{2}\rceil }& n\equiv 0,1,3(\mathrm{mod}4);\\ \lceil {\displaystyle \frac{n}{2}\rceil +1,}& n\equiv 2(\mathrm{mod}4);\end{array}$$

Proof. Let,

$$S=\{\begin{array}{cc}\{x_{4k},x_{4k+1}|k=0,\dots ,\ell -1\},& n=4\ell \\ \{x_{4k},x_{4k+1}\}\cup \{x_{4\ell }|k=0,\dots ,\ell -1\},& n=4\ell +1\\ \{x_{4k},x_{4k+1}\}\cup \{x_{4\ell },x_{4\ell +1}|k=0,\dots ,\ell -1\}& n=4\ell +2\\ \{x_{4k},x_{4k+1}\}\cup \{x_{4\ell },x_{4\ell +1}|k=0,\dots ,\ell -1\}& n=4\ell +3.\end{array}$$

Now in order to prove that S is locating-TD set of $C_n$ , we consider the following cases:

Case 1. For $n\equiv 0,1,3(\mathrm{mod}4)$ , due to Theorem 1, the minimum locating-total dominating set is $|S|\ge \lceil \frac{n}{2}\rceil$ . From Table 1 all intersections of the vertices with the set S are distinct and non-empty so $|S|\le \lceil \frac{n}{2}\rceil$ . From these facts $|S|=\lceil \frac{n}{2}\rceil$ . Thus ${\gamma }_t^L(C_n)=\lceil \frac{n}{2}\rceil$ .

Table 1.

Locating-total dominating vertices in $C_n$ .

$n$	$v\in V\mathrm{\setminus }S$	$S{\cap }^N(v)$	$v\in V\mathrm{\setminus }S$	$S{\cap }^N(v)$
$4\ell$	$x_{4k+2}$	$\{x_{4k+1}\}$	$x_{4k+3}$	$\{x_{4(k+1)}\}$
$4\ell +1$	$x_{4k+2}$	$\{x_{4k+1}\}$	$x_{4k+3}$	$\{x_{4(k+1)}\}$
$4\ell +2$	$x_{4k+2}$	$\{x_{4k+1}\}$	$x_{4k+3}$	$\{x_{4(k+1)}\}$
$4\ell +3$	$x_{4k+2}$	$\{x_{4k+1}\}$	$x_{4k+3}$	$\{x_{4(k+1)}\}$
	$x_{4\ell +2}$	$\{x_{4\ell +1},x_0\}$

Case 2. For $n\equiv 2(\mathrm{mod}4)$ , on the contrary, we consider that the minimum locating-total dominating set is $|S|=\lceil \frac{n}{2}\rceil$ . Then one of the other vertex within S is not totally dominated which contradicts the definition. In order to show that now let us suppose that $S=\{x_{4k},x_{4k+1},x_{4\ell }\}$ , for some $k=0,1,\dots ,\ell -1$ here the vertex $x_{4\ell }$ is not totally dominated so $|S|\ne \lceil \frac{n}{2}\rceil$ . From Table 1 it is clearly shown that the intersections are distinct and non-empty, so $|S|\le \lceil \frac{n}{2}\rceil +1$ . And from the above facts $|S|=\lceil \frac{n}{2}\rceil +1$ . Therefore, ${\gamma }_t^L(C_n)=\lceil \frac{n}{2}\rceil +1$ .

Subdivision of cycle graphs

The subdivision of the graph G is obtained from G by replacing every edge with a length of the path of at least one. Let us assume a cycle graph with vertex set $V(C_n)=\{x_0,x_1,\dots ,x_{n-1}\}$ . The subdivision of the cycle graph denoted as $S(C_n)$ , is obtained by introducing the vertices $\{y_0,y1,\dots ,y_{n-1}\}$ as shown in Figure 2 Mathematically the vertex and edge set of the graph $S(C_n)$ .

$$V(S(C_n))=\{x_k,y_k|k=0,\dots ,n-1\}$$

and

$$E(S(C_n))=\{(x_k,y_k),(y_k,x_{k+1}),|k=0,\dots ,n-1\}.$$

Figure 2.

The subdivision graph of cycle $(C_{10})$ .

Theorem 3

Let G be the graph of subdivision of cycle graph $S(C_n)$ , then

$${\gamma }_t^L(G)=n$$

Proof.

The subdivision of the cycle graphs is a $2$ -regular graph as well. Then by employing Theorem 2, we have ${\gamma }_t^L(G)\ge \lceil \frac{2.2n}{2+2}\rceil =n$ .

In order to prove that, let the locating-total dominating set $S=\{x_0,x_1,\dots ,x_{n-1}\}$ . Indeed it is quite evident to indicate that the intersections $S{\cap }^N(x_0)=\{y_0,y_{n-1}\}$ , and $S{\cap }^N(x_k)=\{y_{k-1},y_k\}(1\le k\le n-1)$ are non-empty and distinct. Thus, the set S is the total-locating dominating set. That is $|S|=n$ , therefore, ${\gamma }_t^L(G)\le n$ . Due to the previous fact, we have ${\gamma }_t^L(G)\ge n$ . It is proven that, ${\gamma }_t^L(G)=n$ .

Squared cycle graphs

We consider the locating-TD in the squared cycle graphs, which are an extension of cycle graphs. The squared cycle graph $S^2(n)$ is a $4$ -regular graph of order n with $V(C^2(n))=\{u_0,y_1,\dots ,u_{n-1}\}$ as shown in Figure 3 or each $p(0\le p\le n-1)$ , we join $u_p$ to $u_{p+1},u_{p+2}$ and to $u_{p-1},u_{p-2}$ . Furthermore, if these vertices are arranged cyclically $u_0,u_1,\dots ,u_{n-1}$ then each vertex $u_p$ is adjacent to the $2$ vertices which follow that $u_p$ and $2$ vertices that immediately precede $u_p$ . Thus $C^2(n)$ is a four regular graph as shown in Figure 3. It is essential to note that the squared cycle graph is a special case for the Harary graph $H(m,n)$ $m=4$ .

Figure 3.

The squared cycle graph $C_{10}^2$ .

Theorem 4

Let G be the graph of $C^2(n)$ , then

$${\gamma }_t^L(G)\{\begin{array}{cc}=\lceil {\displaystyle \frac{n}{3}\rceil ,}& n\equiv 0,1,2,4(\mathrm{mod}6);\\ \le \lceil {\displaystyle \frac{n}{3}\rceil +1}& n\equiv 3,5(\mathrm{mod}6).\end{array}$$

Proof.

The lower bound is due to Theorem 2. ${\gamma }_t^L(G)\ge \lceil \frac{2n}{4+2}\rceil =\lceil \frac{n}{3}\rceil$ .

The lower bound is attained for $n=6\ell$ , $n=6\ell +1$ , $n=6\ell +2$ , and $n=6\ell +4$ .

Let,

$$S=\{\begin{array}{cc}\{u_{6k},u_{6k+4}\}|k=0,\dots ,\ell -1& n=6\ell ;\\ \{u_{6k},u_{6k+4}\}\cup \{u_{6\ell }|k=0,\dots ,\ell -1\}& n=6\ell +1;\\ \{u_{6k},u_{6k+4}\}\cup \{u_{6\ell }|k=0,\dots ,\ell -1\}& n=6\ell +2;\\ \{u_{6k},u_{6k+4}\}\cup \{u_{6\ell },u_{6\ell +2}|k=0,\dots ,\ell -1\}& n=6\ell +3;\\ \{u_{6k},u_{6k+4}\}\cup \{u_{6\ell },u_{6\ell +3}|k=0,\dots ,\ell -1\}& n=6\ell +4;\\ \{u_{6k},u_{6k+4}\}\cup \{u_{6\ell },u_{6\ell +3},u_{6\ell +4}|k=0,\dots ,\ell -1\}& n=6\ell +5;\end{array}$$

In order to prove that, the set S is the locating-total dominating set of the graph G. The same procedure will be implemented as we did for the proof of cycle graphs, six cases are considered. It is quite evident from Table 2. The intersections of the vertices $V_G\mathrm{\setminus }S$ , are non-empty and distinct, thus proving that the set S is the locating-total dominating set of G. In order to prove that, the set S is the locating-total dominating set of the graph G. The same procedure will be implemented for the proof of cycle graphs; six cases are considered. It is pretty evident from Table 2. The intersections of the vertices $V_G\mathrm{\setminus }S$ are non-empty and distinct, thus proving that the set S is the locating-total dominating set of G.

Table 2.

Locating-total dominating vertices of squared cycle graph $C^2(n)$ .

$n$	$v\in V\mathrm{\setminus }S$	$S{\cap }^N(v)$	$v\in V\mathrm{\setminus }S$	$S{\cap }^N(v)$
$6\ell$	$u_{6k+1}$	$\{u_{6k}\}$	$u_{6k+2}$	$\{u_{6k},u_{6k+4}\}$
	$u_{6k+3}$	$\{u_{6k+4}\}$	$u_{6k+5}$	$\{u_{6k+4},u_{6(k+1)}\}$
$6\ell +1$	$u_{6k+2}$	$\{u_{6k},u_{6k+4}\}$	$u_{6k+3}$	$\{u_{6k+4}\}$
	$u_{6k+5}(k=0,\dots ,\ell -2)$	$\{u_{6k+4},u_{6(k+1)}\}$	$u_{6k+7}(k=1,\dots ,\ell -1)$	$\{u_{6k}\}$
	$u_1$	$\{u_0,u_{6\ell }\}$	$u_{6\ell -1}$	$\{u_{6\ell -2},u_{6\ell },u_0\}$
$6\ell +2$	$u_{6k+1}$	$\{u_{6k}\}$	$u_{6k+2}$	$\{u_{6k},u_{6k+4}\}$
	$u_{6k+3}$	$\{u_{6k+4}\}$	$u_{6k+5}$	$\{u_{6k+4},u_{6(k+1)}\}$
$6\ell +3$	$u_{6k+2}$	$\{u_{6k},u_{6k+4}\}$	$u_{6k+3}$	$\{u_{6k+4}\}$
	$u_{6k+5}(k=0,\dots ,\ell -2)$	$\{u_{6k+4},u_{6(k+1)}\}$	$u_{6k+7}(k=1,\dots ,\ell -1)$	$\{u_{6k}\}$
	$u_1$	$\{u_0,u_{6\ell +2}\}$	$u_{6\ell +1}$	$\{u_{6\ell },u_{6\ell +2},u_0\}$
$6\ell +4$	$u_{6k+2}$	$\{u_{6k},u_{6k+4}\}$	$u_{6k+3}$	$\{u_{6k+4}\}$
	$u_{6k+5}$	$\{u_{6k+4},u_{6(k+1)}\}$	$u_{6k+7}(k=1,\dots ,\ell -1)$	$\{u_{6k}\}$
	$u_1$	$\{u_0,u_{6\ell +3}\}$	$u_{6\ell +1}$	$\{u_{6\ell },u_{6\ell +3}\}$
	$u_{6\ell +2}$	$\{u_{6\ell },u_{6\ell +3},u_0\}$
$6\ell +5$	$u_{6k+2}$	$\{u_{6k},u_{6k+4}\}$	$u_{6k+3}$	$\{u_{6k+4}\}$
	$u_{6k+5}$	$\{u_{6k+4},u_{6(k+1)}\}$	$u_{6k+7}(k=1,\dots ,\ell -1)$	$\{u_{6k}\}$
	$u_1$	$\{u_0,u_{6\ell +4}\}$	$u_{6\ell +1}$	$\{u_{6\ell },u_{6\ell +3}\}$
	$u_{6\ell +2}$	$\{u_{6\ell },u_{6\ell +2},u_{6\ell +4}\}$

Conjecture 1. Let G be the graph of $C^2(n)$ , then

$${\gamma }_t^L(G)=\{\begin{array}{cc}\lceil {\displaystyle \frac{n}{3}\rceil ,}& n\equiv 0,1,2,4(\mathrm{mod}6);\\ \lceil {\displaystyle \frac{n}{3}\rceil +1}& n\equiv 3,5(\mathrm{mod}6).\end{array}$$

The graph of prism ${\mathcal{P}}_{\mathit{n}}$

The prism graph is the cartesian product of the cycle $C_n$ and path $P_2$ , and a $3$ -regular graph as shown in Figure 4. The prism graph is an Archimedean convex polytope as defined in the study by Juvoič ¹¹ Also, the prism graph is equivalent to the Petersen graph $P(n,1)$ . From the mathematical point of view.

Figure 4.

The graph of prism $P_n$ .

The vertex set of prism graph ${\mathcal{P}}_n$ .

$$V(P_n)=\{v_k,w_k|k=0,\dots ,n-1\}$$

and the edge set of ${\mathcal{P}}_n$ .

$$E(P_n)=\{(x_k,y_k),(y_k,x_{k+1}),|k=0,\dots ,n-1\}.$$

The locating-TD number for $3\le n\le 4$ , is ${\gamma }_t^L({\mathcal{P}}_3)=3$ , and ${\gamma }_t^L({\mathcal{P}}_n)=4$ . The following result for the graph of the prism ${\mathcal{P}}_n$ is due to Theorem 2.

Theorem 5

For $n\ge 5$ , the locating-TD number for the prism graph ${\mathcal{P}}_n$ .

$${\gamma }_t^L({\mathcal{P}}_n)\{\begin{array}{cc}=\lceil {\displaystyle \frac{4n}{5}\rceil ,}& n\equiv 0,2,4(\mathrm{mod}5);\\ \le \lceil {\displaystyle \frac{4n}{5}\rceil +1}& n\equiv 1,3(\mathrm{mod}5).\end{array}$$

Proof.

Let,

$$S=\{\begin{array}{cc}\{v_{5k},v_{5k+3},w_{5k},w_{5k+3}\}|k=0,\dots ,\ell -1& n=5\ell \\ \{v_{5k},v_{5k+3},w_{5k},w_{5k+3}\}\cup \{v_{5\ell },w_{5\ell }|k=0,\dots ,\ell -1\}& n=5\ell +1\\ \{v_{5k},v_{5k+3},w_{5k},w_{5k+3}\}\cup \{v_{5\ell },w_{5\ell }|k=0,\dots ,\ell -1\}& n=5\ell +2\\ \{v_{5k},v_{5k+3},w_{5k},w_{5k+3}\}\cup \{v_{5\ell },v_{5\ell +2},w_{5\ell },w_{5\ell +2}|k=0,\dots ,\ell -1\}& n=5\ell +3\\ \{v_{5k},v_{5k+3},w_{5k},w_{5k+3}\}\cup \{v_{5\ell },v_{5\ell +3},w_{5\ell },w_{5\ell +3}|k=0,\dots ,\ell -1\}& n=5\ell +4\end{array}$$

In order to prove that the set S is the locating-total dominating set, there are five cases. The intersection of the vertices $V(G)\mathrm{\setminus }S$ is shown in Table 3, and it is clearly seen that these intersections are non-empty and distinct as well. Thus proving that the set S is the locating-total dominating set of cardinality $\lceil \frac{4n}{5}\rceil$ , when $n\equiv 0,2,4(\mathrm{mod}5)$ , and $\lceil \frac{4n}{5}\rceil +1$ , when $n\equiv 1,3(\mathrm{mod}5)$ .

Table 3.

Locating-total dominating vertices in the prism graph ${\mathcal{P}}_n$ .

$n$	$v\in V\mathrm{\setminus }S$	$S{\cap }^N(v)$	$v\in V\mathrm{\setminus }S$	$S{\cap }^N(v)$
$5\ell$	$v_{5k+1}$	$\{v_{5k}\}$	$v_{5k+2}$	$\{v_{5k+3}\}$
	$v_{5k+4}$	$\{v_{5k+3},v_{5(k+1)}\}$	$w_{5k+1}$	$\{w_{5k}\}$
	$w_{5k+2}$	$\{w_{5k+3}\}$	$w_{5k+4}$	$\{w_{5k+3},w_{5(k+1)}\}$
$5\ell +1$	$v_{5k+1}$	$\{v_{5k}\}$	$v_{5k+2}$	$\{v_{5k+3}\}$
	$v_{5k+4}$	$\{v_{5k+3},v_{5(k+1)}\}$	$w_{5k+1}$	$\{w_{5k}\}$
	$w_{5k+2}$	$\{w_{5k+3}\}$	$w_{5k+4}$	$\{w_{5k+3},w_{5(k+1)}\}$
$5\ell +2$	$v_{5k+1}$	$\{v_{5k}\}$	$v_{5k+2}$	$\{v_{5k+3}\}$
	$v_{5k+4}$	$\{v_{5k+3},v_{5(k+1)}\}$	$w_{5k+1}$	$\{w_{5k}\}$
	$w_{5k+2}$	$\{w_{5k+3}\}$	$w_{5k+4}$	$\{w_{5k+3},w_{5(k+1)}\}$
	$v_{5\ell +1}$	$\{v_{5\ell },v_0\}$	$w_{5\ell +1}$	$\{w_{5\ell },w_0\}$
$5\ell +3$	$v_{5k+1}$	$\{v_{5k}\}$	$v_{5k+2}$	$\{v_{5k+3}\}$
	$v_{5k+4}$	$\{v_{5k+3},v_{5(k+1)}\}$	$w_{5k+1}$	$\{w_{5k}\}$
	$w_{5k+2}$	$\{w_{5k+3}\}$	$w_{5k+4}$	$\{w_{5k+3},w_{5(k+1)}\}$
	$v_{5\ell +1}$	$\{v_{5\ell },v_{5\ell +2}\}$	$w_{5\ell +1}$	$\{w_{5\ell },w_{5\ell +2}\}$
$5\ell +4$	$v_{5k+1}$	$\{v_{5k}\}$	$v_{5k+2}$	$\{v_{5k+3}\}$
	$v_{5k+4}$	$\{v_{5k+3},v_{5(k+1)}\}$	$w_{5k+1}$	$\{w_{5k}\}$
	$w_{5k+2}$	$\{w_{5k+3}\}$	$w_{5k+4}$	$\{w_{5k+3},w_{5(k+1)}\}$
	$v_{5\ell +1}$	$\{v_{5\ell }\}$	$v_{5\ell +2}$	$\{v_{5\ell +3}\}$
	$w_{5\ell +1}$	$\{w_{5\ell }\}$	$w_{5\ell +2}$	$\{w_{5\ell +3}\}$

Table 4.

Locating-total dominating vertices in the graph of antiprism ${\mathcal{A}}_n$ .

$n$	$v\in V\mathrm{\setminus }S$	$S{\cap }^N(v)$	$v\in V\mathrm{\setminus }S$	$S{\cap }^N(v)$
$3\ell$	$v_{3k+2}$	$\{v_{3k+1},v_{3(k+1)}\}$	$w_{3k}$	$\{v_{3k},v_{3k+1}\}$
	$w_{3k+1}$	$\{v_{3k+1}\}$	$w_{3k+2}$	$\{v_{3(k+1)}\}$
$3\ell +1$	$v_{3k+2}$	$\{v_{3k+1},v_{3(k+1)}\}$	$w_{3k}$	$\{v_{3k},v_{3k+1}\}$
	$w_{3k+1}$	$\{v_{3k+1}\}$	$w_{3k+2}$	$\{v_{3(k+1)}\}$
	$w_{3\ell }$	$\{v_{3\ell },v_0\}$
$3\ell +2$	$v_{3k+2}$	$\{v_{3k+1},v_{3(k+1)}\}$	$w_{3k}$	$\{v_{3k},v_{3k+1}\}$
	$w_{3k+1}$	$\{v_{3k+1}\}$	$w_{3k+2}$	$\{v_{3(k+1)}\}$
	$w_{3\ell }$	$\{v_{3\ell },v_{3\ell +1}\}$	$w_{3\ell +1}$	$\{v_{3\ell +1},v_0\}$

From the computational evidence we present the following conjecture.

Conjecture 2. For $n\ge 5$ , the locating–TD number for the prism graph ${\mathcal{P}}_n$ .

$${\gamma }_t^L({\mathcal{P}}_n)=\{\begin{array}{cc}\lceil {\displaystyle \frac{4n}{5}\rceil ,}& n\equiv 0,2,4(\mathrm{mod}5);\\ \lceil {\displaystyle \frac{4n}{5}\rceil +1}& n\equiv 1,3(\mathrm{mod}5).\end{array}$$

Convex polytopes

A convex polytope is a polytope with a convex set of points in the $n$ -dimensional Euclidean space. A graph of a convex polytope is formed from its vertices and edges having the same incidence relation. Graphs of convex polytopes were first considered by Bača.12,13 The author studied graceful and anti-graceful labeling problems for these geometrically essential graphs. The metric dimension of rotationally symmetric graphs was studied by Imran et al.. ¹⁴ The domination-related parameters in the graphs of convex polytopes are considered in some recent studies. The binary locating domination number (respectively locating domination number) is studied by Simić et al., ¹⁵ and the same problem was further studied for other classes of convex polytopes by Raza et al. ¹⁶ The open locating domination number in graphs of convex polytopes was studied by Savića et al. ¹⁷ and Raza ¹⁸ . Kartelj et al. ¹⁹ studied the problem of roman domination number of some classes of convex polytopes. In the next section, we study the problem of locating-TD in some graphs of convex polytopes.

Exact values

The graph of antiprism ${\mathcal{A}}^{\mathit{n}}$

The graph of antiprism ${\mathcal{A}}_n$ as shown in Figure 5 is a $4$ -regular graph. The recent study on this family of the graph is carried out by Raza et al., ²⁰ where the authors discuss the mixed metric dimension. The graph of antiprism is a $4$ -regular graph. It is the octahedron for $n=3$ . From the mathematical point of view, the vertex and edge set of antiprism graph ${\mathcal{A}}_n$ are as follows:

Figure 5.

The graph of antiprism $A_n$ .

The vertex set of $V({\mathcal{A}}^n)$ is given as:

$$V({\mathcal{A}}_n)=\{v_k,w_k|k=0,\dots ,n-1\}$$

and the edge set of $E(A^n)$ is given as:

$$E({\mathcal{A}}_n)=\{(v_k,v_{k+1}),(v_k,w_k),(v_{k+1},w_k),(w_k,w_{k+1})|k=0,\dots ,n-1\}.$$

The antiprism ${\mathcal{A}}_n$ has $|V({\mathcal{A}}_n)|=2n$ and $|E({\mathcal{A}}_n)|=4n$ .

The locating-TD number of the antiprism graph when $3\le n<6$ ${\gamma }_t^L({\mathcal{A}}_3)=3$ , ${\gamma }_t^L({\mathcal{A}}_4)=3$ , and ${\gamma }_t^L({\mathcal{A}}_5)=4$ .

Theorem 6

For $n\ge 6$ , the locating-total dominating number for antiprism graph ${\mathcal{A}}_n$ .

$${\gamma }_t^L({\mathcal{A}}_n)=\lceil {\displaystyle \frac{2n}{3}\rceil }$$

Proof.

The graph of antiprism as seen from Figure 5, is a $4$ -regular graph with $2n$ vertices. Then, by Theorem 2, ${\gamma }_t^L({\mathcal{A}}_n)\ge \lceil \frac{2(2n)}{4+2}\rceil =\lceil \frac{2n}{3}\rceil$ .

Let,

$$S=\{\begin{array}{cc}\{v_{3k},v_{3k+1}\}|k=0,\dots ,\ell -1& n=3\ell ;\\ \{v_{3k},v_{3k+1}\}\cup \{v_{3\ell }|k=0,\dots ,\ell -1\}& n=3\ell +1;\\ \{v_{3k},v_{3k+1}\}\cup \{v_{3\ell },v_{3\ell +1}|k=0,\dots ,\ell -1\}& n=3\ell +2.\end{array}$$

Now we can prove that the set S is the locating-total dominating set by considering three cases. Table 3 clearly indicates that the intersection of the vertices $V(G)\mathrm{\setminus }S$ is non-empty and distinct. So $|S|=\lceil \frac{2n}{3}\rceil$ . This implies that ${\gamma }_t^L({\mathcal{A}}_n)\le \lceil \frac{2n}{3}\rceil$ . Due to the previous facts we already know that ${\gamma }_t^L({\mathcal{A}}_n)\ge \lceil \frac{2n}{3}\rceil$ . So these facts imply that ${\gamma }_t^L({\mathcal{A}}_n)=\lceil \frac{2n}{3}\rceil$ .

The upper bounds

The graph of a convex polytope ${\mathcal{R}}_{\mathit{n}}$

The graph of a convex polytope ${\mathcal{R}}_n$ is defined by Bača ¹³ as shown in Figure 6. The graph is derived from the graph of antiprism. Now mathematically, the vertex and edge set is shown as follows:

Figure 6.

The graph of convex polytope ${\mathcal{R}}_n$ .

Figure 7.

The graph of convex polytope ${\mathcal{T}}_n$ .

The vertex set of ${\mathcal{R}}^n$ .

$$V({\mathcal{R}}_n)=\{w_k,x_k,y_k|k=0,1,\dots ,n-1\},$$

and edge set of ${\mathcal{R}}^n$ .

$$E({\mathcal{R}}_n)=\{(w_k,w_{k+1}),(w_k,x_k),(w_{k+1},x_k)(x_k,x_{k+1}),(x_k,y_k),(y_k,y_{k+1})|k=0,1,\dots ,n-1\}.$$

Theorem 7

For $n\ge 6$ , we have for ${\mathcal{R}}_n$

$${\gamma }_t^L({\mathcal{R}}_n)\le n$$

Proof.

Let $S\subseteq V({\mathcal{R}}_n)$ such that, $S=\{x_k|k=0,\dots ,n-1\}$ . Next, we show that the set S is a locating-total dominating set for the graph ${\mathcal{R}}_n$ . It can be seen that

$$S{\cap }^N(w_k)=\{x_{k-1},x_k\},S{\cap }^N(y_k)=\{x_k\}.$$

It is clear that intersections between the vertices of a graph with the set S are non-empty, and all these intersections are distinct. So S is a locating-total dominating set for the graph of a convex polytope ${\mathcal{R}}_n$ . Therefore, we obtain that, ${\gamma }_t^L({\mathcal{R}}_n)\le n$ . Finally, computational evidence encourages us to conjecture that Theorem 7 in fact gives the exact values for ${\mathcal{R}}_n$ .

Conjecture 3. For $n\ge 6$ , we conjecture that

$${\gamma }_t^L({\mathcal{R}}_n)=n$$

(1)

The graph of a convex polytope ${\mathcal{T}}_{\mathit{n}}$

The graph of convex polytope ${\mathcal{T}}_n$ as studied by Savića et al., 17 where they discuss the open locating domination number for this family of graphs. It consists of $4n$ three-sided faces, n four-sided faces, and a pair of $n$ -sided faces as shown in Figure 9, and is constructed by joining the graphs of a convex polytope ${\mathcal{R}}_n$ , and the graph of ${\mathcal{A}}_n$ . The vertex set and edge set for the graph of a convex polytope ${\mathcal{T}}_n$ .

Figure 9.

The graph of convex polytope ${\mathcal{Q}}_n$ .

The vertex set of ${\mathcal{T}}_n$ .

$$V({\mathcal{T}}_n)=\{w_k,x_k,y_k,z_k|k=0,\dots ,n-1\}$$

and the edge set of ${\mathcal{T}}_n$ .

$$E({\mathcal{T}}_n)=\{(w_k,w_{k+1}),(w_{k+1},x_k),(x_k,x_{k+1}),(y_k,y_{k+1}),(y_{k+1},z_k),(z_k,z_{k+1})\}\cup$$

$$\{(w_k{x}_k),(x_k{y}_k),(y_k{z}_k)|k=0,\dots ,n-1\}.$$

Theorem 8.

For $n\ge 6$ , the locating-TD number of ${\mathcal{T}}_n$ .

$${\gamma }_t^L({\mathcal{T}}_n)\le \{\begin{array}{cc}\lceil {\displaystyle \frac{4n}{3}\rceil ,}& n\equiv 0,1(\mathrm{mod}3);\\ \lceil {\displaystyle \frac{4n}{3}\rceil +1}& n\equiv 2(\mathrm{mod}3).\end{array}$$

Proof.

Let,

$$S=\{\begin{array}{cc}\{w_{3k},w_{3k+1},y_{3k},y_{3k+1}\}|k=0,\dots ,\ell -1& n=3\ell \\ \{w_{3k},w_{3k+1},y_{3k},y_{3k+1}\}{\cup }^{\{}{w}_{3\ell },y_{3\ell }|k=0,\dots ,\ell -1\}& n=3\ell +1\\ \{w_{3k},w_{3k+1},y_{3k},y_{3k+1}\}{\cup }^{\{}{w}_{3\ell },w_{3\ell +1},y_{3\ell },y_{3\ell +1}|k=0,\dots ,\ell -1\}& n=3\ell +2\end{array}$$

In order to prove that the set S is a locating-total dominating set of the graph of a convex polytope ${\mathcal{T}}_n$ . The Table 5 the intersection of the vertices $V(G)\mathrm{\setminus }S$ are all non-empty and distinct. So the set S is the locating-total dominating set with the cardinality $\lceil \frac{4n}{3}\rceil$ , when $n\equiv 0,1(\mathrm{mod}3)$ . Also, $\lceil \frac{4n}{3}\rceil +1$ , when $n\equiv 2(\mathrm{mod}3)$ .

Table 5.

Locating-total dominating vertices in the graph of ${\mathcal{T}}_n$ .

$n$	$v\in V\mathrm{\setminus }S$	$S{\cap }^N(v)$	$v\in V\mathrm{\setminus }S$	$S{\cap }^N(v)$
$3\ell$	$w_{3k+2}$	$\{w_{3k+1},w_{3(k+1)}\}$	$x_{3k}$	$\{w_{3k},w_{3k+1},y_{3k}\}$
	$x_{3k+1}$	$\{w_{3k+1},y_{3k+1}\}$	$x_{3k+2}$	$\{w_{3(k+1)}\}$
	$y_{3k+2}$	$\{y_{3k+1},y_{3(k+1)}\}$	$z_{3k}$	$\{y_{3k}\}$
	$z_{3k+1}$	$\{y_{3k},y_{3k+1}\}$	$z_{3k+2}$	$\{y_{3(k+1)}\}$
$3\ell +1$	$w_{3k+2}$	$\{w_{3k+1},w_{3(k+1)}\}$	$x_{3k}$	$\{w_{3k},w_{3k+1},y_{3k}\}$
	$x_{3k+1}$	$\{w_{3k+1},y_{3k+1}\}$	$x_{3k+2}$	$\{w_{3(k+1)}\}$
	$y_{3k+2}$	$\{y_{3k+1},y_{3(k+1)}\}$	$z_{3k}(k=1,\dots ,\ell$ )	$\{y_{3k}\}$
	$z_{3k+1}$	$\{y_{3k+1}\}$	$z_{3k+2}$	$\{y_{3(k+1)}\}$
	$x_{3\ell }$	$\{w_{3\ell },y_{3\ell },w_0\}$	$z_{3\ell }$	$\{y_{3\ell },y_0\}$
$3\ell +2$	$w_{3k+2}$	$\{w_{3k+1},w_{3(k+1)}\}$	$x_{3k}$	$\{w_{3k},w_{3k+1},y_{3k}\}$
	$x_{3k+1}$	$\{w_{3k+1},y_{3k+1}\}$	$x_{3k+2}$	$\{w_{3(k+1)}\}$
	$y_{3k+2}$	$\{y_{3k+1}\}$	$z_{3k}(k=1,\dots ,\ell )$	$\{y_{3k}\}$
	$z_{3k+1}$	$\{y_{3k},y_{3k+1}\}$	$z_{3k+2}$	$\{y_{3k+1}\}$
	$w_{3\ell +1}$	$\{w_{3\ell },w_0\}$	$x_{3\ell }$	$\{w_{3\ell },y_{3\ell }\}$
	$z_0$	$\{y_0,y_{3\ell +1}\}$

Finally, computational evidence encourages us to conjecture that Theorem 8 in fact gives the exact values for ${\mathcal{T}}_n$ .

Conjecture 4. For $n\ge 6$ , we conjecture that

$${\gamma }_t^L({\mathcal{T}}_n)=\{\begin{array}{cc}\lceil {\displaystyle \frac{4n}{3}\rceil ,}& n\equiv 0,1(\mathrm{mod}3);\\ \lceil {\displaystyle \frac{4n}{3}\rceil +1}& n\equiv 2(\mathrm{mod}3).\end{array}.$$

(2)

The graph of a convex polytope ${\mathcal{D}}_{\mathit{n}}$

The graph of convex polytope defined by the study of Bača, ¹³ which consists of $2n$ five-sided faces as shown in Figure 8.

Figure 8.

The graph of convex polytope ${\mathcal{D}}_n$ .

The vertex set of ${\mathcal{D}}_n$ .

$$V({\mathcal{D}}_n)=\{w_k,x_k,y_k,z_k|k=0,\dots ,n-1\}$$

and edge set of ${\mathcal{D}}_n$ .

$$E({\mathcal{D}}_n)=\{(w_k{w}_{k+1}),(w_k{x}_k),(x_k{y}_k),(x_{k+1}{y}_k),(y_k{z}_k),(z_k{z}_{k+1})|k=0,\dots ,n-1\}$$

Theorem 9

For $n\ge 6$ , the locating-TD number for the graph of ${\mathcal{D}}_n$ .

$${\gamma }_t^L({\mathcal{D}}_n)\le 2n$$

Proof.

Let $S\subset V({\mathcal{D}}_n)$ such that $S=\{w_k,z_k|k=0,\dots ,\ell -1\}$ . Next, we show that the set S is a locating-total dominating set of ${\mathcal{D}}_n$ . It can be seen that,

$$S{\cap }^N(x_k)=\{w_k\},S{\cap }^N(y_k)=\{z_k\}.$$

It is clearly shown that all the intersections with the set S are distinct, non-empty and totally dominated. This shows that the set S is a locating-total dominating set of the graph ${\mathcal{D}}_n$ . Therefore, we can obtain that ${\gamma }_t^L({\mathcal{D}}_n)\le 2n$ .

The graph of convex polytope ${\mathcal{Q}}_{\mathit{n}}$

The graph of a convex polytope ${\mathcal{Q}}_n$ is defined in the study by Bača ¹² in which is formed from the graph of ${\mathcal{P}}_n$ , and it contains three-sided, four-sided, five-sided, and $n$ -sided faces, respectively, as shown in Figure 9. Mathematically, the vertex and edge set of the graph ${\mathcal{Q}}_n$ .

The vertex set of ${\mathcal{Q}}_n$ .

$$V({\mathcal{Q}}_n)=\{w_k,x_k,y_k,z_k|k=0,\dots ,n-1\}$$

and edge set of ${\mathcal{Q}}_n$ .

$$E({\mathcal{Q}}_n)=\{(w_k{w}_{k+1}),(x_k{x}_{k+1}),(x_{k+1}{y}_k),(z_k{z}_{k+1})\}$$

$${\cup }^{\{}(w_k{x}_k),(x_k{y}_k),(y_k{z}_k)|k=0,\dots ,n-1\}.$$

Theorem 10

For $n\ge 6$ , the locating-TD number for the graph of ${\mathcal{Q}}_n$

$${\gamma }_t^L({\mathcal{Q}}_n)\le \{\begin{array}{cc}\lceil {\displaystyle \frac{3n}{2}\rceil }& n\equiv 0,1,3(\mathrm{mod}4);\\ \lceil {\displaystyle \frac{3n}{2}\rceil +1,}& n\equiv 2(\mathrm{mod}4);\end{array}$$

Proof.

Let,

$$S=\{\begin{array}{cc}\{x_k|k=0,\dots ,n-1\}{\cup }^{\{}{z}_{4k},z_{4k+1}|k=0,\dots ,\ell -1\}& n=4\ell ;\\ \{x_k|k=0,\dots ,n-1\}{\cup }^{\{}{z}_{4k},z_{4k+1},z_{4\ell }|k=0,\dots ,\ell -1\}& n=4\ell +1;\\ \{x_k|k=0,\dots ,n-1\}{\cup }^{\{}{z}_{4k},z_{4k+1},z_{4\ell },z_{4\ell +1}|k=0,\dots ,\ell -1\}& n=4\ell +2;\\ \{x_k|k=0,\dots ,n-1\}{\cup }^{\{}{z}_{4k},z_{4k+1},z_{4\ell },z_{4\ell +1}|k=0,\dots ,\ell -1\}& n=4\ell +3.\\ & \end{array}$$

In the case of ${\mathcal{Q}}_n$ , there are four cases, and as it is previously proven for other families of graphs, that all vertices in $V(G)\mathrm{\setminus }S$ and the intersections of their neighborhoods with the set S. From the above Table 6, it can be observed that all these intersections with the set S are distinct, non-empty, and totally dominated. Thus for any two vertices $u,v\in V(G)\mathrm{\setminus }S$ , we have $S{\cap }^N(v)\ne S{\cap }^N(u)\ne \mathrm{\varnothing }$ and the set S totally dominates.

Table 6.

Locating-total dominating vertices in the graph of ${\mathcal{Q}}_n$ .

$n$	$v\in V\mathrm{\setminus }S$	$S{\cap }^N(v)$	$v\in V\mathrm{\setminus }S$	$S{\cap }^N(v)$
$4\ell$	$w_k|$ k = 0,…,n − 1	$\{x_k\}$	$y_{4k}$	$\{x_{4k},x_{4k+1},z_{4k}\}$
	$y_{4k+1}$	$\{x_{4k+1},x_{4k+2},z_{4k+1}\}$	$y_{4k+2}$	$\{x_{4k+2},x_{4k+3}\}$
	$y_{4k+3}$	$\{x_{4k+3},x_{4(k+1)}\}$	$z_{4k+2}$	$\{z_{4k+1}\}$
	$z_{4k+3}$	$\{z_{4(k+1)}\}$
$4\ell +1$	$w_k|$ k = 0,…,n − 1	$\{x_k\}$	$y_{4k}$	$\{x_{4k},x_{4k+1},z_{4k}\}$
	$y_{4k+1}$	$\{x_{4k+1},x_{4k+2},z_{4k+1}\}$	$y_{4k+2}$	$\{x_{4k+2},x_{4k+3}\}$
	$y_{4k+3}$	$\{x_{4k+3},x_{4(k+1)}\}$	$z_{4k+2}$	$\{z_{4k+1}\}$
	$z_{4k+3}$	$\{z_{4(k+1)}\}$	$y_{4\ell }$	$\{x_{4\ell },x_0,z_{4\ell }\}$
$4\ell +2$	$w_k|$ k = 0,…,n − 1	$\{x_k\}$	$y_{4k}$	$\{x_{4k},x_{4k+1},z_{4k}\}$
	$y_{4k+1}$	$\{x_{4k+1},x_{4k+2},z_{4k+1}\}$	$y_{4k+2}$	$\{x_{4k+2},x_{4k+3}\}$
	$y_{4k+3}$	$\{x_{4k+3},x_{4(k+1)}\}$	$z_{4k+2}$	$\{z_{4k+1}\}$
	$z_{4k+3}$	$\{z_{4(k+1)}\}$	$y_{4\ell }$	$\{x_{4\ell },x_{4\ell +1},z_{4\ell }\}$
	$y_{4\ell +1}$	$\{x_{4\ell +1},x_0,z_{4\ell +1}\}$
$4\ell +3$	$w_k|$ k = 0,…,n − 1	$\{x_k\}$	$y_{4k}$	$\{x_{4k},x_{4k+1},z_{4k}\}$
	$y_{4k+1}$	$\{x_{4k+1},x_{4k+2},z_{4k+1}\}$	$y_{4k+2}$	$\{x_{4k+2},x_{4k+3}\}$
	$y_{4k+3}$	$\{x_{4k+3},x_{4(k+1)}\}$	$z_{4k+2}$	$\{z_{4k+1}\}$
	$z_{4k+3}$	$\{z_{4(k+1)}\}$	$y_{4\ell }$	$\{x_{4\ell },x_{4\ell +1},z_{4\ell }\}$
	$y_{4\ell +1}$	$\{x_{4\ell +1},x_{4\ell +2},z_{4\ell +1}\}$	$y_{4\ell +2}$	$\{x_{4\ell +2},x_0\}$
	$z_{4\ell +2}$	$\{z_{4\ell +1},z_0\}$

Conclusion

This paper finds the locating-TD number in some families of cycle-related graphs, and graphs of convex polytopes are considered. Future research can consider more families of convex polytopes that exhibit exact values for the domination-related parameter and various other complex graphs.