Variety of General Position Problems in Graphs

Abstract

Let X be a vertex subset of a graph G. Then $u, v\in V(G)$ are X-positionable if $V(P)\cap X \subseteq \{u,v\}$ holds for any shortest u, v-path P. If each two vertices from X are X-positionable, then X is a general position set. The general position number of G is the cardinality of a largest general position set of G and has been already well investigated. In this paper a variety of general position problems is introduced based on which natural pairs of vertices are required to be X-positionable. This yields the total (resp. dual, outer) general position number. It is proved that the total general position sets coincide with sets of simplicial vertices, and that the outer general position sets coincide with sets of mutually maximally distant vertices. It is shown that a general position set is a dual general position set if and only if its complement is convex. Several sufficient conditions are presented that guarantee that a given graph has no dual general position set. The total general position number, the outer general position number, and the dual general position number of arbitrary Cartesian products are determined.

1 Introduction

General position sets were introduced to graph theory independently in [1, 2], but in the special case of hypercubes, these sets had been studied previously in [3]. Finding a largest general position set in a graph G is an NP-hard problem [2]. In [4], a characterization of general position sets in graphs was proved and the general position number for the complement of bipartite graphs, the complement of trees, and the complement of hypercubes was determined. Afterwards, general position sets received a wide attention, see [5,6,7,8,9] for a selection of recent developments.

Mutual-visibility sets are closely related to general position sets and were recently introduced by Di Stefano [10]. While investigating mutual-visibility sets in strong products, there was a natural need to introduce total mutual-visibility sets [11]. This has led to the variety of mutual-visibility sets which was formalized in [12]. Motivated by the variety of mutual-visibility sets, the main purpose of this paper is to introduce and study the corresponding variety of general position sets. It consists of general position sets, total general position sets, outer general position sets, and dual general position sets. This line of research has very recently been continued in [13], where the total, the outer, and the dual general position sets were investigated in strong and lexicographic products.

The rest of the paper is organized as follows. In the rest of the introduction we give definitions needed. In the next section we introduce the variety of the general position sets and characterize total general position sets and outer general position sets. In Sect. 3 we focus on dual general position sets. We first observe that a general position set is a dual general position set if and only if its complement is convex. Then we consider graphs with small dual general position numbers. In particular, several sufficient conditions are presented that guarantee that a given graph has no dual general position set at all. In Sect. 4 we determine the total general position number, the outer general position number, and the dual general position number of arbitrary Cartesian products.

For a natural number n we set $[n] = \{1,\ldots , n\}$. Graphs $G = (V(G), E(G))$ in this paper are connected unless otherwise stated. The order of G is the value of |V(G)|. The open neighborhood of a vertex u of G is denoted by $N_G(u)$. The degree of a vertex u of G is $\deg _G(u) = |N_G(u)|$. If $X\subseteq V(G)$, then G[X] denotes the subgraph of G induced by X. Moreover, $G-X$ is the subgraph of G obtained from G by deleting all vertices from X. If G is not a tree, then its girth g(G) is the length of a shortest cycle of G. A vertex of G is simplicial if its neighbourhood induces a complete subgraph. The set of simplicial vertices of G will be denoted by S(G) and the cardinality of S(G) by s(G). The clique number of G is denoted by $\omega (G)$.

