Keywords: total general position; outer general position; dual general position; vertex-deleted subgraph; edge-deleted subgraph

AMS Subj.Class.(2020): 05C12, 05C69

1 Introduction↩︎

The concept of a general position set was introduced into graph theory independently in two papers, namely in [1], [2], but in the case of hypercubes implicitly also much earlier in [3]. It was the article [2] that has stimulated a great deal of interest in this concept. The survey [4] provides a systematic review of the results, in addition we point to the following selected recent publications [5]–[13].

For a general position set, one requires that the vertices of the set are in general position. This requirement can be generalized by requiring that the vertices of some set lie in general position with respect to the selected set. Using this idea, and considering the natural selections for sets to be considered, in [14] a variety of general position sets was defined as follows. First, for a given graph \(G = (V (G), E(G))\) and a set of vertices \(Z \subseteq V (G)\), two vertices \(x, y \in V(G)\) are said to be \(Z\)-positionable if any shortest \(x,y\)-path intersects \(Z\) at most in \(x\) and \(y\), that is, no inner vertex of the path lies in \(Z\). Second, if \(\overline{Z} = V(G)\setminus Z\), then the set \(Z\) is

1. a general position set, if every \(u, v \in Z\) are \(Z\)-positionable;

2. a total general position set, if every \(u, v \in V(G)\) are \(Z\)-positionable;

3. an outer general position set, if every \(u, v \in Z\) are \(Z\)-positionable, and every \(u \in Z\), \(v \in \overline{Z}\) are \(Z\)-positionable; and

4. a dual general position set, if every \(u, v \in Z\) are \(Z\)-positionable, and every \(u, v \in \overline{Z}\) are \(Z\)-positionable.

Typically, we are interested in the cardinalities of largest such sets, which are respectively denoted by \({\rm gp}(G)\), \({\rm gp}_{\rm t}(G)\), \({\rm gp}_{\rm o}(G)\), and \({\rm gp}_{\rm d}(G)\), and called the general position number, the total general position number, the outer general position number, and the dual general position number of \(G\). If \(\tau \in \{{\rm gp}, {\rm gp}_{\rm t}, {\rm gp}_{\rm o}, {\rm gp}_{\rm d}\}\), then a set \(Z\) is a \(\tau\)-set if it has the corresponding property and \(|Z| = \tau(G)\). Note that, by definition, \({\rm gp}_{\rm t}(G)\le {\rm gp}_{\rm o}(G)\le {\rm gp}(G)\) and \({\rm gp}_{\rm t}(G)\le {\rm gp}_{\rm d}(G)\le {\rm gp}(G)\). After being introduced in [14], this variety has been also investigated on strong and lexicographic products of graphs [15].

The paper [16] investigates how removing a vertex or an edge affects the general position number of a graph. It is proved that \({\rm gp}(G-x)\leq 2{\rm gp}(G)\) holds for any vertex \(x\) of a connected graph \(G\) and that if \(x\) lies in some \({\rm gp}\)-set of \(G\), then \({\rm gp}(G) - 1 \le {\rm gp}(G-x)\). On the other hand, \({\rm gp}(G-x)\) can be much larger than \({\rm gp}(G)\) also when \(G-x\) is connected. For the edge removal it is proved that \({\rm gp}(G)/2\le {\rm gp}(G-e)\leq\;2{\rm gp}(G)\) holds for any edge \(e\) of \(G\). In this paper we continue this line of research by investigating how removing a vertex or an edge affects the other three general position numbers.

In the next section we give definitions and recall results needed in the rest of the paper. In Section 3 we consider the vertex removal. For the total general position sets we prove that if \(x\) is not a cut vertex, then \({\rm gp}_{\rm t}(G) -1 \le {\rm gp}_{\rm t}(G-x) \le {\rm gp}_{\rm t}(G) + \deg_G(x)\). Section 3.2 addresses the outer general position number and informs that anything can happen with outer general position sets when a vertex is removed. On the other hand, if \(x\) lies in some \({\rm gp}_{\rm o}\)-set, then \({\rm gp}_{\rm o}(G)-1 \le {\rm gp}_{\rm o}(G-x)\). Moreover, if \(x\) is a simplicial vertex, then \({\rm gp}_{\rm o}(G-x) \le {\rm gp}_{\rm o}(G)+\deg_G(x)-1\). Section 3.3 then deals with the dual general position number. Similarly, as for the outer general position number, \({\rm gp}_{\rm d}(G-x)\) can be arbitrarily larger/smaller than \({\rm gp}_{\rm d}(G)\). On the other hand, if \(x\) is not a cut vertex and lies in some \({\rm gp}_{\rm d}\)-set of \(G\), then \({\rm gp}_{\rm d}(G)-1 \le {\rm gp}_{\rm d}(G-x)\). In the final section we consider the edge removal operation. For the total and the outer general position number we prove sharp lower and upper bounds, while for the dual general position number we show that the difference \({\rm gp}_{\rm d}(G) - {\rm gp}_{\rm d}(G-e)\) can be arbitrarily large. All bounds proved in this paper are demonstrated to be sharp.