The distance $d_G(u,v)$ between vertices u and v of G is the usual shortest-path distance. The diameter $\textrm{diam}(G)$ of G is the maximum distance between pairs of vertices of G. A subgraph $G'$ of a graph G is isometric, if for every two vertices x and y of $G'$ we have $d_{G'}(x,y) = d_{G}(x,y)$. A subgraph $G'$ of a graph G is convex, if for every two vertices of $G'$, every shortest path in G between them lies completely in $G'$. By abuse of language we also say that a set of vertices is convex if it induces a convex subgraph.

The Cartesian product $G\,\square \,H$ of graphs G and H has the vertex set $V(G\,\square \,H) = V(G)\times V(H)$, and vertices (g, h) and $(g', h')$ are adjacent if either $gg'\in E(G)$ and $h = h'$, or $g = g'$ and $hh'\in E(H)$. The strong product $G\boxtimes H$ is obtained from the Cartesian product $G\,\square \,H$ by adding the edges $(g, h)(g', h')$ whenever $gg'\in E(G)$ and $hh'\in E(H)$. The join $G\oplus H$ is the graph obtained from the disjoint union of G and H by adding all possible edges between vertices from G and vertices from H.

2 The Variety

In this section we first introduce the announced variety of general position sets. After that we characterize total general position sets and outer general position sets.

Let $G = (V(G), E(G))$ be a graph and $X\subseteq V(G)$. Vertices $u,v\in V(G)$ are X-positionable if for any shortest u, v-path P we have $V(P)\cap X \subseteq \{u,v\}$. Note that each pair of adjacent vertices is X-positionable. Set ${\overline{X}} = V(G)\setminus X$. Then we say that X is

• a general position set, if every $u,v\in X$ are X-positionable;

• a total general position set, if every $u,v\in V(G)$ are X-positionable;

• an outer general position set, if every $u,v\in X$ are X-positionable, and every $u\in X$, $v\in {\overline{X}}$ are X-positionable; and

• a dual general position set, if every $u,v\in X$ are X-positionable, and every $u,v\in {\overline{X}}$ are X-positionable.

The cardinality of a largest general position set, a largest total general position set, a largest outer general position set, and a largest dual general position set will be respectively denoted by $\textrm{gp}(G)$, $\textrm{gp}_{\textrm{t}}(G)$, $\textrm{gp}_{\textrm{o}}(G)$, and $\textrm{gp}_{\textrm{d}}(G)$. Also, these graph invariants will be respectively called the general position number, the total general position number, the outer general position number, and the dual general position number of G. Moreover, for any invariant $\tau (G)$ from the above ones, by a $\tau$-set we mean any set of vertices of cardinality $\tau (G)$. In addition, for any two invariants $\tau _1(G)$ and $\tau _2(G)$, by a $(\tau _1,\tau _2)$-graph we mean any graph G with $\tau _1(G)=\tau _2(G)$.

If G is a graph, then by definition,

$$\begin{aligned} \textrm{gp}(G)&\ge \textrm{gp}_{\textrm{o}}(G) \ge \textrm{gp}_{\textrm{t}}(G)\quad \textrm{and} \end{aligned}$$

(1)

$$\begin{aligned} \textrm{gp}(G)&\ge \textrm{gp}_{\textrm{d}}(G) \ge \textrm{gp}_{\textrm{t}}(G)\,. \end{aligned}$$

(2)

If G is a block graph, then $\textrm{gp}(G) = s(G)$, see [2, Theorem 3.6]. Moreover, we can check directly that the set of simplicial vertices of G is also a total general position set. Hence block graphs are $(\textrm{gp},\textrm{gp}_{\textrm{t}})$-graphs. Having (1) and (2) in mind we thus get that if G is a block graph, then

$$\begin{aligned} \textrm{gp}(G) = \textrm{gp}_{\textrm{o}}(G) = \textrm{gp}_{\textrm{d}}(G) = \textrm{gp}_{\textrm{t}}(G) = s(G). \end{aligned}$$

In particular, if $n\ge 2$, then $\tau (P_n) = 2$ for each $\tau \in \{\textrm{gp}, \textrm{gp}_{\textrm{o}}, \textrm{gp}_{\textrm{d}}, \textrm{gp}_{\textrm{t}}\}$. Moreover,

• each pair of distinct vertices of $P_n$ forms a $\textrm{gp}$-set of $P_n$,

• $\{1,n\}$ is the only $\textrm{gp}_{\textrm{o}}$-set of $P_n$,

• $\{1,2\}$, $\{1,n\}$, and $\{n-1,n\}$ are the only $\textrm{gp}_{\textrm{d}}$-sets of $P_n$,

• $\{1,n\}$ is the only $\textrm{gp}_{\textrm{t}}$-set of $P_n$.

Contrary to block graphs, by considering Cartesian products of two complete graphs we will see that all these four parameters can be pairwise arbitrary different.

We now characterize total general position sets as follows.

Theorem 2.1

Let G be a graph and $X\subseteq V(G)$. Then X is a total general position set of G if and only if $X\subseteq S(G)$. Moreover, $\textrm{gp}_{\textrm{t}}(G)=s(G)$.

Proof

Assume first that X is a total general position set of G and consider an arbitrary vertex x from X. Suppose that $x\not \in S(G)$. Then x has two adjacent vertices y and z such that $d_G(y,z)=2$, which means that there exists a shortest y, z-path containing x. Hence the vertices y and z are not X-positionable, a contradiction. As a consequence, we conclude that x must belong to S(G) and then $X\subseteq S(G)$.

To prove the converse, assume that $X\subseteq S(G)$. Consider any two vertices u and v from V(G) and let $P_{uv}$ be a shortest u, v-path of G. If u is adjacent to v, then $V(P_{uv}) = \{u,v\}$ and hence u and v are X-positionable. Assume next that $d_G(u,v)\ge 2$. Let $P_{uv}$ be the path $u=x_1, x_2, \ldots , x_k=v$. Then $k\ge 3$. Suppose that $x_i\in X$, where $2\le i\le k-1$. Since $x_i$ is a simplicial vertex of G, $x_{i-1}$ must be adjacent to $x_{i+1}$ and hence $x_1,\ldots , x_{i-1},x_{i+1},\ldots , x_k$ is a u, v-path shorter than $P_{uv}$. Since this is not possible, $V(P_{uv})\cap X\subseteq \{u,v\}$, and thus u and v are X-positionable. Hence X is a total general position set of G, and then we can conclude that $\textrm{gp}_{\textrm{t}}(G)=s(G)$. $\square$

Corollary 2.2

Let G be a graph. Then $\textrm{gp}_{\textrm{t}}(G)=0$ if and only if G has no simplicial vertices.

We continue with a characterization of outer general position sets. For this sake, the following concepts are crucial. A vertex u of a graph G is maximally distant from $v\in V(G)$ if for every $w\in N_G(u)$ it holds $d_G(v,w)\le d_G(u,v)$. If also v is maximally distant from u, then u and v are said to be mutually maximally distant. The strong resolving graph $G _{\textrm{SR}}$ of G has $V(G _{\textrm{SR}}) = V(G)$ and two vertices being adjacent in $G _{\textrm{SR}}$ if they are mutually maximally distant in G. This notion was introduced in [14] as a tool to study the strong metric dimension. The paper [15] gives a survey on strong resolving graphs with an emphasis on the realization problem (which graphs have a given graph as their strong resolving graph) and the characterization problem (characterize graphs that are strong resolving graphs of some graphs). From our perspective, in [16] it was proved that $\textrm{gp}(G)\ge \omega (G _{\textrm{SR}})$ holds for any connected graph G.

Next we turn our attention to outer general position sets. Note first that if u and v are vertices of G such that $d_G(u,v) = \textrm{diam}(G)$, then $\{u,v\}$ is an outer general position set. Hence, if G is a connected graph of order at least 2, then $\textrm{gp}_{\textrm{o}}(G)\ge 2$. In general, outer general position sets can be characterized as follows.

Theorem 2.3

Let G be a connected graph and $X\subseteq V(G)$. Then X is an outer general position set of G if and only if each two vertices from X are mutually maximally distant. Moreover,

$$\begin{aligned} \textrm{gp}_{\textrm{o}}(G) = \omega (G _{\textrm{SR}}). \end{aligned}$$

Proof

Let $X\subseteq V(G)$ be a set with $|X|\ge 2$.

Assume first that X is an outer general position set of G and let $x,y\in X$. If x and y are not mutually maximally distant, there exists (at least) one neighbor of x or y, say $w\in N_G(x)$, such that $d_G(w,y) = d_G(x,y) + 1$. Hence there exists a shortest w, y-path which contains x. Then no matter whether $w\in X$ or $w\notin X$, this contradicts the fact that $\{x,y\}\subseteq X$ is an outer general position set.

Conversely, assume that any two vertices from X are mutually maximally distant. Consider any two vertices u and v. If $u,v\in X$, the internal vertices of all shortest u, v-paths are not from S as u and v are mutually maximally distant. Hence u and v are X-positionable. Assume next that, without loss of generality, $u\in X$ and $v\in V(G)\setminus X$. If there exists a vertex $w\in X\setminus \{u\}$ lying on a shortest u, v-path, then u and w are not mutually maximally distant. Hence u, v are X-positionable.

The formula $\textrm{gp}_{\textrm{o}}(G) = \omega (G _{\textrm{SR}})$ now follows by the above characterization of outer general position sets and by the definition of the strong resolving graph. $\square$

As already mentioned, it was proved in [16] that $\textrm{gp}(G)\ge \omega (G _{\textrm{SR}})$ holds for any connected graph G. Hence by Theorem 2.3 we have

$$\begin{aligned} \textrm{gp}(G)\ge \omega (G _{\textrm{SR}}) = \textrm{gp}_{\textrm{o}}(G). \end{aligned}$$

Thus, knowing that $\textrm{gp}(G) = \omega (G _{\textrm{SR}})$ holds for some graph G, we also know $\textrm{gp}_{\textrm{o}}(G)$. For instance, [16, Proposition 4.5] asserts that if $r_1\ge t_1\ge 1$ and $r_2\ge t_2\ge 1$, then

$$\begin{aligned} \textrm{gp}(K_{r_1,t_1}\boxtimes K_{r_2,t_2}) = r_1r_2 = \omega ((K_{r_1,t_1}\boxtimes K_{r_2,t_2}) _{\textrm{SR}}), \end{aligned}$$

which in turn implies that

$$\begin{aligned} \textrm{gp}_{\textrm{o}}(K_{r_1,t_1}\boxtimes K_{r_2,t_2}) = r_1r_2. \end{aligned}$$

3 Dual General Position Sets

From Theorem 2.1 it follows that if X is a total general position set of G, then each subset of X is also a total general position set of G. Similarly, by Theorem 2.3 this hereditary property also holds for outer general position sets. In addition, this property is also known to hold for general position sets. A bit surprisingly, if X is a dual general position set of G and $Y\subseteq X$, then Y need not be a dual general position set of G. To see this, consider two adjacent vertices of $C_5$ which form a dual general position set, however, one vertex of $C_5$ does not form such a set. So each of the properties of being in general position, being in total general position, and being in outer general position is hereditary, but the property of being in dual general position property is not.

The above consideration indicates that the dual general position is intrinsically different from the other three invariants. In this section we have a closer look to it. We first characterize which general position sets are dual general position sets. Then we respectively consider graphs G with $\textrm{gp}_{\textrm{d}}(G) = 0$, $\textrm{gp}_{\textrm{d}}(G) = 1$, and $\textrm{gp}_{\textrm{d}}(G) \ge 2$.

Let X be a dual general position set in a graph G. Then, clearly, X is a general position set. Hence to find a largest dual general position set in G if suffices to check all general position sets in G and check if they are also dual. For this task, the following result is useful.

Theorem 3.1

Let X be a general position set of a graph G. Then X is a dual general position set if and only if $G-X$ is convex.

Proof

Assume that X is a dual general position set. Let $x,y\in V(G)\setminus X$ and let P be a shortest x, y-path. Since X is a dual general position set, the vertices x and y are X-positionable which in turn implies that $V(P)\cap X = \emptyset$. It follows that $G-X$ is convex.

Conversely, assume that X is a general position set and $G-X$ is convex. If $x,y\in X$, then x and y are X-positionable since X is a general position set. Consider next $x,y\in V(G)\setminus X$. Since $G-X$ is convex, each shortest x, y-path lies in $G-X$ hence no such path contains vertices from X. We can conclude that X is a dual general position set. $\square$

For the later use we state explicitly the following consequence of Theorem 3.1.

Corollary 3.2

If G is a graph and $X\subseteq S(G)$, then X is a dual general position set.

Proof

Since $X\subseteq S(G)$ we see that X is a general position set and also that $G-X$ is convex. Hence the assertion follows by Theorem 3.1. $\square$

3.1 Graphs G with $\textrm{gp}_{\textrm{d}}(G) = 0$

In this subsection we focus on graphs G with $\textrm{gp}_{\textrm{d}}(G) = 0$. It follows from Theorem 3.1 that $\textrm{gp}_{\textrm{d}}(G) = 0$ if and only if for every general position set X the subgraph $G-X$ is not convex in G. Since dual general position sets are not hereditary (recall the example of $C_5$), we must consider all general position sets, not only singletons.

We say that an edge e of a graph G is $P_4$-inner isometric, if e is the middle edge of some isometric $P_4$.

Proposition 3.3

Let G be a connected graph. If each edge of G is $P_4$-inner isometric, then $\textrm{gp}_{\textrm{d}}(G)=0$.

Proof

Assume that G is a graph in which each edge is $P_4$-inner isometric. Then clearly $\delta (G)\ge 2$. Suppose on the contrary that $\textrm{gp}_{\textrm{d}}(G)\ge 1$ and let x be a vertex of G from some dual general position set X. Let y be a neighbor of x. From our assumption, the edge xy is $P_4$-inner isometric and let $x', x, y, y'$ be the vertices of an isometric $P_4$, denote it by Q, where $x'x\in E(G)$ and $yy'\in E(G)$. Then at least one of the vertices $x'$ and y belongs to X, for otherwise $x'$ and y are not X-positionable.

Suppose first that $y\in X$. It implies that $y'\not \in X$ for otherwise x and $y'$ are not X-positionable. Analogously, $x'\not \in X$ also holds. But then the vertices $x'$ and $y'$ are not X-positionable.

Suppose second that $x'\in X$. Then $y\notin X$, for otherwise y and $x'$ are not X-positionable. Consider now an isometric $P_4$, say R, such that the edge $x'x$ is the middle edge of R. Let R be the path on the vertices $z', x', x, z$, where $z'x'\in E(G)$ and $xz\in E(G)$. Since $x,x'\in X$ we see that $z'\notin X$ and $z\notin X$. Since Q is isometric, we have $z'\ne y$ and $z'\ne y'$. If $z=y$, then $z'$ and $z=y$ are not X-positionable. Similarly, if $z\ne y$, then again $z'$ and z are not X-positionable. This final contradiction implies that $\textrm{gp}_{\textrm{d}}(G) = 0$. $\square$

Corollary 3.4

Let G be a connected graph with $g(G) \ge 6$. Then $\textrm{gp}_{\textrm{d}}(G)=0$ if and only if $\delta (G)\ge 2$.

Proof

If $\delta (G) = 1$ and u is a pendant vertex of G, then $\{ u \}$ is a dual general position set, hence $\textrm{gp}_{\textrm{d}}(G)\ge 1$.

To prove the other direction, assume that $\delta (G)\ge 2$. Since $g(G)\ge 6$ we see that each edge of G is $P_4$-inner isometric. Proposition 3.3 yields the conclusion. $\square$

Next, we give an infinite family of graphs whose dual general position number is zero, yet none of their edges is $P_4$-inner isometric. Let $m\ge 5$ and consider the join graph $G_m = P_m \oplus 2K_1$, see Fig. 1.

Fig. 1

The graph $G_m$

It is readily verified that no edge of $G_m$ is $P_4$-inner isometric. On the other hand, the following holds.

Proposition 3.5

If $m\ge 5$, then $\textrm{gp}_{\textrm{d}}(G_m) = 0$.

Proof

Set $G_m=P_m\oplus 2K_1$, let $V(P_m)=\{p_1,\ldots ,p_m\}$ with natural adjacencies, and let $V(2K_1)=\{x,x'\}$, see Fig. 1 again.

Let X be an arbitrary dual general position set of $G_m$. If $x, x'\not \in X$, then $X = \emptyset$ for otherwise x and $x'$ are not X-positionable. In the rest we may hence assume without loss of generality that $x\in X$, for otherwise we are done.

We first claim that $x'\notin X$. Indeed, otherwise no vertex $p_i$, $i\in [m]$, lies in X, but then no two vertices $p_i$ and $p_j$, $|i - j|\ge 2$, are not X-positionable. Further and similarly, we have $\{p_1,\ldots ,p_m\}\cap X\ne \emptyset$. Hence there exists $i\in [m]$ such that $p_i\in X$. Select and fix i to be the smallest such index. Then by the symmetry we may assume that $1\le i\le \lceil m/2\rceil$. We now distinguish two cases.

Suppose first that $i=1$. Then it follows that $p_j\not \in X$ for $3\le j\le m$. Since $m\ge 5$, the vertex x lies in the middle of a shortest $p_3,p_m$-path, hence the vertices $p_3$ and $p_m$ are not X-positionable.

Suppose second that $2\le i\le \lceil m/2\rceil$. By the way i is selected and by the symmetry we have $p_1\notin X$ and $p_{m}\notin X$. But then $p_1$ and $p_m$ are not X-positionable. $\square$

For the cycles $C_4$ and $C_5$, it is observed that $\textrm{gp}_{\textrm{d}}(C_4)=\textrm{gp}_{\textrm{d}}(C_5)=2$. These graphs can be considered as special cases of generalized theta graphs which are defined as follows. For positive integers $1\le \ell _1\le \cdots \le \ell _k$ and $\ell _2\ge 2$, the generalized theta graph $\Theta (\ell _1,\ldots ,\ell _k)$ is obtained by joining two vertices a and b with k internally disjoint paths of lengths $\ell _1,\ldots , \ell _k$.

Proposition 3.6

Let $1\le \ell _1\le \cdots \le \ell _k$, where $k\ge 2$, $\ell _2\ge 2$. Then $\textrm{gp}_{\textrm{d}}(\Theta (\ell _1,\ldots ,\ell _k)) = 0$ if and only if one of the following cases holds:

• (i) $k=2$, $\ell _1+\ell _2\ge 6$;

• (ii) $k\ge 3$, $\ell _1=1$, $\ell _2\ge 5$;

• (iii) $k\ge 3$, $\ell _1=2$, and $\ell _i\ne 3$ for $2\le i\le k$;

• (iv) $k\ge 3$, $\ell _1\ge 3$.

Proof

Set $\Theta =\Theta (\ell _1,\ldots ,\ell _k)$ for the rest of the proof and let $Q_1,\ldots , Q_k$ be the internally disjoint paths of lengths $\ell _1,\ldots , \ell _k$ of $\Theta$ connecting a and b.

(i):

If $k=2$ and $\ell _1+\ell _2\le 5$, then $\Theta \in \{C_3, C_4, C_5\}$, hence $\textrm{gp}_{\textrm{d}}(\Theta )\ge 2$. On the other hand, if $\ell _1+\ell _2\ge 6$, then $\Theta$ is a cycle of order at least 6 and thus each edge of $\Theta$ is $P_4$-inner isometric. Hence $\textrm{gp}_{\textrm{d}}(\Theta ) = 0$ by Proposition 3.3.

(ii):

Let $k\ge 3$ and $\ell _1=1$. Assume first that $\ell _2\le 4$. If $\ell _2 = 2$, then the middle vertex of $Q_2$ is simplicial and by Corollary 3.2, $\{x\}$ is a dual general position set and so $\textrm{gp}_{\textrm{d}}(\Theta )\ge 1$. If $\ell _2 = 3$, then $\Theta [Q_1\cup Q_2]\cong C_4$. Let u and v be the internal vertices of $Q_2$. Then we infer that $\Theta -\{u,v\}$ is convex and using Theorem 3.1 we get $\textrm{gp}_{\textrm{d}}(\Theta )\ge 2$. Similarly, we get that $\textrm{gp}_{\textrm{d}}(\Theta )\ge 2$ if $\ell _2 = 4$. Assume finally that $\ell _2\ge 5$. Then each edge of $\Theta$ is $P_4$-inner isometric. By Proposition 3.3 we thus have $\textrm{gp}_{\textrm{d}}(\Theta ) = 0$.

(iii):

Let $k\ge 3$ and $\ell _1=2$. Assume first that there exists an index i such that $\ell _i = 3$ and let i be the smallest such index. Note that $i\ge 2$. If $x_i$ and $x_i'$ are the two internal vertices of $Q_i$, then $\Theta - \{x_i,x_i'\}$ is convex, hence Theorem 3.1 implies that $\textrm{gp}_{\textrm{d}}(\Theta )\ge 2$. Assume second that $\ell _i \ne 3$ for each $2\le i\le k$. If $\ell _1 = \cdots = \ell _k = 2$, then $\Theta \cong K_{2,k}$. A possible dual general position set wound need to contain two adjacent vertices of each 4-cycle, but this is not possible. So $\textrm{gp}_{\textrm{d}}(K_{2,k}) = 0$ for $k\ge 3$. Let next j be the smallest index such that $\ell _j \ge 4$, so that $\ell _1 = \cdots = \ell _{j-1} = 2$. (It is possible that $j=2$.) Then the subgraph of $\Theta$ induced by $Q_1\cup \cdots \cup Q_{j-1}$ is isomorphic to $K_{2,j-1}$ and we readily see that no vertex from it can lie in a dual general position set. In addition, the vertices from $Q_1\cup Q_{j'}$, where $j'\ge j$, induce an isometric cycle of $\Theta$ of order at least 6, from which we conclude that none of the vertices from the cycle can lie in a dual general position set. We conclude that $\textrm{gp}_{\textrm{d}}(\Theta ) = 0$.

(iv):

In this case we have $g(\Theta ) \ge 6$, hence the assertion follows by Corollary 3.4.

$\square$

3.2 Graphs G with $\textrm{gp}_{\textrm{d}}(G) = 1$

We next consider graphs G with $\textrm{gp}_{\textrm{d}}(G) = 1$.

Proposition 3.7

If G is a connected graph with $\textrm{gp}_{\textrm{d}}(G) = 1$, then $s(G) = 1$.

Proof

Let G be a connected graph with $\textrm{gp}_{\textrm{d}}(G) = 1$ and let $\{x\}$ be a $\textrm{gp}_{\textrm{d}}$-set of G. Suppose first that $s(G) = 0$. Then it follows that the order of G is at least 4 as each of the smaller graphs contains at least one simplicial vertex. In particular, since x is not simplicial, it has two neighbors, say $x'$ and $x''$, such that $d_G(x',x'')=2$. But then $x'$ and $x''$ are not $\{x\}$-positionable. This contradiction implies that $s(G)\ge 1$. On the other hand, Corollary 3.2 yields that $s(G)\le 1$ and we are done. $\square$

The converse of Proposition 3.7 is not true. For a sporadic example consider the graph G obtained from $C_4$ by attaching a pendant vertex to one of the vertices of $C_4$. Then $\textrm{gp}_{\textrm{d}}(G) = 2 \ne 1$ but $s(G) = 1$. An infinite family of such examples is the following. For integers $k\ge 1$ and $\ell \ge 4$, let $G_{k,\ell }$ be the graph consisting of a chain of k cycles $C_\ell$ which share vertices such that for an intermediate $C_\ell$ its vertices of degree 3 are its diametral vertices. Finally attach a pendant vertex to a degree 2 vertex of the last cycle. In Fig. 2 the graphs $G_{6,4}$ and $G_{6,5}$ are shown.

Fig. 2

Graphs $G_{6,4}$ and $G_{6,5}$ and their largest dual general position sets

Proposition 3.8

If $k\ge 1$ and $\ell \ge 4$, then

$$\begin{aligned} \textrm{gp}_{\textrm{d}}(G_{k,\ell }) = \left\{ \begin{array}{ll} 1; & \ell \ge 6,\\ 2; & \ell =4,\\ 3; & \ell =5.\\ \end{array}\right. \end{aligned}$$

Proof

Let $e = uv$ be the pendent edge of $G_{k,\ell }$, where u is the pendant vertex. Since u is a simplicial vertex of $G_{k,\ell }$, Corollary 3.2 implies $\textrm{gp}_{\textrm{d}}(G_{k,\ell })\ge 1$.

Assume first $\ell \ge 6$. Since $g(G_{k,\ell })\ge 6$ and each edge of $G_{k,\ell }-u$ is $P_4$-inner isometric, no vertex of $G_{k,\ell }-u$ lies in a dual general position set of $G_{k,\ell }$, cf. Corollary 3.4. Hence we have $\textrm{gp}_{\textrm{d}}(G_{k,\ell })\le 1$ and thus $\textrm{gp}_{\textrm{d}}(G_{k,\ell }) = 1$.

Assume second $\ell = 4$. Let $i, i', j, j'$ be the vertices of the first $C_4$ as indicated in Fig. 2. Since $\{i,i'\}$ is a general position set of $G_{k,\ell }$ and $G_{k,\ell }-\{i,i'\}$ is convex, Theorem 3.1 implies that $\textrm{gp}_{\textrm{d}}(G_{k,\ell })\ge 2$. Suppose on the contrary that $\textrm{gp}_{\textrm{d}}(G_{k,\ell })\ge 3$ and let X be an arbitrary $\textrm{gp}_{\textrm{d}}$-set of $G_{k,\ell }$.

Assume that X contains a vertex x with $\deg _{G_{k,\ell }}(x) = 4$. Then at least three neighbors of x lie in X for, otherwise two neighbors of x are not X-positionable. But then again two neighbors of x are not X-positionable. By a parallel argument we also see that X does not contain the vertex of degree 3. It follows that each vertex of X is of degree at most 2.

We claim that $u\notin X$. Since $|X|\ge 3$, there exist $y, y'\in X$ such that $\deg _{G_{k,\ell }}(y) = \deg _{G_{k,\ell }}(y') = 2$. (It is possible $y,y'\in \{i,i',j\}$.) If y and $y'$ are adjacent, then we may without loss of generality assume that $y=i$ and $y' = i'$. But then $i'$ and u are not X-positionable, so this cannot happen. Assume next that y and $y'$ are not adjacent. Let z and $z'$ be the two neighbors of y. It is clear that z and $z'$ are not X-positionable if y and $y'$ lie on the same cycle $C_4$. And if y and $y'$ are not on the same 4-cycle, then either y lies on a shortest $u,y'$-path or $y'$ lies on the shortest u, y-path. We conclude that indeed $u\notin X$.

We have thus proved that $\deg _{G_{k,\ell }}(x) = 2$ for each $x\in X$. Let x and $x'$ be two arbitrary vertices from X. By the same argument as used in the previous paragraph we get that $xx'\in E(G_{k,\ell })$. As there are only two such edges possible, that is, $ii'$ and $i'j$, and as $\{i,i',j\}$ is not a dual general position set, we can conclude that $\{i,i'\}$ is a largest dual general position set and so $\textrm{gp}_{\textrm{d}}(G_{k,\ell }) = 2$.

The argument for the case $\ell = 5$ is similar and left to the reader. $\square$

3.3 Graphs G with $\textrm{gp}_{\textrm{d}}(G) \ge 2$

We next consider when a set of cardinality two forms a dual general position set. In the next result we deduce a characterization (additional to the one of Theorem 3.1) for two adjacent vertices.

Theorem 3.9

If x and y are two adjacent vertices of a graph G, then the following statements are equivalent.

• (i) $\{x,y\}$ is a dual general position set of G;

• (ii) $G-\{x,y\}$ is convex;

• (iii) For each $u,v\in N_G(x)\cup N_G(y)$ we have $d_{G}(u,v)\le 2$, and the graphs $G[N_G(x)-\{y\}]$ and $G[N_G(y)-\{x\}]$ are complete.