2 Preliminaries↩︎

We consider simple and connected graphs \(G=(V(G), E(G))\). For a positive integer \(k\), the set \(\{1,\ldots, k\}\) is denoted by \([k]\).

Let \(u\in V(G)\). Then \(N_G(u)\) denotes the set of neighbors of \(u\) in \(G\) and \(N_G[u] = N_G(u)\cup \{u\}\). The degree \(\deg_G(u)\) of \(u\) is \(\deg_G(u) = |N_G(u)|\). If \(X\subseteq V(G)\), then the subgraph of \(G\) induced by \(X\) is denoted by \(G[X]\). The graph \(G-u\) is obtained by deleting \(u\) and all incident edges from \(G\), that is, \(G-u\) is the subgraph \(G[V(G)\setminus \{u\}]\). For an edge \(e \in E(G)\), the graph \(G-e\) is obtained by deleting the edge \(e\) from \(G\). A vertex \(u\) of \(G\) is simplicial if \(N_G(u)\) 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)\). Moreover, \(\omega(G)\) and \(\alpha(G)\) stand for the clique number and the independence number of \(G\).

The distance \(d_G(u,v)\) between vertices \(u\) and \(v\) of \(G\) is the number of edges on a shortest \(u,v\)-path. Let \(H\) be a subgraph of \(G\). Then \(H\) is convex if for any vertices \(u,v\in V(H)\), any shortest \(u,v\)-path in \(G\) lies completely in \(H\). By abuse of language, we will also say that a set \(X\subseteq V(G)\) is convex if \(X\) induces a convex subgraph.

The vertex \(u\) of \(G\) is maximally distant from a vertex \(v\in V(G)\) if every \(w\in N_G(u)\) satisfies \(d_G(v,w)\le d_G(u,v)\). If \(u\) is maximally distant from \(v\), and \(v\) is also maximally distant from \(u\), then \(u\) and \(v\) are mutually maximally distant, MMD for short. Note that true twins, that is, vertices \(u\) and \(v\) with \(N_G[u] = N_G[v]\), are MMD. The strong resolving graph \(G{}_{\rm SR}\) of \(G\) has \(V(G)\) as the vertex set, two vertices being adjacent in \(G{}_{\rm SR}\) if they are MMD in \(G\). This concept was introduced in [17] for the purpose of better understanding the strong metric dimension of graphs.

The first known result which we need later on describes general position sets in an arbitrary graph. To state it, some more definitions are required. If \({\cal P} = \{X_1, \ldots, X_t\}\) a partition of \(X\subseteq V(G)\), then \({\cal P}\) is distance-constant if for any \(i,j\in [t]\), \(i\ne j\), there exists a constant \(p_{ij}\), such that \(d_G(x,y) = p_{ij}\) for every \(x\in X_i\), \(y\in X_j\). If so, we set \(d_G(X_i,X_j) = p_{ij}\). A distance-constant partition \({\cal P}\) is in-transitive if \(p_{ik} \ne p_{ij} + p_{jk}\) holds for \(i,j,k\in [t]\).

The following theorem is the most important for us since it contains characterizations of the three variants of general position sets. They were respectively proved in [14].

We conclude the preliminaries with the following straightforward, but very useful observation.

3 Vertex removal↩︎

Before we turn our attention to vertex-deleted subgraphs in specific variants of general position sets, we consider the following example which is useful to understand each of the three invariants investigated. Let \(G_n\), \(n\ge 2\), be the graph, and \(x\) its vertex as shown in Fig. 1.

Since \(s(G_n) = 2n\), Theorem 2(i) yields \({\rm gp}_{\rm t}(G_n) = 2n\). Observe that two vertices of \(G_n\) are MMD if and only if they are leaves. Hence \({\rm gp}_{\rm o}(G_n) = 2n\) by Theorem 2(ii). By Lemma 1 we also have \({\rm gp}_{\rm d}(G_n)\geq 2n\). To prove the reverse inequality, we will apply Theorem 2(iii). For this sake we first get by a case analysis that \({\rm gp}(G_n) = 2n+1\). By symmetry, the only \({\rm gp}\)-sets to be considered are \(X_1\cup X_2 \cup\{v\}\), \(X_2\cup Y \cup\{u\}\), \(X_2\cup Y \cup\{v\}\), and \(X_2\cup Y \cup\{w\}\). If \(Z\) is any of these sets, then \(G_n - Z\) is not connected, hence clearly not convex. Theorem 2(iii) thus implies that none of these sets is a dual general position set. It follows that \({\rm gp}_{\rm d}(G_n)\le 2n\) and we can conclude that \({\rm gp}_{\rm d}(G_n) = 2n\).