Proof

Let $X=N_G(x)-\{y\}$ and $Y=N_G(y)-\{x\}$.

$(i) \Rightarrow (ii)$::

If $\{x,y\}$ is a dual general position set of G, it follows from Theorem 3.1 that $G-\{x,y\}$ is convex.

$(ii) \Rightarrow (iii)$::

Assume that $G-\{x,y\}$ is convex. Then G[X] is complete. Indeed, for otherwise two nonadjacent vertices $x'$ and $x''$ from X are not $\{x,y\}$-positionable. Analogously, G[Y] is complete. Furthermore, if $u\in X$ and $v\in Y$, then $d_G(u,v) \le 3$. But if $d_G(u,v) = 3$, then $G-\{x,y\}$ is not convex, hence we conclude that $d_{G}(u,v)\le 2$ for any $u,v\in N_G(x)\cup N_G(y)$.

$(iii) \Rightarrow (i)$::

Let $1\le d_{G}(u,v)\le 2$ for any two vertices $u,v\in N_G(x)\cup N_G(y)$, and let G[X] and G[Y] be complete. Set $G'=G-\{x,y\}$. Consider two arbitrary distinct vertices p and q from $G'$. We claim that no shortest p, q-path passes x or y. Let Q be an arbitrary shortest p, q-path. Suppose first that $V(Q) \cap \{x,y\} = \{x\}$. Then Q contains two neighbors of x but since G[X] is complete, this is a contradiction. The case when $V(Q) \cap \{x,y\} = \{y\}$ is ruled out analogously. In the remaining case suppose that $V(Q) \cap \{x,y\} = \{x,y\}$. Then Q contains a subpath $x', x, y, y'$, where $x'\in X$ and $y'\in Y$. But by our assumption $d_G(x',y') \le 2$, a contradiction with the assumption that Q is a shortest path. We conclude that u and v are $\{x,y\}$-positionable and consequently $\{x,y\}$ is a dual general position set.

$\square$

A result parallel to Theorem 3.9 for two nonadjacent vertices is simpler and reads as follows.

Proposition 3.10

Let x and y be two non-adjacent vertices of a graph G. Then the set $\{x,y\}$ is a dual general position set if and only if x and y are simplicial vertices.

Proof

Assume first that $\{x,y\}$ is a dual general position set. Then x is simplicial for otherwise there exist two neighbors u and v of x such that $d_G(u,v) = 2$. By our assumption, $u\ne y$ and $v\ne y$, but then u and v are not $\{x,y\}$-positionable. Analogously y is simplicial. The reverse implication follows by Corollary 3.2. $\square$

4 The Variety in Cartesian Products

To determine the general position number of Cartesian product graphs is a difficult problem and has been already widely investigated. It took several intermediately steps before the general position number of integer lattices (alias Cartesian products of a finite number of paths) has been determined [17]. Bounds on the general position number of Cartesian products of arbitrary graphs were independently proved in [5, 18]. Special Cartesian products were studied in [19] (products of two trees), in [20] (products of paths and cycles), and in [20, 21] (products of two cycles).

In this section we determine the total general position number, the outer general position number, and the dual general position number of arbitrary Cartesian products. For this purpose, we need some additional notation and terminology on Cartesian products. Let G and H be graphs and consider $G\,\square \,H$. Given a vertex $h\in V(H)$, the subgraph of $G\,\square \,H$ induced by the set of vertices $\{(g,h):\ g\in V(G)\}$, is a G-layer and is denoted by $G^h$. H-layers $^gH$ are defined analogously. Each G-layer and each H-layer is isomorphic to G and H, respectively. If $X\subseteq V(G\,\square \,H)$, the projection $p_G(X)$ of X to G is the set $\{g\in V(G):\ (g,h)\in X\ \mathrm{for\ some}\ h\in V(H)\}$. The projection $p_H(X)$ of X to H is defined analogously.