Since the graph \(G_n - x\) is a tree, Lemma 1 gives \[{\rm gp}_{\rm t}(G_n-x) = {\rm gp}_{\rm o}(G_n-x) = {\rm gp}_{\rm d}(G_n-x) = s(G_n-x) = 4n\,,\] and we are done. \(\square\)

3.1 Total general position sets↩︎

In this subsection we show that the total general position set of \(G-x\) can be bounded below and above when \(x\) is not a cut vertex of graph \(G\).

The bounds clearly hold if \(G\) is complete, hence assume in the rest of the proof that \(G\) is not complete.

Let \(X\) be a \({\rm gp}_{\rm t}\)-set of \(G\). Then \(X = S(G)\) by Theorem 2(i).

To prove the lower bound it suffices to show that \(X\setminus\{x\} \subseteq S(G-x)\). Suppose on the contrary that \(y \in X\setminus\{x\}\) is not simplicial in \(G-x\). Then there exist \(z,w \in N_{G-x}(y)\) such that \(z\) and \(w\) are not adjacent in \(G-x\). The vertices \(z\) and \(w\) are also not adjacent in \(G\), but then \(y\) is not simplicial in \(G\), a contradiction. Hence \(X\setminus\{x\} \subseteq S(G-x)\) and by applying Theorem 2(i) we get \({\rm gp}_{\rm t}(G) -1 \le {\rm gp}_{\rm t}(G-x)\). This proves the lower bound.

For the upper bound observe that if \(y\in V(G)\setminus N_G[x]\) is a simplicial vertex of \(G-x\), then \(y\) is a simplicial vertex of \(G\). Using Theorem 2(i) once more we can argue as follows: \[{\rm gp}_{\rm t}(G-x) = s(G-x) \le s(G) + \deg_G(x) = {\rm gp}_{\rm t}(G) + \deg_G(x)\,.\] This proves the upper bound in the general case. Assume now that \(x\) is a simplicial vertex. Since \(G\) is not complete, at least one vertex in \(N_G(x)\) is not simplicial in \(G-x\), hence \[{\rm gp}_{\rm t}(G-x) = s(G-x) \le s(G) + (\deg_G(x) - 1) = {\rm gp}_{\rm t}(G) + \deg_G(x) - 1\,.\]

To show that the lower bound is sharp, consider the stars \(K_{1,n}, n \ge 3\). Clearly, \(s(K_{1,n}) = n\) and then \(s(K_{1,n}-x) = n-1\) for any leaf \(x\) of \(K_{1,n}\). To demonstrate that the upper bound is tight, consider complete bipartite graphs \(K_{2,n}\), \(n\ge 3\). If \(x\) is a vertex of \(K_{2,n}\) of degree \(n\), then we have \({\rm gp}_{\rm t}(K_{2,n}) = 0\) and \({\rm gp}_{\rm t}(K_{2,n}-x) = n = {\rm gp}_{\rm t}(K_{2,n})+\deg_{K_{2,n}}(x)\). Finally, to show that the upper bound is sharp in the case when \(x\) is a simplicial vertex, consider the edge deleted complete graph \(K_n-e\) and let \(x_1\) and \(x_2\) be the vertices of \(K_n-e\) of degree \(n-2\). Then \(S(K_n-e) = \{x,y\}\), so that \({\rm gp}_{\rm t}(K_n-e) = 2\). On the other hand, \((K_n-e)-x_1\cong K_{n-1}\). Hence \({\rm gp}_{\rm t}((K_n-e)-x_1) = n-1 = {\rm gp}_{\rm t}(K_n-e) + \deg_{K_n-e}(x_1) - 1\). \(\square\)

3.2 Outer general position sets↩︎

In this subsection we show that anything can happen with outer general position sets when a vertex of a graph \(G\) is removed.

To demonstrate that \({\rm gp}_{\rm o}(G-x)\) can be arbitrarily larger than \({\rm gp}_{\rm o}(G)\), consider the graph \(G_n\), \(n\ge 2\), from Fig. 1. By Proposition 3, \({\rm gp}_{\rm o}(G_n) = 2n\) and \({\rm gp}_{\rm o}(G_n-x) = 4n\).