For total general position sets, Corollary 2.2 implies:

Corollary 4.1

If G and H are connected graphs of order at least 2, then $\textrm{gp}_{\textrm{t}}(G\,\square \,H) = 0$.

Proof

It is straightforward to see that $G\,\square \,H$ contains no simplicial vertices. $\square$

For outer general position sets, the following result is useful.

Theorem 4.2

[22, Theorem 3] If G and H are connected graphs, each of order at least 2, then $(G\,\square \,H) _{\textrm{SR}}\cong G _{\textrm{SR}}\times H _{\textrm{SR}}$.

Theorem 4.3

If G and H are two connected graphs, each of order at least 2, then

$$\begin{aligned} \textrm{gp}_{\textrm{o}}(G\,\square \,H) = \min \{\textrm{gp}_{\textrm{o}}(G),\textrm{gp}_{\textrm{o}}(H)\}. \end{aligned}$$

Proof

By Theorem 2.3 we have $\textrm{gp}_{\textrm{o}}(G\,\square \,H) = \omega ((G\,\square \,H) _{\textrm{SR}})$. Theorem 4.2 implies that $\omega ((G\,\square \,H) _{\textrm{SR}}) = \omega (G _{\textrm{SR}}\times H _{\textrm{SR}})$. Since $\omega (G\times H) = \min \{\omega (G), \omega (H)\}$, see [23, Exercise 16.1], we have $\textrm{gp}_{\textrm{o}}(G\,\square \,H) =\min \{\omega (G _{\textrm{SR}}),\omega (H _{\textrm{SR}})\}$. Using Theorem 2.3 again we conclude that $\textrm{gp}_{\textrm{o}}(G\,\square \,H) = \min \{\textrm{gp}_{\textrm{o}}(G),\textrm{gp}_{\textrm{o}}(H)\}$. $\square$

Corollary 4.4

If $m, n\ge 3$, then $\textrm{gp}_{\textrm{o}}(K_m\,\square \,K_n) = \min \{m, n\}$.

For dual general position sets, the following result that characterizes convex subgraphs of Cartesian product graphs will be applied.

Lemma 4.5

[23, Lemma 6.5] A subgraph W of $G=G_1\,\square \,\cdots \,\square \,G_k$ is convex if and only if $W=U_1\,\square \,\cdots \,\square \,U_k$, where each $U_i$ is convex in $G_i$.

Theorem 4.6

Let G and H be two graphs, each of order at least 2. Then $\textrm{gp}_{\textrm{d}}(G\,\square \,H) > 0$ if and only if one factor is complete and the other factor has a simplicial vertex. Moreover,

• (i) $\textrm{gp}_{\textrm{d}}(K_n\,\square \,K_m) = \max \{n,m\}$, and

• (ii) if H is not complete and contains a simplicial vertex, then $\textrm{gp}_{\textrm{d}}(K_n\,\square \,H) = n$.

Proof

Set $V(G)=[n]$ and $V(H)=[m]$. So we have $V(G\,\square \,H) = [n]\times [m]$.

Assume first that $\textrm{gp}_{\textrm{d}}(G\,\square \,H) > 0$ and let X be a dual general position set of $G\,\square \,H$. Then X is clearly a general position set of $G\,\square \,H$ and hence by Theorem 3.1, $K = (G\,\square \,H) - X$ is a convex subgraph of $G\,\square \,H$. Consequently, by Lemma 4.5 we infer that $K = G' \,\square \,H'$, where $G'$ is convex in G and $H'$ is convex in H. Suppose that $G'$ and $H'$ are proper subgraphs of G and H, respectively. Then there exist vertices $g\in V(G)\setminus V(G')$ and $h\in V(H)\setminus V(H')$, such that g has a neighbor $g'\in V(G)$ and h has a neighbor $h'\in V(H)$. Then $(g',h), (g,h), (g,h')$ is an induced path of $G\,\square \,H$, where all its vertices are from X, a contradiction.