To show that \({\rm gp}_{\rm o}(G-x)\) can also be arbitrarily smaller than \({\rm gp}_{\rm o}(G)\), consider the fan graph \(F_n\), \(n\ge 3\), of order \(n+1\), which is obtained from \(P_n\) and a vertex adjacent to all the vertices of \(P_n\). Let \(x\) be the vertex of \(F_n\) of degree \(n\). In [15] it is proved that if \(G\) is a diameter \(2\) graph with no true twins, then \({\rm gp}_{\rm o}(G) = \alpha(G)\). Since \(F_n-x\cong P_n\), we thus have \[{\rm gp}_{\rm o}(F_n) = \lceil n/2\rceil\quad {\rm and}\quad {\rm gp}_{\rm o}(F_n-x) = 2\,.\]

On the other hand, in the case when a vertex \(x\) lies in some \({\rm gp}_{\rm o}\)-set, we can bound \({\rm gp}_{\rm o}(G-x)\) from below as follows.

Let \(X\) be a \({\rm gp}_{\rm o}\)-set of \(G\) such as \(x \in X\). Then \(|X| = {\rm gp}_{\rm o}(G)\) and by Theorem 2(ii), every pair of vertices in \(X\) are MMD in \(G\).

To show the bound, it suffices to prove the assertion that \(X\setminus\{x\}\) is an outer general position set of \(G-x\). Given Theorem 2(ii) this is equivalent to proving that every two vertices in \(X\setminus \{x\}\) are MMD in \(G-x\). Suppose on the contrary that there exist \(u, v \in X\setminus \{x\}\) such that \(u\) and \(v\) are not MMD in \(G-x\). By symmetry we may assume that there exists \(u' \in N_{G-x}(u)\) such that \(d_{G-x}(u',v) = d_{G-x}(u,v) + 1\). Since \(u\) and \(v\) are MMD in \(G\), we have \(d_{G}(u',v) \le d_{G}(u,v)\). This implies that \(x\) lies on some shortest \(u',v\)-path in \(G\). But then \(v\) and \(x\) are not MMD in \(G\), a contradiction. This contradiction implies that every pair of vertices in \(X\setminus \{x\}\) are MMD in \(G-x\). We can conclude that \({\rm gp}_{\rm o}(G-x) \ge |X\setminus \{x\}| = {\rm gp}_{\rm o}(G) -1\).

For sharpness of the bound, consider the stars \(K_{1,n}\), \(n \ge 3\). Then \({\rm gp}_{\rm o}(K_{1,n}) = n\) and \({\rm gp}_{\rm o}(K_{1,n}-x) = n-1\) for any leaf \(x\) of \(K_{1,n}\). \(\square\)

By Theorem 5 we can thus bound \({\rm gp}_{\rm o}(G-x)\) from below when \(x\) is not a cut vertex and lies in some \({\rm gp}_{\rm o}\)-set of \(G\). As a possible general upper bound on \({\rm gp}_{\rm o}(G-x)\) we pose:

If Conjecture 6 holds true, then it is sharp as justified by Proposition 3. For the case when \(x\) is a simplicial vertex, the conjecture holds true, and even more is true:

Let \(u\) and \(v\) be arbitrary vertices of \(G-x\). Since \(x\) is a simplicial vertex of \(G\), no shortest \(u,v\)-path in \(G\) contains \(x\) which in turn implies that a \(u,v\)-path is shortest in \(G\) if and only if it is shortest in \(G-x\). Consequently, if \(u,v\in V(G)\setminus N_G[x]\), then \(u, v\) are MMD in \(G\) if and only if they are MMD in \(G-x\).

Let \({\rm gp}_{\rm o}(G) = k\) and let \(X\) be a largest set of pairwise MMD vertices of \(G\). Note that \(x\in X\). Let further \(Y\) be a largest set of pairwise MMD vertices of \(G-x\). Then by the above, \(|Y\cap (V(G)\setminus N_G[x])| \le k-1\). This in turn implies that \[|Y| \le (k-1) + |N_G(x)| = {\rm gp}_{\rm o}(G) - 1 + \deg_G(x)\,,\] which proves the bound.

Let \(G_{n,k}\), \(k < \frac{n+1}{2}\), be the graph obtained from \(K_n\) and another vertex \(x\) which is adjacent to \(k\) vertices of \(K_n\). Then \({\rm gp}_{\rm o}(G_{n,k}) = \max \{n-k+1, k\} = n-k+1\), where the last equality holds because we have assumed that \(k < \frac{n+1}{2}\). On the other hand, \(G_{n,k}-x \cong K_n\) and hence \({\rm gp}_{\rm o}(G_{n,k}-x) = n\). \(\square\)

3.3 Dual general position sets↩︎

In this subsection we first show that \({\rm gp}_{\rm d}(G-x)\) can be arbitrarily larger/smaller than \({\rm gp}_{\rm d}(G)\). After that we prove that if \(x\) is not a cut vertex and lies in some \({\rm gp}_{\rm d}\)-set of \(G\), then \({\rm gp}_{\rm d}(G)-1 \le {\rm gp}_{\rm d}(G-x)\). We conclude the subsection by demonstrating that for such a vertex \(x\), the value \({\rm gp}_{\rm d}(G-x)\) cannot be bounded from above by \({\rm gp}_{\rm d}(G)\).

Consider the fan graphs \(F_n\), \(n\geq 4\), with the vertex \(x\) of degree \(n\). By Theorem 2(iii), it is straightforward to check that every largest general position set of \(F_n\) is also a dual general position set. Hence \({\rm gp}(F_n) = {\rm gp}_{\rm d}(F_n)\). Moreover, it was proved in [19] that if \(n\ge 4\), then \({\rm gp}(F_n) = \left\lceil \frac{2(n+1)}{3}\right\rceil\). Hence, since \(F_n - x\cong P_n\), we have \[{\rm gp}_{\rm d}(F_n) = \left\lceil \frac{2(n+1)}{3}\right\rceil \quad {\rm and}\quad {\rm gp}_{\rm d}(F_n-x) = 2\,.\]

On the other hand, consider the family of graphs defined as follows. The wheel \(W_{n}\), \(n\ge 4\), is the graph of order \(n+1\) obtained from \(C_n\) by adding one more vertex and connecting it to all vertices of the cycle. The mushroom \(M_k\), \(k\ge 4\), is the graph obtained from the disjoint union of \(W_{k+4}\) and \(K_k\) by adding a matching between the vertices of \(K_k\) and \(k\) consecutive vertices of the \((k+4)\)-cycle of \(W_{k+4}\). See Fig. 2 for \(M_4\).

Let \(k\geq 4\), and set \[V(M_k) = \{w_1,\ldots,w_{k+4}, x, v_1,\ldots, v_k\}\,,\] where \(V(W_{k+4}) = \{w_1,\ldots,w_{k+4}, x\}\) with \(x\) being the center of \(W_{k+4}\), \(V(K_{k}) = \{v_1,\ldots, v_{k}\}\), and \(v_iw_i\in E(M_k)\) for \(i\in [k]\), see Fig. 2 again.

Let \(Y = V(K_k)\cup\{w_{k+2},w_{k+3}\}\). Then it follows from Theorem 1 that \(Y\) is a general position set of \(M_k\). Moreover, \(M_k - Y\) is convex, hence Theorem 2(iii) implies that \(Y\) is a dual general position set of \(M_k\). Thus \({\rm gp}_{\rm d}(M_k)\geq k+2\).

To prove that \({\rm gp}_{\rm d}(M_k)\leq k+2\), suppose on the contrary that there exists a dual general position set \(X\) of \(M_k\) with \(|X| > k+2\). We first claim that \(x\notin X\). Suppose that \(x\in X\). Then at least one of \(w_1\) and \(w_4\) must belong to \(X\), say \(w_1\in X\). Then \(w_4\notin X\). Since \(w_1\in X\), exactly one of \(w_2\) and \(w_{k+4}\) lies in \(X\). If \(w_{k+4}\in X\), then \(w_2\) and \(w_4\) are not \(X\)-positionable. And if \(w_{2}\in X\), then \(w_{k+4}\) and \(w_4\) are not \(X\)-positionable. We analogously get a contradiction in the case when \(w_{4}\in X\). We can conclude that \(x\notin X\). We next claim that \(w_i\notin X\) for each \(i\in [k]\). Suppose that \(w_i\in X\) for some \(i\in [k]\). Since \(x\notin X\), we get that \(v_i\in X\) because \(x,w_i,v_i\) is the unique shortest \(x,v_i\)-path. Further, exactly one of the neighbors of \(w_{i}\) on the \((k+4)\)-cycle of \(W_{k+4}\) lies in \(X\). But this is not possible, as \(X\) is a general position set.

From our assumption, we have \(|X\cap\{w_{k+1},w_{k+2},w_{k+3},w_{k+4}\}|\geq 3\). If \(w_{k+1}\in X\), then \(w_{k+2}\in X\) because \(w_k\notin X\). Otherwise, the vertices \(w_k\) and \(w_{k+2}\) are not \(X\)-positionable. Since \(w_{k+2}\) lies on the shortest \(w_{k+1},w_{k+3}\)-path, it follows that \(w_{k+3}\notin X\) and \(w_{k+4}\in X\). If \(w_{k+4}\in X\), then we must have \(w_1\in X\) which is not possible because we have proved that \(w_i\notin X\) for each \(i\in [k]\). This contradiction implies that \(w_{k+1}\notin X\). Similarly, we get that \(w_{k+4}\notin X\). Therefore, \(|X\cap \{w_{k+1},w_{k+2},w_{k+3},w_{k+4}\}|\leq 2\), which leads to \(|X|\leq k+2\), the final contradiction. We can conclude that \({\rm gp}_{\rm d}(M_k) = k+2\).

We now prove that \({\rm gp}_{\rm d}(M_k-x)=0\). Let \(X\) be an arbitrary dual general position set of \(M_k-x\). Then we first infer that \(w_i\notin X\) for each \(i\in [k]\). Indeed, if \(w_i\in X\) for some \(i\in [k]\), then exactly one of \(w_{i-1}, w_{i+1}\) must belong to \(X\), but this leads to a contradiction that \(X\) is a dual general position set. Similarly we get that none of \(w_{k+j}\), \(j\in [4]\), belong to \(X\). Finally, if some \(v_i\in X\), then we get that all \(v_i\), \(i\in [k]\) belong to \(X\), but then \(w_1\) and \(w_k\) are not \(X\)-positionable. We can conclude that \(X = \emptyset\). \(\square\)

Proposition 8 shows that \({\rm gp}_{\rm d}(G - x)\) can be arbitrarily smaller than \({\rm gp}_{\rm d}(G)\). Next, we show that \({\rm gp}_{\rm d}(G - x)\) can also be arbitrarily larger than \({\rm gp}_{\rm d}(G)\) by the following example. Let \(T_k\), \(k\ge 3\), be a graph obtained from the disjoint union of \(K_{1,2k}\) with the central vertex \(u\) and leaves \(v_1,\ldots, v_{2k}\), and an isolated vertex \(x\), by adding the edges \(xv_i\), \(i \in [k]\).

Since \(s(T_k) = k\), Lemma 1 gives \({\rm gp}_{\rm d}(T_k)\geq k\). To prove the reverse inequality, consider an arbitrary \({\rm gp}_{\rm d}\)-set \(X\) of \(T_k\). Suppose first that \(x\in X\). Then \(v_i, v_j\in X\), where \(i,j \in [k]\), is not possible since then \(v_i\) and \(v_j\) are not \(X\)-positionable. Analogously we see that also \(v_i, v_j\notin X\), where \(i,j \in [k]\), cannot happen. Since \(k\ge 3\), we can conclude that \(x\notin X\). By an analogous reason, \(u \notin X\). This in turn implies that \(v_i\notin X\) for each \(i\in [k]\). Hence \(|X|\leq k\), and then \({\rm gp}_{\rm d}(T_k) = k\).

Since \(s(T_k - x) = 2k\), Lemma 1 implies that \({\rm gp}_{\rm d}(T_k-x) = 2k\), and we are done. \(\square\)

We also have a result parallel to Theorem 5 for the dual general position number in the following.

Let \(X\) be a \({\rm gp}_{\rm d}\)-set of \(G\) such that \(x \in X\). Then \(|X| = {\rm gp}_{\rm d}(G)\) and by Theorem 2(ii), \(G-X\) is convex. By the proof of [16], the set \(X\setminus\{x\}\) is a general position set of \(G-x\). It suffices to show that \((G-x) -(X\setminus\{x\})\) is convex in \(G-x\). Suppose on the contrary that this is not the case. There are \(u,v \notin X\) such that a shortest \(u,v\)-path \(P\) containing a vertex \(w \in X\setminus \{x\}\). Since \(G-X\) is convex, \(d_G(u,v) < d_G(u,w)+d_G(w,v)\). Based on this, we can conclude the following: \[\begin{align} d_{G-x}(u,v) & = d_{G-x}(u,w)+d_{G-x}(w,v)\\ & \ge d_G(u,w)+d_G(w,v)\\ & > d_G(u,v)\,. \end{align}\] This in turn implies that \(x\) lies on the shortest \(u,v\)-path in \(G\) which contradicts with \(G-X\) being convex. We can conclude that \((G-x) -(X\setminus\{x\})\) is convex in \(G-x\). Using Theorem 2(iii) again, the set \(X\setminus\{x\}\) is a dual general position set of \(G-x\) and hence \({\rm gp}_{\rm d}(G-x) \ge |X\setminus \{x\}| = {\rm gp}_{\rm d}(G) -1\).

To prove the sharpness of the bound, consider a graph \(K_{1,n}\), \(n\geq 3\), and let \(x\) be an arbitrary leaf of it. Then \({\rm gp}_{\rm d}(K_{1,n})=n\) and \({\rm gp}_{\rm d}(K_{1,n}-x) =n-1\). \(\square\)

In Theorem 10 we have bounded \({\rm gp}_{\rm d}(G-x)\) from below by \({\rm gp}_{\rm d}(G)-1\) when \(x\) is not a cut vertex and lies in some \({\rm gp}_{\rm d}\)-set of \(G\). We next demonstrate that for such a vertex \(x\) the value \({\rm gp}_{\rm d}(G-x)\) cannot be bounded from above by \({\rm gp}_{\rm d}(G)\).

Consider the graph \(Y_k\), which is obtained from the complete graph \(K_{k+3}\) by adding two vertices \(x\) and \(y\), and connecting each of them them to the same \(k\) vertices of \(K_{k+3}\) as illustrated in Fig. 3.

Let \(\{v_1,\ldots,v_{k}, u,v,w\}\) be the set of vertices of the induced complete graph \(K_{k+3}\) in \(Y_k\) as indicated in Fig. 3. Then \(V(Y_k) = \{v_1,\ldots,v_{k}, u,v,w,x,y\}\) and \(\deg_{Y_k}(u) = \deg_{Y_k}(v) = \deg_{Y_k}(w) = k+2\). It is straightforward to check that \(\{x,y, u,v,w\}\) is a general position set of \(Y_k\). Hence \(\{x,y, u,v,w\}\) is also a dual general position set of \(Y_k\) by Theorem 2(iii). Therefore, \({\rm gp}_{\rm d}(Y_k)\geq 5\).

To prove \({\rm gp}_{\rm d}(Y_k)\leq 5\), consider an arbitrary \({\rm gp}_{\rm d}\)-set \(X\) of \(Y_k\). Suppose on the contrary that \(v_i\in X\) for some \(i\in [k]\). Then exactly one of the vertices \(x\) and \(y\) must be in \(X\). Otherwise, \(v_i\) would lie on a shortest \(x,y\)-path, which is a contradiction. Assume, without loss of generality, that \(x\in X\) and \(y\notin X\). We claim that there is no vertex from \(\{u,v,w\}\) contained in \(X\). If \(z\in \{u,v,w\}\cap X\), then \(v_i\) lies on a shortest \(x,z\)-path, contradicts with the fact that \(X\) is a \({\rm gp}_{\rm d}\)-set of \(Y_k\). If a vertex of \(\{u,v,w\}\) does not contain in \(X\), say \(u\), then \(v_i\) lies on a shortest \(y,u\)-path, which implies that \(y\) and \(u\) are not \(X\)-positionable. This contradiction yields \(v_i\notin X\) for each \(i\in [k]\). Therefore, \(|X|\leq 5\), and we conclude that \({\rm gp}_{\rm d}(Y_k) = 5\).

If \(x\) is removed from \(Y_k\), by Theorem 1, the set \(\{v_1,\ldots,v_k,u,v,w\}\) is a largest general position set of \(Y_k - x\). Using Theorem 2(iii), we get that \(\{v_1,\ldots,v_k,u,v,w\}\) is also a dual general position set of \(Y_k - x\). Note that \({\rm gp}_{\rm d}(Y_k-x)\leq {\rm gp}(Y_k-x) = k+3\). We can conclude that \({\rm gp}_{\rm d}(Y_k-x) = k+3\). \(\square\)

4 Edge removal↩︎

Impact of removing an edge on the general position number of a graph was investigated in [16]. In this section, we complement this by examining the effect of edge removal on the other three general position invariants.

We begin with the total general position number, for which the following notation is needed. If \(G\) is a graph and \(e=uv\in E(G)\), then let \(S(G)_{e}\) denote the set of simplicial vertices in \(G\) which are adjacent to both \(u\) and \(v\).

Let \(e = uv\). If \(x\) is a simplicial vertex which is adjacent to at most one of \(u\) and \(v\), then \(x\) remains simplicial in \(G-e\). Thus \({\rm gp}_{\rm t}(G-e) = s(G-e) \ge s(G) - |S(G)_e| = {\rm gp}_{\rm t}(G) - |S(G)_e|\). If \(x\ne u,v\) is a simplicial vertex of \(G-e\), it remains simplicial in \(G\). Hence \({\rm gp}_{\rm t}(G) \ge {\rm gp}_{\rm t}(G-e) - 2\).

For the sharpness, note first that \(s(K_n) = n\) and \(s(K_n-e) = 2\), hence the lower bound is sharp. For the upper bound, let \(X_n\), \(n\ge 2\), be the graph obtained from the disjoint union of two copies of \(K_n\), say \(K\) and \(K'\) and a vertex \(x\), by adding an edge \(e = uv\) between \(K\) and \(K'\), and joining \(x\) to a vertex \(u'\) in \(K\) and a vertex \(v'\) in \(K'\), where \(\{u,v\} \cap \{u',v'\} = \emptyset\). Then we infer that \({\rm gp}_{\rm t}(X_n)=2(n-2)\) and \({\rm gp}_{\rm t}(X_n-e)=2(n-1)\), that \({\rm gp}_{\rm o}(G)/2\le {\rm gp}_{\rm o}(G-e)\leq\;2{\rm gp}_{\rm o}(G)\), and that \(\square\)

For the outer general position number, the following holds.

Let \(e=uv\) and let \(X\) be a \({\rm gp}_{\rm o}\)-set of \(G\). Then consider the sets of vertices \[\begin{align} X_{uv} & = \{w\in X:\;d_G(u,w) < d_G(v,w) \}, \\ X_{vu} & = \{w\in X:\;d_G(v,w) < d_G(u,w) \}, \\ _vX_u & = \{w\in X:\;d_G(u,w) = d_G(v,w) \}\,. \end{align}\] Clearly, \(X = X_{uv} \cup X_{vu} \cup\, _vX_u\). Let \[X_u = X_{uv} \cup\, _vX_u\quad {\rm and}\quad X_v = X_{vu} \cup\, _vX_u\,.\] Then we recall from the proof of [16] that \(X_u\) and \(X_v\) are general position sets of \(G-e\). Moreover, by a parallel argument we prove that \(X_u\) and \(X_v\) remain to be MMD in \(G-e\) provided they were MMD in \(G\). Since \(|X|/2 \le \max\{ |X_u|, |X_v|\}\), Theorem 2(ii) yields the lower bound. The argument for the upper bounds proceeds along parallel lines.

To demonstrate the sharpness of the lower bound, consider first graphs \(Y'_n\), \(n\ge 3\), constructed as follows. First, take two disjoint copies of \(K_n\), say \(K\) and \(K'\) and add an edge between them, say \(e=uv\), where \(u\in K\) and \(v\in K'\). Second, add two new vertices \(u'\) and \(v'\), the edge \(u'v'\), all the edges between \(u'\) and \(V(K)\setminus \{u\}\), and all the edges between \(v'\) and \(V(K')\setminus \{v\}\), see Fig. 4.

We can observe that \({\rm gp}_{\rm o}(Y'_n) = 2(n-1)\) and that \({\rm gp}_{\rm o}(Y'_n-e) = n-1\). This demonstrates the sharpness of the lower bound.

For the sharpness of the upper bound, let \(Z_n\), \(n\ge 2\), be the graph obtained from two disjoint copies of \(K_{2,n}\) by adding an edge \(e=uv\) between them, where \(u\) and \(v\) are vertices of degree \(n\) in different copies of \(K_{2,n}\). Then \({\rm gp}_{\rm o}(Z_n) = n\) and \({\rm gp}_{\rm o}(Z_n-e) = 2n\). \(\square\)

To conclude the paper, we consider the dual general position number under edge removal for which we have the following.

Consider the graphs \(H_n\), \(n\geq 1\), obtained from \(n\) disjoint triangles and one \(C_6\), by selecting an edge in each of these \(n+1\) graphs and identifying them into a single edge. See Fig. 5 from which the vertex labelling of \(H_n\) should be clear.

Let \(X = \{w_1,\dots, w_n\}\). It is straightforward to check that \(X\) is a general position set of \(H_n\). Since there is a unique shortest path between \(x\) and \(y\) that does not contain any vertex from \(X\), it follows from Theorem 2 (iii) that \(G-X\) is convex, thus proving that \(X\) is the largest dual general position set of \(H_n\). Hence \({\rm gp}_{\rm d}(H_n) \ge n\). On the other hand, removing the edge \(e = xy\), every edge of \(H_n-e\) is the middle edge of some isometric path \(P_4\). In view of [14] we have \({\rm gp}_{\rm d}(H_n-e) = 0\). \(\square\)

Acknowledgements↩︎

This work was supported by the Slovenian Research and Innovation Agency (ARIS) under the grants P1-0297, N1-0355, and N1-0285.

Data Availability Statement↩︎

Data sharing is not applicable to this article as no new data were created or analyzed in this study.

Conflict of Interest Statement↩︎

Sandi Klavžar is an Associate Editor of the Discrete Applied Mathematics journal and was not involved in the review and decision-making process of this article. In addition, the authors declare no other conflict of interest.

References↩︎