By the above contradiction, $p_G(X) = V(G)$ or $p_H(X) = V(H)$. We may without loss of generality assume that $p_G(X) = V(G)$. Since layers in Cartesian products are convex, this implies that V(G) is a general position set in G which in turn implies that G is a complete graph. Moreover, since X is a general position set we also see that $|p_H(X)| = 1$ and let h be the unique vertex of H to which X projects. Now, if h is not a simplicial vertex of H, then there exist vertices $h', h''\in N_H(h)$ such that $h'h''\notin E(H)$. But then K is clearly not convex, hence h must be a simplicial vertex of H.

To complete the argument we observe that if G is complete and $h\in V(H)$ is a simplicial vertex, then by Theorem 3.1 the set $V(G)\times \{h\}$ is a dual general position set.

The two formulas in the cases when $\textrm{gp}_{\textrm{d}}(G\,\square \,H) > 0$ follow directly from the above discussion. $\square$

In [18, Theorem 3.8] it is proved that $\textrm{gp}(K_m \,\square \,K_n) = m + n - 2$. Combining this result with Corollary 4.4 and Theorem 4.6 we see that the four general position invariants considered can vary arbitrary. For instance, for any $n\ge 3$ we have:

$$\begin{aligned} \textrm{gp}(K_n\,\square \,K_{2n})&= 3n - 2,\\ \textrm{gp}_{\textrm{d}}(K_n\,\square \,K_{2n})&= 2n, \\ \textrm{gp}_{\textrm{o}}(K_n\,\square \,K_{2n})&= n, \\ \textrm{gp}_{\textrm{t}}(K_n\,\square \,K_{2n})&= 0. \end{aligned}$$

5 Concluding Remarks

In this paper we have introduced the variety of general position sets. We have completely described the total general position sets and the outer general position sets. On the other hand, we have observed that the dual general position sets are not hereditary. This fact makes the investigation of dual general position sets quite tricky. For instance, we have given a sufficient condition for a graph G to satisfy $\textrm{gp}_{\textrm{d}}(G) = 0$, yet we were not been able to characterize graphs G with this property. The same problems remains open for the case $\textrm{gp}_{\textrm{d}}(G) = 1$.

We have seem that if G is a block graph, then $\textrm{gp}(G) = \textrm{gp}_{\textrm{o}}(G) = \textrm{gp}_{\textrm{d}}(G) = \textrm{gp}_{\textrm{t}}(G)$. It would be an interesting project to characterize the graphs for which this holds. Moreover, the same question can be posed for each subsets of the involved invariants, for instance, to characterize the graphs G for which $\textrm{gp}(G) = \textrm{gp}_{\textrm{d}}(G)$ holds.

Finally we comment on the complexity point of view. As already mentioned in the introduction, finding a largest general position set is an NP-hard problem. On the other hand, Theorem 2.1 implies that a largest total general position set in a graph is unique and can be found in polynomial time. The complexity of finding a largest outer general position set and of finding a largest dual general position set is not known yet. By Theorem 2.3, the first problem is equivalent to determining the clique number of a strong resolving graph and we suspect that this could be difficult. In addition, we also suspect (in view of Theorem 3.1) that finding a largest dual general position set is also difficult.