$\mathcal{I}_{f}^{p_{f}}$. Consequently we have that as $c_{f}>p_{f}$, for any
arbitrary stable matching under $\mathcal{I}$,
$\mu(f)=\mu^{*}_{c_{f}})(f)=\mu^{*}(f)$.

∎

Analogous arguments to those in this proof lead to the following corollary.

######  Corollary 2.

Given an instance $\mathcal{I}=\langle F,W,C,\succ\rangle$ and a firm $f\in
F$, for any $b_{1}<p_{f}$ and any $b_{2}>b_{1}$, we have that for an arbitrary
stable matching $\mu_{1}$ of $\mathcal{I}_{f}^{b_{1}}$ and an arbitrary stable
matching $\mu_{2}$ of $\mathcal{I}_{f}^{b_{2}}$, $|\mu_{1}(f)|<|\mu_{2}(f)|$.

The above corollary provides us the following remark:

######  Remark 1.

Given an instance $\mathcal{I}=\langle F,W,C,\succ\rangle$ and a firm $f\in
F$, the size of $f$’s matched set under a stable matching in
$\mathcal{I}_{f}^{b}$ will increase as $b$ is increased from $0$ to $p_{f}$
and then be fixed at $p_{f}$ for all $b>p_{f}$.

We now show that Lemma 1 can be used to prove Theorem 3.

See 3

###### Proof.

Let $M$ be a matching algorithm that takes as input an instance of the many-
to-one matching problem and always returns a stable matching. We shall now
show that for any $f$ such that its capacity under $\mathcal{I}$ $c_{f}>p_{f}$
then any preference manipulation cannot benefit $f$ and in fact will match it
to the same set of workers as the true preferences.

Let $\succ_{f}$ be $f$’s true preferences under $\mathcal{I}$ and
$\succ^{\prime}$ be an arbitrary preference relation that is a permutation of
$\succ_{f}$ i.e. for any $w\in W$, $w\succ^{\prime}\emptyset$ if and only if
$w\succ_{f}\emptyset$.

Recall the definition of $W_{f}$ from the proof of Lemma 1. $W_{f}$ is the set
of workers who propose to $f$ during the WPDA under $\mathcal{I}_{f}^{p_{f}}$.
Observe that $W_{f}$ is the set of agents that propose to $f$ during the WPDA
under $\langle F,W,C,(\succ^{\prime},\succ_{-f})\rangle$, that is when $f$
reports its preference as $\succ^{\prime}$. Thus, the set of agents matched to
$f$ under the WPDA under the true or misreported preferences is the same.
Further, as $f$ is unsaturated (from Lemma 1), the set of workers matched to
$f$ under the matching returned by $M$ on $\langle
F,W,C,(\succ^{\prime},\succ_{-f})\rangle$, must be the same as the set of
workers matched to $f$ under the worker optimal stable matching in the
misreported instance. This set is the same as the workers matched to $f$ in
the true instance. That is, if $\mathcal{I}^{\prime}=\langle
F,W,C,(\succ^{\prime},\succ_{-f})\rangle$

$M_{f}(I^{\prime})={\sf WPDA}(I^{\prime})={\sf WPDA}(I)=M_{f}(I)$

∎

Aziz et al. [2015] had shown that in many-to-one matchings, a firm can only
beneficially preference manipulate the WPDA if it receives more proposals than
its capacity. A firm receives more proposals than its capacity, only if its
capacity is below the peak. As a result, their result combined with arguments
analogous to those in the proof of Lemma 1 lead to the following corollary.

######  Corollary 3.

Given an instance $\mathcal{I}=\langle F,W,C,\succ\rangle$ and a firm $f\in
F$, with $c_{f}=p_{f}$. We have that preference manipulation cannot benefit
$f$ under the WPDA.

#### Comparison under FPDA

We now do an analogous comparison for the FPDA.

##### Below peak

We first show an instance where Pref is the best manipulation available to a
firm with capacity below peak.

######  Example 7.

Consider an instance $\mathcal{I}$ with two firms $f_{1},f_{2}$ and six
workers $w_{1},\dots,w_{6}$. The firms have capacities $c_{1}=2$ and
$c_{2}=3$, and have lexicographic preferences as follows:

$\textstyle w_{1},\,w_{2},\,w_{3}$ $\textstyle:f_{2}\succ f_{1}\succ\emptyset$
$\textstyle w_{4},\,w_{5},\,w_{6}$ $\textstyle:f_{1}\succ f_{2}\succ\emptyset$
$\textstyle f_{1}$ $\textstyle:w_{1}\succ w_{4}\succ w_{5}\succ w_{6}\succ
w_{2}\succ w_{3}$ $\textstyle f_{2}$ $\textstyle:w_{4}\succ w_{5}\succ
w_{6}\succ w_{1}\succ w_{2}\succ w_{3}$

The unique stable matching in this instance is

$\mu_{1}=\\{(w_{4},f_{1}),(w_{5},f_{1}),(w_{1},f_{2}),(w_{2},f_{2}),(w_{6},f_{2})\\}.$

Increasing the capacity of $f_{1}$ to $c_{1}=3$ would result in the instance
$\mathcal{I}^{\prime}$ which has the following unique stable matching

$\mu_{2}=\\{((w_{4},f_{1}),(w_{5},f_{1}),(w_{6},f_{1}),(w_{1},f_{2}),(w_{2},f_{2})\\}.$

It is easy to check that the peak for firm $f_{1}$ is $3$. Thus, in the
original instance $\mathcal{I}$, the firm $f_{1}$ is below its peak.

Now, starting from the original instance $\mathcal{I}$, if $f_{1}$ uses Delete
by decreasing its capacity to $c_{1}=1$, then it gets matched with the
singleton set $\\{w_{1}\\}$ under FPDA. On the other hand, if $f_{1}$ uses Add
in the instance $\mathcal{I}$ by changing its capacity to $c_{1}\geq 3$, then
it gets matched with the set $\\{w_{4},w_{5},w_{6}\\}$. Under lexicographic
preferences, firm $f_{1}$ prefers the outcome under Delete than that under
Add.

By using Pref, the firm can do even better. Indeed, if $f_{1}$ misreports its
preferences in the instance $\mathcal{I}$ to be

$f_{1}:w_{1}\succ w_{2}\succ w_{4}\succ w_{5}\succ w_{6}\succ w_{3},$

then under the FPDA algorithm, it is matched with the set $\\{w_{1},w_{2}\\}$,
which is more preferable for $f_{1}$ (according to its true preferences) than
the outcome under Delete.∎

We now show an example where Delete is best manipulation available.

######  Example 8.

Consider the following example with three firms $f_{1}$, $f_{2}$ and $f_{3}$
and four workers $w_{1},\cdots,w_{4}$. The firms have lexicographic
preferences with capacities being $c_{1}=c_{3}=2$ and $c_{2}=1$. The
preference relations are as follows:

$\textstyle w_{1}$ $\textstyle:f_{3}\succ f_{2}\succ f_{1}\succ\emptyset$
$\textstyle w_{2},\,w_{3},\,w_{4}$ $\textstyle:f_{1}\succ f_{2}\succ
f_{3}\succ\emptyset$ $\textstyle f_{1}$ $\textstyle:w_{1}\succ w_{2}\succ
w_{3}\succ w_{4}$ $\textstyle f_{2}$ $\textstyle:w_{2}\succ w_{1}\succ
w_{3}\succ w_{4}$ $\textstyle f_{3}$ $\textstyle:w_{3}\succ w_{4}\succ
w_{1}\succ w_{2}$

The firm optimal stable matching here is

$\mu_{1}=\\{(w_{2},f_{1}),(w_{3},f_{1}),(w_{4},f_{2}),(w_{1},f_{3})\\}$

In this case, however $f_{1}$ reports its preferences, with a capacity of two,
it will always issue two proposals and be matched to one of the following sets
$\\{w_{2},w_{3}\\}$, $\\{w_{2},w_{4}\\}$ or $\\{w_{3},w_{4}\\}$. However, if
$f_{1}$ were to report its capacity as one, the FPDA would result in the
following matching:

$\mu_{2}=\\{(w_{1},f_{1}),(w_{2},f_{2}),(w_{3},f_{3}),(w_{4},f_{4})\\}$

Clearly, $f_{1}$ prefers $\mu_{2}$ to $\mu_{1}$ and any matching resulting
from misreporting its preference. ∎

##### At peak

For the firm-proposing algorithm, preference manipulation can prove to be
useful when the firm’s capacity is at peak. We now show a straightforward
example for lexicographic preferences, that can extended easily to the
strongly monotone setting.

######  Example 9.

Consider the following instance with two firms $f_{1}$ and $f_{2}$ with
lexicographic preferences and four workers $w_{1},\cdots,w_{4}$. The
preference relations are as follows:

$\textstyle w_{1},\,w_{4}$ $\textstyle:f_{2}\succ f_{1}\succ\emptyset$
$\textstyle w_{2},\,w_{3}$ $\textstyle:f_{1}\succ f_{2}\succ\emptyset$
$\textstyle f_{1}$ $\textstyle:w_{1}\succ w_{2}\succ w_{3}\succ w_{4}$
$\textstyle f_{2}$ $\textstyle:w_{2}\succ w_{3}\succ w_{1}\succ w_{4}$

Here the true capacity of the firms is $c_{1}=c_{2}=2$. For this instance,
$f_{1}$ is at its peak capacity. The unique stable matching for this instance
is:

$\mu_{1}=\\{(w_{2},f_{1}),(w_{3},f_{1}),(w_{1},f_{2}),(w_{4},f_{2})\\}$

Increasing the capacity of $f_{1}$ will also result in the same stable
matching $\mu_{1}$. However, if $f_{1}$ were to misreport its preference as
$\\{w_{1},w_{4}\\}\succ\\{w_{1},w_{2}\\}\succ\\{w_{1},w_{3}\\}\succ\\{w_{2},w_{4}\\}\succ\\{w_{2},w_{3}\\}\succ\\{w_{2},w_{3}\\}\succ\\{w_{1}\\}\succ\\{w_{4}\\}\succ\\{w_{2}\\}\succ\\{w_{3}\\}$,
the resulting firm optimal stable matching will be:

$\mu_{2}=\\{(w_{1},f_{1}),(w_{4},f_{1}),(w_{2},f_{2}),(w_{3},f_{2})\\}$

Clearly it is better for $f_{1}$ to misreport its preference.∎

The example in Sönmez [1997] shows outperformance of Delete at and above peak
under the FPDA.

##### Above peak

When the capacity of the firm is above its peak, Pref again turns out to be
unhelpful under FPDA. This is proven in Theorem 3. The example to show Delete
outperforming Pref can be found in Sönmez [1997].

###  D.2 Manipulation via Add

We have seen above various instances where Delete or Pref are the beneficial
manipulation actions. We find that Add is only useful when the firm is below
peak. When a firm is at or above peak, increasing its capacity is not
beneficial to it, under any stable matching algorithm. This is a
straightforward consequence of Lemma 1.

######  Corollary 4.

Given an instance $\mathcal{I}=\langle F,W,C,\succ\rangle$ and a firm $f\in
F$, if $c_{f}\geq p_{f}$ then increasing the capacity of $f$ will not improve
the set of workers matched to $f$ under any stable matching algorithm.

As a result, Add can only be helpful when the firm’s capacity is below peak.
We show a simple example where this is the case.

######  Example 10.

Consider the following instance with two firms $f_{1}$ and $f_{2}$ and five
workers $w_{1},\cdots,w_{5}$. All the workers have the preference relation,
both firms have the same responsive preference relation over single workers.
In this case, whether the preferences over the larger sets of workers are
strongly monotone or lexicographic, we find that the best manipulation action
available to $f_{1}$ stays the same. As we assume that the workers have the
same preference relation, the instance will always have a unique stable
matching, so the best manipulation action is the same for both the firm-
optimal and worker-optimal algorithms.

$\textstyle w_{1}\,-\,w_{5}$ $\textstyle:f_{1}\succ f_{2}\succ\emptyset$
$\textstyle f_{1},\,f_{2}$ $\textstyle:w_{1}\succ w_{2}\succ w_{3}\succ w_{4}\
\succ w_{5}$

In this case, as $f_{1}$ is the most preferred firm for all the workers, a
stable matching will always match it to its favourite $c_{1}$ agents. In act,
irrespective of $f_{2}$’s capacity, $f_{1}$’s peak is $5$. Initially, each
firm has capacity equal to two, i.e., $c_{1}=c_{2}=2$. In this case, the firm-
optimal stable matching is

$\mu_{1}=\\{(w_{1},f_{1}),(w_{2},f_{1}),(w_{3},f_{2}),(w_{4},f_{2})\\}.$

For $f_{1}$, preference manipulation cannot help $f_{1}$ get a better pair of
workers to match with, as $f_{1}$ is already matched to their favourite pair
of workers. Also, decreasing capacity will only make it worse. However,
increasing $f_{1}$’s capacity, will improve $f_{1}$’s matched set. ∎

###  D.3 Strongly Monotone Preferences

Strongly monotone preferences are a type of responsive preferences where
agents always prefer larger sets over smaller sets. They were first defined by
Konishi and Ünver [2006]. Such preferences make manipulation harder. Konishi
and Ünver [2006] and Kojima [2007] show that under the WPDA, firms cannot
benefit by Delete when the preferences are strongly monotone. Clearly, this
contrasts with our results for the general responsive preference class. Hence,
we specifically study the class of Strongly Monotone (responsive) preferences
to see which manipulation actions can be useful. We recall the manipulation
trends for responsive preferences and contrast them with those for strongly
monotone preferences in Figure 2.

##### Manipulation via Capacities

We find that when Lemma 1 is combined with the fact that under strongly
monotone preferences, larger sets are always preferred, we get the following
observation.

######  Observation 1.

Given an instance $\mathcal{I}=\langle F,W,C,\succ\rangle$ and a firm $f\in
F$, with strongly monotone preferences. When $f$ is below peak, that is, when
$c_{f}<p_{f}$, the best manipulation strategy for $f$ is to increase its
capacity to $p_{f}$. That is, for any stable matching algorithm, $f$ will
(weakly) prefer the matching returned by the algorithm when it misreports its
capacity as $p_{f}$ over the matching returned by the algorithm on any other
misreport by $f$.

######  Proposition 7.

Given an instance $\mathcal{I}=\langle F,W,C,\succ\rangle$ and a firm $f\in
F$. If $f$ has strongly monotone preferences, when $c_{f}\leq p_{f}$, $f$
cannot benefit from reducing its capacity under any stable matching algorithm.
For the WPDA, $f$ can never benefit from Delete.

###### Proof.

Recall that for a firm $f$ with a strongly monotone preference relation
$\succ_{f}$, for any subsets of workers acceptable to $f$ $W_{1}$ and $W_{2}$,
whenever $|W_{1}|>|W_{2}|$ then $W_{1}\succ_{f}W_{2}$.

Fix an instance $\mathcal{I}$ and firm $f$ such that $c_{f}\leq p_{f}$. Let
$M$ be any stable matching algorithm. Thus, the $f$ must be saturated under
the For any $b<c_{f}<p_{f}$, the size of the set of workers matched to $f$
under $M(I_{f}^{b})$ will be $b$ which is less than the size of the set of
workers matched to $f$ under $M(I)$. As $f$’s preference is strongly monotone,
$f$ prefers the larger set and cannot benefit by reducing its capacity.

Now consider an arbitrary instance $\mathcal{I}$ and firm $f$ with a strongly
monotone preference. We know that if $c_{f}\leq p_{f}$, $f$ cannot benefit by
reducing its capacity for any stable matching algorithm, in particular with
the WPDA. If $c_{f}>p_{f}$, from Lemma 1, we have that the set of agents
matched to $f$ under he worker optimal stable matching of $\mathcal{I}$ is the
same as the set of agents matched to $f$ under the worker optimal stable
matching of $\mathcal{I}_{f}^{p_{f}}$. Thus, for the WPDA, if $f$ were to
reduce its capacity to $b$ s.t. $c_{f}>b\geq p_{f}$, it would continue to be
matched to the same set of agents. If the choice of reduced capacity were
$b<p_{f}$ then the size of the set of agents matched to $f$ would be smaller,
which it does not prefer.

Consequently, a firm with strongly monotone preferences can never benefit by
reducing its capacity when the stable matching algorithm is the WPDA. ∎

A consequence of Proposition 7 and the fact that Pref is not useful under the
WPDA at and above peak, is the following.

######  Remark 2.

For a firm with strongly monotone preference and capacity at or above peak,
there is no beneficial manipulation via preferences or capacities under the
WPDA.

WPDA:

PrefDelAdd (a) Below peak

PrefDelAdd (b) At peak

PrefDelAdd (c) Above peak

FPDA:

PrefDelAdd (d) Below peak

PrefDelAdd (e) At peak

PrefDelAdd (f) Above peak

Figure 1:  Manipulation trends for general responsive preferences for the WPDA
(top) and FPDA (bottom) algorithm under the below peak/at peak/above peak
regimes. An arrow from action $X$ to action $Y$ denotes the existence of an
instance where $X$ is strictly more beneficial for the firm than $Y$. Each
missing arrow from $X$ to $Y$ denotes that there is (provably) no instance
where $X$ is more beneficial than $Y$. (repeated from page 1)

WPDA:

PrefDelAdd (a) Below peak

PrefDelAdd (b) At peak

PrefDelAdd (c) Above peak

FPDA:

PrefDelAdd (d) Below peak

PrefDelAdd (e) At peak

PrefDelAdd (f) Above peak

Figure 2:  Manipulation trends for Strongly Monotone preferences. An arrow
from action $X$ to action $Y$ denotes the existence of an instance where $X$
is strictly more beneficial for the firm than $Y$. Each missing arrow from $X$
to $Y$ denotes that there is (provably) no instance where $X$ is more
beneficial than $Y$.

#####  Pref under strongly monotone preferences

We now study when Pref can be useful to agents with strongly monotone
preferences. Above peak, we have seen in Theorem 3 that preference
manipulation cannot improve the stable set of a firm. For strongly monotone
preferences, when the capacity of a firm is below peak, clearly, increasing
the capacity of the firm is the best manipulation action. However, Pref can
still outperform Delete. Examples similar to Example 4 and Example 7 can be
constructed for the strongly monotone preference setting.

At peak, under the WPDA, we have seen that preference manipulation in
Corollary 3 that preference manipulation is not useful. We now show an example
where preference manipulation can be useful under strongly monotone
preferences at peak under the FPDA.

######  Example 11.

Consider the following instance with two firms $f_{1}$ and $f_{2}$ and four
workers $w_{1},\cdots,w_{4}$. The preference relations are as follows:

$\textstyle w_{1},\,w_{4}$ $\textstyle:f_{2}\succ f_{1}\succ\emptyset$
$\textstyle w_{2},\,w_{3}$ $\textstyle:f_{1}\succ f_{2}\succ\emptyset$
$\textstyle f_{1}$
$\textstyle:\\{w_{1},w_{2}\\}\succ\\{w_{1},w_{3}\\}\succ\\{w_{1},w_{4}\\}\succ\\{w_{2},w_{3}\\}\succ$
$\textstyle\hskip
14.45377pt\\{w_{2},w_{4}\\}\succ\\{w_{3},w_{4}\\}\succ\\{w_{1}\\}\succ\\{w_{2}\\}\succ\\{w_{3}\\}\succ\\{w_{4}\\}$
$\textstyle f_{2}$
$\textstyle:\\{w_{2},w_{3}\\}\succ\\{w_{1},w_{2}\\}\succ\\{w_{2},w_{4}\\}\succ\\{w_{1},w_{3}\\}\succ$
$\textstyle\hskip
14.45377pt\\{w_{3},w_{4}\\}\succ\\{w_{1},w_{4}\\}\succ\\{w_{2}\\}\succ\\{w_{3}\\}\succ\\{w_{1}\\}\succ\\{w_{4}\\}$

Here the true capacity of the firms is $c_{1}=c_{2}=2$. For this instance,
$f_{1}$ is at its peak capacity. The unique stable matching for this instance
is:

$\mu_{1}=\\{(w_{2},f_{1}),(w_{3},f_{1}),(w_{1},f_{2}),(w_{4},f_{2})\\}$

Increasing the capacity of $f_{1}$ will also result in the same stable
matching $\mu_{1}$. However, if $f_{1}$ were to misreport its preference as
$\\{w_{1},w_{4}\\}\succ\\{w_{1},w_{2}\\}\succ\\{w_{1},w_{3}\\}\succ\\{w_{2},w_{4}\\}\succ\\{w_{2},w_{3}\\}\succ\\{w_{2},w_{3}\\}\succ\\{w_{1}\\}\succ\\{w_{4}\\}\succ\\{w_{2}\\}\succ\\{w_{3}\\}$,
the resulting firm optimal stable matching will be:

$\mu_{2}=\\{(w_{1},f_{1}),(w_{4},f_{1}),(w_{2},f_{2}),(w_{3},f_{2})\\}$

Clearly it is better for $f_{1}$ to misreport its preference.


# The general position number under vertex and edge removal

Pakanun Dokyeesuna Email<EMAIL_ADDRESS>Sandi Klavžar a,b,c Email:
<EMAIL_ADDRESS>Jing Tian d,b Email<EMAIL_ADDRESS>
###### Abstract

Let ${\rm gp}(G)$ be the general position number of a graph $G$. 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\leq{\rm gp}(G-x)$. Constructions are given which show that ${\rm
gp}(G-x)$ can be much larger than ${\rm gp}(G)$ also when $G-x$ is connected.
For diameter $2$ graphs it is proved that ${\rm gp}(G-x)\leq{\rm gp}(G)$, and
that ${\rm gp}(G-x)\geq{\rm gp}(G)-1$ when the diameter of $G-x$ remains $2$.
It is demonstrated that ${\rm gp}(G)/2\leq{\rm gp}(G-e)\leq 2{\rm gp}(G)$
holds for any edge $e$ of a graph $G$. For diameter $2$ graphs these results
sharpens to ${\rm gp}(G)-1\leq{\rm gp}(G-e)\leq\ {\rm gp}(G)+1$. All these
bounds are proved to be sharp.

a Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

b Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

c Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

d School of Science, Zhejiang University of Science and Technology, Hangzhou,
Zhejiang 310023, PR China

Keywords: general position set; vertex-deleted subgraph; edge-deleted
subgraph; graph diameter

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

##  1 Introduction

Local operations are valuable in graph theory for understanding and analyzing
the properties of graphs and refer to operations that affect only a small part
of a graph, rather than the whole structure. These operations include
vertex/edge removal/addition and edge subdivision or contraction, and often
lead to respective criticality concepts, cf. [2, 4, 7, 9, 21, 32].

The general position problem was introduced to graph theory in [5, 17] and
proved to be NP-hard in [17]. In [3], the structure of general position sets
was clarified. Afterwards, the problem of determining the general position
number of a graph received a wide attention, cf. [6, 23, 25, 28, 31]. This is
in particular the case for graph products. The general position number of the
Cartesian product of paths [13], of paths and cycles [16], and of two trees
[30] were determined, while in [15] the general position number of strong
product graphs was investigated. The concept has been modified and/or
generalized into several directions. Let us point here to $d$-position sets
[12], Steiner general position problem [11], edge general position problem
[14, 19, 27], monophonic general position problem [26], and general position
polynomials [8].

In this paper, we focus on how much the general position number of a graph can
be affected by removing a vertex or by removing an edge. In the next section
we give definitions and recall known results needed. In Section 3, we prove
that ${\rm gp}(G-x)\leq 2{\rm gp}(G)$ holds for any vertex $x$ of a graph $G$.
Then we demonstrate that ${\rm gp}(G-x)$ cannot be bounded from below by a
function of ${\rm gp}(G)$. On the other hand, if $x$ lies in some ${\rm
gp}$-set of $G$, then we prove that ${\rm gp}(G)-1\leq{\rm gp}(G-x)$. In
Section 4, we give two constructions which show that ${\rm gp}(G-x)$ can be
much larger than ${\rm gp}(G)$ also when $G-x$ is connected. In Section 5, we
focus on the vertex removing operation in diameter $2$ graphs. We show that if
${\rm diam}(G)=2$, then ${\rm gp}(G-x)\leq{\rm gp}(G)$ and prove that ${\rm
gp}(G)-1\leq{\rm gp}(G-x)\leq{\rm gp}(G)$ when the diameter of $G-x$ remains
$2$. In Section 6, we prove that ${\rm gp}(G)/2\leq{\rm gp}(G-e)\leq 2{\rm
gp}(G)$ holds for any edge $e$ of a graph $G$. For diameter $2$ graphs $G$ we
sharpen the bound by proving that ${\rm gp}(G)-1\leq{\rm gp}(G-e)\leq\ {\rm
gp}(G)+1$. All the above bounds are along the way shown to be sharp.

##  2 Preliminaries

Unless stated otherwise, the graphs $G=(V(G),E(G))$ considered in this paper
are simple and connected. For a positive integer $k$, we use $[k]$ to
represent the set $\\{1,\ldots,k\\}$. The degree of a vertex $u$ is the number
of vertices adjacent to $u$ in $G$. Vertices of degree one are called leaves.
The number of leaves of $G$ is denoted by $\ell(G)$. If $S\subseteq V(G)$, the
subgraph of $G$ induced by $S$ is denoted by $G[S]$. In particular, $G-v$
denotes $G[V(G)\setminus\\{v\\}]$. A vertex subset $S$ is an independent set
of $G$ if $G[S]$ is an edgeless graph. The independence number of $G$, denoted
by $\alpha(G)$, is the maximum cardinality of an independent set in $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. A shortest path of $G$ also is called a
geodesic of $G$. The diameter of $G$ is the maximum distance between pairs of
vertices of $G$ and is denoted by ${\rm diam}(G)$. A subgraph $H$ of $G$ is
isometric if for each pair of vertices $u,v\in V(H)$ we have
$d_{H}(u,v)=d_{G}(u,v)$. The interval between vertices $u$ and $v$ is

$I_{G}[u,v]=\\{w:\ d_{G}(u,v)=d_{G}(u,w)+d_{G}(w,v)\\}\,.$

A set $X\subseteq V(G)$ is a general position set of $G$ if for each pair
$u,v\in X$ and any shortest $u,v$-path $P$ we have $V(P)\cap X=\\{u,v\\}$. The
cardinality of a largest general position set of $G$ is the general position
number of $G$ denoted by ${\rm gp}(G)$ and refereed to as the gp-number of
$G$. A general position set $X$ of cardinality ${\rm gp}(G)$ is refereed to as
a gp-set of $G$. For a vertex $u\in V(G)$, a set $X\subseteq V(G)$ is
$u$-colinear if $X$ is a general position set such that $u\notin X$ and
$y\notin I_{G}[x,u]$ for any $x,y\in X$.

Subgraphs $H_{1},\ldots,H_{k}$ of a graph $G$ form an isometric cover of $G$
if each $H_{i},\,i\in[k]$, is isometric in $G$, and
$\bigcup_{i=1}^{k}V(H_{i})=V(G)$.

###### Theorem 2.1

[17, Theorem 3.1] If $\\{H_{1},$…$,H_{k}\\}$ is an isometric cover of $G$,
then

${\rm gp}(G)\leq\sum_{i=1}^{k}{\rm gp}(H_{i})\,.$

The _isometric-path number_ of a graph $G$, denoted by ${\rm ip}(G)$, is the
minimum number of isometric paths required to cover the vertices of $G$.

###### Proposition 2.2

[17, Corollary 3.2] If $G$ is a graph, then ${\rm gp}(G)\leq 2{\rm ip}(G)$.

The following result will be used several times, either implicitly or
explicitly.

###### Proposition 2.3

[17, Corollary 3.7] If $T$ is a tree, then ${\rm gp}(T)=\ell(T)$.

The fan graph $F_{n}$, $n\geq 3$, is obtained by taking the join of the path
graph $P_{n}$ and the graph $P_{1}$. Equivalently, a fan graph is obtained
from a wheel graph by removing an edge of it between two degree $3$ vertices,
cf. [24].

###### Proposition 2.4

[29, Corollary 2.9] If $n\geq 4$, then ${\rm
gp}(F_{n})=\lceil\frac{2n}{3}\rceil$.

The final known result we recall describes general position sets in an
arbitrary graph. To state it, some more definitions are required. If ${\cal
P}=\\{S_{1},\ldots,S_{t}\\}$ a partition of $S\subseteq V(G)$, then ${\cal P}$
is _distance-constant_ if for any $i,j\in[t]$, $i\neq j$, there exists a
constant $p_{ij}$, such that $d_{G}(x,y)=p_{ij}$ for every $x\in S_{i}$, $y\in
S_{j}$. If so, we set $d_{G}(S_{i},S_{j})=p_{ij}$. A distance-constant
partition ${\cal P}$ is in-transitive if $p_{ik}\neq p_{ij}+p_{jk}$ holds for
$i,j,k\in[t]$.

###### Theorem 2.5

[3, Theorem 3.1] Let $G$ be a graph. Then $S\subseteq V(G)$ is a general
position set if and only if the components of $G[S]$ are complete subgraphs,
the vertices of which form an in-transitive, distance-constant partition of
$S$.

##  3 General bounds

In this section we prove that ${\rm gp}(G-x)\leq 2{\rm gp}(G)$ holds for any
vertex $x$ of a graph $G$. Then we demonstrate that ${\rm gp}(G-x)$ cannot be
bounded from below by a function of ${\rm gp}(G)$. On the other hand, if $x$
lies in some gp-set, then ${\rm gp}(G)-1\leq{\rm gp}(G-x)$.

###### Theorem 3.1

If $x$ is a vertex of a graph $G$, then ${\rm gp}(G-x)\leq 2{\rm gp}(G)$.
Moreover, the bound is sharp.

Proof. Let $R$ be an arbitrary ${\rm gp}$-set of $G-x$. Then clearly $x\not\in
R$. We partition $R$ into two sets $R_{1}$ and $R_{2}$ as follows. For every
$u\in R$, we put each vertex from $(I_{G}[u,x]\setminus\\{u\\})\cap R$ into
$R_{2}$. This defines $R_{2}$, and then $R_{1}=R\setminus R_{2}$. By the
definition of the sets $R_{1}$ and $R_{2}$, the set $R_{1}$ is an $x$-colinear
set of $G$. We next claim that $R_{2}$ is also an $x$-colinear set of $G$.

Consider two vertices $u,u^{\prime}\in R_{2}$ and suppose by way of
contradiction that there exists a shortest $x,u$-path $P_{x,u}$ in $G$ that
contains $u^{\prime}$. Then
$d_{G}(u,x)=d_{G}(u,u^{\prime})+d_{G}(u^{\prime},x)$. Since $u\in R_{2}$,
there exists a vertex $u^{\prime\prime}\in R_{1}$, and a shortest
$x,u^{\prime\prime}$-path $P_{x,u^{\prime\prime}}$ of $G$ passing through $u$.
We are going to show that $u^{\prime\prime}$, $u$, and $u^{\prime}$ lie on a
common shortest path in $G-x$. If not, it follows that there exists a shortest
$u^{\prime},u^{\prime\prime}$-path in $G-x$ such that
$d_{G-x}(u^{\prime},u^{\prime\prime})<d_{G-x}(u^{\prime},u)+d_{G-x}(u,u^{\prime\prime})$.
From our assumption, $x$ does not lie on any shortest
$u^{\prime},u^{\prime\prime}$-path, any shortest $u^{\prime},u$-path, and any
shortest $u,u^{\prime\prime}$-path in $G$. Therefore,
$d_{G-x}(u^{\prime},u^{\prime\prime})=d_{G}(u^{\prime},u^{\prime\prime})$,
$d_{G-x}(u,u^{\prime\prime})=d_{G}(u,u^{\prime\prime})$, and
$d_{G-x}(u,u^{\prime})=d_{G}(u,u^{\prime})$. Then

$\displaystyle d_{G}(x,u^{\prime\prime})$
$\displaystyle=d_{G}(x,u)+d_{G}(u,u^{\prime\prime})$
$\displaystyle=d_{G}(x,u^{\prime})+d_{G}(u^{\prime},u)+d_{G}(u,u^{\prime\prime})$
$\displaystyle=d_{G}(x,u^{\prime})+d_{G-x}(u^{\prime},u)+d_{G-x}(u,u^{\prime\prime})$
$\displaystyle>d_{G}(x,u^{\prime})+d_{G-x}(u^{\prime},u^{\prime\prime})$
$\displaystyle=d_{G}(x,u^{\prime})+d_{G}(u^{\prime},u^{\prime\prime})$
$\displaystyle\geq d_{G}(x,u^{\prime\prime})\,,$

which is not possible. This contradiction implies that
$d_{G-x}(u^{\prime},u^{\prime\prime})=d_{G-x}(u^{\prime},u)+d_{G-x}(u,u^{\prime\prime})$,
hence $u$ lies on a shortest $u^{\prime},u^{\prime\prime}$-path of $G-x$.
Since we have assumed that $\\{u,u^{\prime},u^{\prime\prime}\\}\subseteq R$ is
a general position set of $G-x$, we have obtained a contradiction which
implies that $R_{2}$ is an $x$-colinear set of $G$.

We now claim that $R_{1}$ and $R_{2}$ are general position sets of $G$.
Suppose first that $R_{1}$ is not a general position sets of $G$. Then there
exist vertices $u,v,w\in R_{1}$ and a shortest $u,w$-path $P$ in $G$ that
passes through $v$. Since $R_{1}\subseteq R$ and $R$ is a general position set
of $G-x$, the path $P$ must contain the vertex $x$. But then $v\notin R_{1}$,
a contradiction. Suppose second that $R_{2}$ is not a general position sets of
$G$. Then there exist vertices $u,v,w\in R_{2}$ and a shortest $u,w$-path $P$
in $G$ that passes through $v$. Again we see that the path $P$ must contain
the vertex $x$. Assume without loss of generality that $x$ lies between $u$
and $v$ on $P$. Since $w\in R_{2}$, there exists a vertex $w^{\prime}\in
R_{1}$, such that $w$ is on a shortest $w^{\prime},x$-path. But then
$w^{\prime},w,v$ lie on a common geodesic, a contradiction with the assumption
that $R$ is a general position set of $G-x$.

Since $R_{1}$ and $R_{2}$ are general position sets of $G$, we can conclude
that

${\rm gp}(G)\geq\max\\{|R_{1}|,|R_{2}|\\}\geq\frac{1}{2}|R|=\frac{1}{2}{\rm
gp}(G-x)\,,$

hence ${\rm gp}(G-x)\leq 2{\rm gp}(G)$.

To show that the bound is sharp, consider the subdivided graph $S(K_{1,n})$,
$n\geq 2$, of the star $K_{1,n}$, that is, the graph obtained from $K_{1,n}$
by subdividing each of its edges once. Let $x$ be the vertex of degree $n$ of
$S(K_{1,n})$. Since $S(K_{1,n})-x\cong nK_{2}$ and having Proposition 2.3 in
mind, we can conclude that ${\rm gp}(S(K_{1,n})-x)=2n=2{\rm gp}(S(K_{1,n}))$.
$\square$

There is no general lower bound on ${\rm gp}(G-x)$ in terms of ${\rm gp}(G)$.
To demonstrate it, consider the fan graphs $F_{n}$, $n\geq 3$. By Proposition
2.4 we have ${\rm gp}(F_{n})=\lceil\frac{2n}{3}\rceil$. Since clearly ${\rm
gp}(F_{n}-x)=2$, where $x$ is the vertex of $F_{n}$ of degree $n$, we see that
${\rm gp}(G-x)$ can indeed be arbitrary smaller than ${\rm gp}(G)$. The next
result leads to many additional such examples.

###### Proposition 3.2

Let $S$ be an independent set of a graph $H$ with $|S|=\alpha(H)$. If $G$ is
the graph obtained from the disjoint union of $H$ and a vertex $x$ by joining
$x$ to each vertex of $S$, then ${\rm gp}(G)\geq\alpha(H)$.

Proof. In $G$, the set $S$ is an independent set of vertices that are pairwise
at distance $2$. Hence $S$ is a general position set of $H$ and the conclusion
follows. $\square$

In Proposition 3.2 we have $H\cong G-x$, hence ${\rm gp}(G-x)={\rm gp}(H)$.
Thus, if ${\rm gp}(H)$ is much smaller than $\alpha(H)$, then ${\rm gp}(G-x)$
is much smaller than ${\rm gp}(G)$. For instance, such graphs are grids
$P_{n}\,\square\,P_{m}$, $n,m\geq 3$, for which we know that ${\rm
gp}(P_{n}\,\square\,P_{m})=4$ [18, Corollary 3.2].

On the other hand, under some additional assumption, ${\rm gp}(G-x)$ can be
bounded from below with ${\rm gp}(G)$ as follows.

###### Proposition 3.3

Let $x$ be a vertex of a graph $G$. If $x$ lies in some gp-set of $G$, then
${\rm gp}(G)-1\leq{\rm gp}(G-x)$.

Proof. Let $S$ be a gp-set of $G$ and $x\in S$. Suppose that
$S\setminus\\{x\\}$ is not a general position set of $G-x$. Then there are
three distinct vertices $u,v,w\in S\setminus\\{x\\}$ lying on a shortest path
in $G-x$. Without loss of generality, assume that $v$ lies on a $u,w$-geodesic
in $G-x$. Since $S$ is a gp-set of $G$, but $S\setminus\\{x\\}$ is not a
general position set of $G-x$, $x$ must lie on a $u,w$-geodesic in $G$. This
contradicts our assumption. Hence, $S\setminus\\{x\\}$ is a general position
set of $G-x$. It concludes that ${\rm gp}(G-x)\geq|S|-1={\rm gp}(G)-1.$
$\square$

##  4 Two constructions

In Theorem 3.1 we have proved that the bound ${\rm gp}(G-x)\leq 2{\rm gp}(G)$
is sharp. However, the sharpness examples were such that $G-x$ is not
connected. In this section we give two constructions which show that ${\rm
gp}(G-x)$ can be much larger than ${\rm gp}(G)$ also when $G-x$ is connected.

In the first construction let $H_{n}$, $n\geq 3$, be the graph defined as
follows. Its vertex set is $Y_{2n}\cup\\{x,x^{\prime}\\}\cup Z_{n}$, where
$Y_{2n}=\\{y_{1},\ldots,y_{2n}\\}$ and $Z_{n}=\\{z_{1},\ldots,z_{n}\\}$. The
vertices of $Y_{2n}$ induce a complete subgraph $K_{2n}$, the vertices of
$\\{x,x^{\prime}\\}\cup Z_{n}$ induce a complete bipartite graph $K_{2,n}$
with the corresponding bipartition, the vertex $x$ is adjacent to vertices
$y_{1},\ldots,y_{n}$, and the vertex $x^{\prime}$ is adjacent to $y_{n+1}$.
See Fig. 1.

$\vdots$$\vdots$$\vdots$$y_{1}$$y_{n}$$y_{n+1}$$y_{n+2}$$y_{2n}$$x$$x^{\prime}$$z_{1}$$z_{2}$$z_{n}$$Y_{2n}$$Z_{n}$$\vdots$$\vdots$
Figure 1: Graph $H_{n}$.

###### Proposition 4.1

If $n\geq 3$, then ${\rm gp}(H_{n})=2n+1$ and ${\rm gp}(H_{n}-x)=3n-1$.

Proof. Set $Y_{j}=\\{y_{1},\ldots,y_{j}\\}$ for $j\in\\{n,n+1\\}$. We claim
that $Y_{n+1}\cup Z_{n}$ is a general position set of $H_{n}$. Consider any
two vertices $u$ and $v$ from $Y_{n+1}\cup Z_{n}$. If $u,v\in Y_{n+1}$, then
$d_{H_{n}}(u,v)=1$. If $u,v\in Z_{n}$, then since
$H_{n}[\\{x,x^{\prime}\\}\cup Z_{n}]\cong K_{2,n}$, we have
$d_{H_{n}}(u,v)=2$. Finally, if $u\in Y_{n+1}$ and $v\in Z_{n}$, then
$d_{H_{n}}(u,v)=2$. Hence, having Theorem 2.5 in mind, $Y_{n+1}\cup Z_{n}$ is
a general position set of $H_{n}$. It follows that ${\rm
gp}(H_{n})\geq|Y_{n+1}\cup Z_{n}|=2n+1$.

To prove the upper bound on ${\rm gp}(H_{n})$, suppose on the contrary that
${\rm gp}(H_{n})\geq 2n+2$ and let $R$ be a gp-set of $H_{n}$. We claim first
that $|Y_{n}\cap R|\geq 1$ and $|Z_{n}\cap R|\geq 1$. Indeed, if $|Y_{n}\cap
R|=0$, then $R=\\{y_{n+1},\ldots,y_{2n}\\}\cup\\{x,x^{\prime}\\}\cup Z_{n}$,
but this is clearly not a general position set. Similarly, if $|Z_{n}\cap
R|=0$, then $R=Y_{2n}\cup\\{x,x^{\prime}\\}$, which is also not a general
position set as $y_{2n}$, $y_{n+1}$, and $x^{\prime}$ lie on a common shortest
path. Hence the claim. Since $|Y_{n}\cap R|\geq 1$ and $|Z_{n}\cap R|\geq 1$,
we get that $x\not\in R$ and $(Y_{2n}\setminus Y_{n+1})\cap R=\emptyset$. It
follows that $R=Y_{n+1}\cup\\{x^{\prime}\\}\cup Z_{n}$. But then $z_{n}$,
$x^{\prime}$, and $y_{n+1}$ are on a shortest path. This final contradiction
proves that ${\rm gp}(H_{n})\leq 2n+1$. We have thus shown that ${\rm
gp}(H_{n})=2n+1$.

Consider now $H_{n}-x$ and note that ${\rm diam}(H_{n}-x)={\rm
diam}(H_{n})=3$. In [5, Theorem 2.4] it was proved that if $G$ is a graph,
then ${\rm gp}(G)\leq n(G)-{\rm diam}(G)+1$. Hence ${\rm gp}(H_{n}-x)\leq
3n-1$. Invoking Theorem 2.5 again, we infer that
$(Y_{2n}\setminus\\{y_{n+1}\\})\cup Z_{n}$ is a general position set of
$H_{n}-x$ which in turn implies that ${\rm gp}(H_{n}-x)=3n-1$. $\square$

We next give another family of graphs in which the general position number
increases arbitrary by removing a vertex. If $k\geq 2$, then let the graph
$G_{k}$ be constructed as follows. Let $V(G_{k})=X_{k}\cup Y_{k}\cup
Z_{k+1}\cup\\{w\\}$, where $X_{k}=\\{x_{1},\ldots,x_{k}\\}$,
$Y_{k}=\\{y_{1},\ldots,y_{k}\\}$, and $Z_{k+1}=\\{z_{1},\ldots,z_{k+1}\\}$.
The vertex $w$ is adjacent to every vertex of $X_{k}\cup Y_{k}$, the vertices
of $Z_{k+1}$ induce a complete graph $K_{k+1}$, $z_{2}$ is adjacent to
$y_{2},\ldots,y_{k}$, and $z_{1}$ is adjacent to $y_{1}$, see Fig. 2. Note
that ${\rm diam}(G_{k})=4$, and that $X_{k}$ and $Y_{k}$ are independent sets
of vertices.

$w$$x_{1}$$x_{2}$$x_{k}$$y_{1}$$y_{2}$$y_{k}$$z_{1}$$z_{2}$$z_{k}$$z_{k+1}$$X_{k}$$Y_{k}$$Z_{k+1}$$\vdots$$\vdots$$\vdots$$\vdots$
Figure 2: Graph $G_{k}$.

###### Proposition 4.2

If $k\geq 2$, then ${\rm gp}(G_{k})=2k$ and ${\rm gp}(G_{k}-z_{2})=3k-2$.

Proof. Let $P_{1}$ be the path induced by the vertices $x_{1},w,y_{1}$, and
$z_{1}$. Let $P_{i}=x_{i}wy_{i}z_{2}z_{i+1}$ be a path of $G_{k}$, where
$2\leq i\leq k$. Set $\Psi=\\{P_{i}:\ i\in[k]\\}$. Then it follows that
$|\Psi|=k$. It is observed that $\Psi$ is a set of isometric paths of $G_{k}$.
By Proposition 2.2, ${\rm gp}(G_{k})\leq 2k$. To show ${\rm gp}(G_{k})\geq
2k$, note that $G[X_{k}\cup Y_{k}\cup\\{w\\}]\cong K_{1,2k}$, hence
Proposition 2.3 implies that ${\rm gp}(G[X_{k}\cup Y_{k}\cup\\{w\\}])=2k$.
Since $G[X_{k}\cup Y_{k}\cup\\{w\\}]$ is an isometric subgraph of $G_{k}$, we
conclude that ${\rm gp}(G_{k})\geq 2k$ and thus ${\rm gp}(G_{k})=2k$.

Consider $G_{k}-z_{2}$. It is straightforward to check that
$S=V(G_{k}-z_{2})\setminus\\{w,y_{1},z_{1}\\}$ is a general position set of
$G_{k}-z_{2}$. For instance, any shortest path between a vertex $x_{i}\in
X_{k}$ and any other vertex from $S$ avoids other vertices of $S$ because
$d_{G_{k}-z_{2}}(x_{i},x_{j})=2$, $d_{G_{k}-z_{2}}(x_{i},y_{j})=2$, and
$d_{G_{k}-z_{2}}(x_{i},z_{j})=4$ for $j\geq 3$. In the latter case, a shortest
$x_{i},z_{j}$-path, induced by the vertices $x_{i},w,y_{1},z_{1}$, and
$z_{j}$, is unique. Thus ${\rm gp}(G_{k}-z_{2})\geq 3k-2$. On the other hand,
suppose that $S$ is a general position set of $G_{k}-z_{2}$ of size $3k-1$.
Because $n(G_{k}-z_{2})=3k+1$, we have
$S\cap\\{w,y_{1},z_{1}\\}\neq\emptyset$. But then we find a vertex from
$X_{k}$, a vertex from $\\{w,y_{1},z_{1}\\}$, and a vertex from
$Z_{k+1}\setminus\\{z_{1},z_{2}\\}$, such that these three vertices from $S$
and lie on a common shortest path in $G_{k}-z_{2}$. As a consequence, we
conclude that ${\rm gp}(G_{k}-z_{2})\leq 3k-2$ and thus we have ${\rm
gp}(G_{k}-z_{2})=3k-2$. $\square$

##  5 Vertex removing in diameter $2$ graphs

Note that for the graphs $H_{n}$ from Proposition 4.1 we have ${\rm
diam}(H_{n})=3$ as well as ${\rm diam}(H_{n}-x)=3$. Also, for the graphs
$G_{k}$ from Proposition 4.2 we have ${\rm diam}(G_{k})=4$ as well as ${\rm
diam}(G_{k}-z_{2})=4$. In both cases we have seen that removing a vertex
increases the general position number arbitrarily. In this section we
therefore focus on the vertex removing operation in diameter $2$ graphs. We
first show that in this case Theorem 3.1 sharpens as ${\rm gp}(G-x)\leq{\rm
gp}(G)$. Second, we prove that if the diameter of $G-x$ remains $2$, then
${\rm gp}(G)-1\leq{\rm gp}(G-x)\leq{\rm gp}(G)$. Before presenting these
results, we consider some examples.

The gp-number of a diameter $2$ graph may stay the same after a vertex is
removed. Consider for instance complete bipartite graphs $K_{n,m}$, where
$2\leq n\leq m$. Then it is known that ${\rm gp}(K_{n,m})=m$, see [5,
Proposition 2.2]. Hence if $x$ is a vertex of $K_{n,m}$ from a smaller
partition set, then ${\rm gp}(K_{n,m}-x)=m={\rm gp}(K_{n,m})$. Consider next
the Petersen graph $P$. Then ${\rm gp}(P)=6$, see [17, page 184]. If $x\in
V(P)$, then ${\rm diam}(P-x)=3$. Moreover, by a case analysis we can check
that ${\rm gp}(P-x)=5$. See Fig. 3 where a gp-set in $P-x$ is marked with
black vertices.

$x$ Figure 3: A gp-set of $P-x$.

###### Proposition 5.1

If $x$ is a vertex of a diameter $2$ graph $G$, then ${\rm gp}(G-x)\leq{\rm
gp}(G)$.

Proof. To prove the proposition it suffices to show that if $S$ is a gp-set of
$G-x$, then $S$ is also a general position set of $G$. Let $u,v,w$ be vertices
from $S$ and suppose by way of contradiction that they lie on a shortest path
in $G$. As ${\rm diam}(G)=2$, the vertices $u,v,w$ induce an isometric $P_{3}$
in $G$. But then this path is also isometric in $G-x$, a contradiction.
$\square$

###### Theorem 5.2

Let $x$ be a vertex of a diameter $2$ graph $G$. If ${\rm diam}(G-x)=2$, then
${\rm gp}(G)-1\leq{\rm gp}(G-x)\leq{\rm gp}(G)$. Moreover, the bounds are
sharp.

Proof. The upper bound follows by Proposition 5.1. Assume that ${\rm
diam}(G)={\rm diam}(G-x)=2$, where $x\in V(G)$. Then we can prove along the
lines of the proof of Proposition 5.1 that if $S$ is a gp-set of $G$, then
$S\setminus\\{x\\}$ is a general position set of $G-x$. Hence ${\rm
gp}(G-x)\geq|S\setminus\\{x\\}|\geq|S|-1={\rm gp}(G)-1$.

Let $n_{1}\geq\cdots\geq n_{k}\geq 2$, $k\geq 3$, and let
$G_{n_{1},\ldots,n_{k}}$ be the graph obtained from the disjoint union of
$K_{n_{1}},\ldots,K_{n_{k}}$ by selecting a vertex in each of the complete
graphs and identify all of them into a single vertex. Then ${\rm
gp}(G_{n_{1},\ldots,n_{k}})=n_{1}+\cdots+n_{k}-k$. If $x$ is an arbitrary
vertex of $G_{n_{1},\ldots,n_{k}}$ which is not its maximum degree vertex,
then ${\rm gp}(G_{n_{1},\ldots,n_{k}}-x)={\rm gp}(G_{n_{1},\ldots,n_{k}})-1$.
This demonstrates sharpness of the lower bound as these graphs are of diameter
2.

Let next $n_{1}\geq\cdots\geq n_{k}\geq 2$, where $k\geq 2$ and $n_{1}>k$, and
consider the complete multipartite graph $K_{n_{1},\ldots,n_{k}}$. Then ${\rm
gp}(K_{n_{1},\ldots,n_{k}})=n_{1}$ and if $x$ is an arbitrary vertex which
does not lie in the $n_{1}$-part, then ${\rm
gp}(K_{n_{1},\ldots,n_{k}}-x)=n_{1}$, which demonstrates sharpness of the
upper bound. $\square$

Another family which demonstrates sharpness of the upper bound in Theorem 5.2
is the family $K_{n}\boxtimes C_{m}$, where $n\geq 2$ and $m\in\\{4,5\\}$. By
[15, Proposition 4.3] we have ${\rm gp}(K_{n}\boxtimes C_{4})=2n$ and ${\rm
gp}(K_{n}\boxtimes C_{5})=3n$. Moreover, it is straightforward to check that
the general position number does not change after one vertex is removed from
these graphs.

Putting together Propositions 3.3 and 5.1, and Theorem 5.2, the following
conclusion follows.

###### Corollary 5.3

Let $x$ be a vertex of a diameter $2$ graph $G$. If ${\rm diam}(G-x)=2$, or
$x$ lies in some gp-set of $G$, then

${\rm gp}(G)-1\leq{\rm gp}(G-x)\leq{\rm gp}(G)\,.$

##  6 Edge removing in general graphs

In this section we consider how much the general position number can be
affected by removing an edge. Contrary to the vertex removal, we can give
general sharp lower and upper bounds. To prove them, we first recall the
following well-known sets from metric graph theory. For instance, these sets
are constitutional stones of partial cubes [22], of distance-balanced graphs
[10], of $\ell$-distance-balanced graphs [20], and of the Mostar index [1].

If $e=uv$ is an edge of a graph $G$, then

$\displaystyle W_{uv}$ $\displaystyle=\\{w\in V(G):\
d_{G}(u,w)<d_{G}(v,w)\\},$ $\displaystyle W_{vu}$ $\displaystyle=\\{w\in
V(G):\ d_{G}(v,w)<d_{G}(u,w)\\},$ ${}_{v}W_{u}$ $\displaystyle=\\{w\in V(G):\
d_{G}(u,w)=d_{G}(v,w)\\}\,.$

For vertices $x,y\in V(G)$, let further ${\cal P}_{G}(x,y)$ be the set of all
shortest $x,y$-paths in $G$. The following technical lemma about these sets
will be crucial for our following arguments.

###### Lemma 6.1

Let $e=uv$ be an edge in a graph $G$ and let $x,y\in W_{uv}\cup\,_{v}W_{u}$.
Then ${\cal P}_{G}(x,y)={\cal P}_{G-e}(x,y)$.

Proof. Let $P\in{\cal P}_{G}(x,y)$. We claim that $P$ does not contain $e$.
Suppose on the contrary that $P$ contains $e$. Assume first that the sequence
of the vertices on $P$ is $x,\ldots,v,u,\ldots,y$. Since $d_{G}(x,u)\leq
d_{G}(x,v)$, the path $P$ is not shortest in $G$, a contradiction. Assume
second that the sequence of the vertices on $P$ is $x,\ldots,u,v,\ldots,y$.
But now the fact that $d_{G}(y,u)\leq d_{G}(y,v)$ gives another contradiction
with the assumption that $P$ is shortest in $G$. We can conclude that
$P\in{\cal P}_{G-e}(x,y)$, therefore ${\cal P}_{G}(x,y)\subseteq{\cal
P}_{G-e}(x,y)$.

Let now $P\in{\cal P}_{G-e}(x,y)$. Suppose that $P\notin{\cal P}_{G}(x,y)$.
This means that there exists an $x,y$-path $Q$ in $G$ shorter than $P$. For
this to happen, $Q$ must necessarily contain the edge $uv$. But then we can
argue analogously as in the first paragraph that $Q$ is not a shortest path.
This contradiction implies that $P\in{\cal P}_{G}(x,y)$. Consequently, ${\cal
P}_{G-e}(x,y)\subseteq{\cal P}_{G}(x,y)$, and we are done. $\square$

The main result of this section reads as follows.

###### Theorem 6.2

If $e$ is an edge of a graph $G$, then

$\frac{{\rm gp}(G)}{2}\leq{\rm gp}(G-e)\leq\ 2{\rm gp}(G)\,.$

Moreover, both bounds are sharp.

Proof. Let $e=uv$ and let $X$ be a gp-set of $G$. Setting

$\displaystyle X_{uv}$ $\displaystyle=\\{w\in X:\ d_{G}(u,w)<d_{G}(v,w)\\},$
$\displaystyle X_{vu}$ $\displaystyle=\\{w\in X:\ d_{G}(v,w)<d_{G}(u,w)\\},$
${}_{v}X_{u}$ $\displaystyle=\\{w\in X:\ d_{G}(u,w)=d_{G}(v,w)\\},$

we have $X=X_{uv}\cup X_{vu}\cup\,_{v}X_{u}$. Let
$X_{u}=X_{uv}\cup\,_{v}X_{u}$ and $X_{v}=X_{vu}\cup\,_{v}X_{u}$. We now show
that $X_{u}$ and $X_{v}$ are general position sets of $G-e$. By symmetry it
suffices to prove the claim for $X_{u}$. Consider any two vertices $x,y\in
X_{u}$ and let $P$ be an arbitrary shortest $x,y$-path in $G-e$. By Lemma 6.1,
the path $P$ is also a shortest $x,y$-path in $G$, hence $V(P)\cap
X_{u}\subseteq\\{x,y\\}$. It follows that $X_{u}$ is a general position set of
$G-e$ and hence also $X_{v}$ is such. Therefore

${\rm gp}(G-e)\geq\max\\{|X_{u}|,|X_{v}|\\}\geq\frac{|X|}{2}=\frac{{\rm
gp}(G)}{2}\,.$

This proves the lower bound.

To prove the upper bound we proceed similarly as above. For this sake let $Y$
be a gp-set of $G-e$ and partition $Y$ into the following subsets:

$\displaystyle Y_{uv}$ $\displaystyle=\\{w\in Y:\
d_{G-e}(u,w)<d_{G-e}(v,w)\\},$ $\displaystyle Y_{vu}$ $\displaystyle=\\{w\in
Y:\ d_{G-e}(v,w)<d_{G-e}(u,w)\\},$ ${}_{v}Y_{u}$ $\displaystyle=\\{w\in Y:\
d_{G-e}(u,w)=d_{G-e}(v,w)\\}.$

Then, using Lemma 6.1 as above, $Y_{u}=Y_{uv}\cup\,_{v}Y_{u}$ and
$Y_{v}=Y_{vu}\cup\,_{v}Y_{u}$ are general position sets of $G$. Hence

${\rm gp}(G)\geq\max\\{|Y_{u}|,|Y_{v}|\\}\geq\frac{|Y|}{2}=\frac{{\rm
gp}(G-e)}{2}\,,$

which proves the upper bound.

To prove sharpness of the lower bound, let $k\geq 3$ and let $G_{k}^{\prime}$
be the graph constructed as follows. Consider the disjoint union of four
copies of $K_{2,k}$, where in two copies an extra edge between its degree $k$
vertices is added (these are the edges $f$ and $f^{\prime}$ in Fig. 4). Then
circularly connect these four graphs by three edges and a path of length $8$
as shown in Fig. 4.

⋮⋮⋮⋮$e$$f$$f^{\prime}$ Figure 4: Graph $G_{k}^{\prime}$.

Let $e$ be the edge incident with $f$ and $f^{\prime}$. Then it is
straightforward to check that ${\rm gp}(G_{k}^{\prime})=4k$ and ${\rm
gp}(G_{k}^{\prime}-e)=2k$.

To prove sharpness of the upper bound, let $k\geq 3$ and let
$G_{k}^{\prime\prime}$ be a graph constructed similarly as $G_{k}^{\prime}$,
the construction of $G_{k}^{\prime\prime}$ should be clear from Fig. 5.

⋮⋮⋮⋮$e$ Figure 5: Graph $G_{k}^{\prime\prime}$.

We can directly check that ${\rm gp}(G_{k}^{\prime\prime})=2k$ and ${\rm
gp}(G_{k}^{\prime\prime}-e)=4k$. $\square$

We next consider how the general position number changes when removing an edge
from diameter $2$ graphs.

###### Theorem 6.3

If $e$ is an edge of a diameter $2$ graph $G$, then

${\rm gp}(G)-1\leq{\rm gp}(G-e)\leq\ {\rm gp}(G)+1\,.$

Moreover, the bounds are sharp.

Proof. Let $e=uv$ and let $X$ be an arbitrary ${\rm gp}$-set of $G$. Assume
first that $u,v\notin X$. Then we claim that $X$ is also a general position
set in $G-e$. To see it, consider any two vertices $x,y\in X$. Since ${\rm
diam}(G)=2$ and $u,v\notin X$, no shortest $x,y$-path of $G$ contains the edge
$uv$, hence ${\cal P}_{G}(x,y)={\cal P}_{G-e}(x,y)$. Thus $X$ is a general
position set of $G-e$, so that in this case ${\rm gp}(G-e)\geq{\rm gp}(G)$.
Assume second that $u\in X$. Then we claim that $X^{\prime}=X\setminus\\{u\\}$
is a general position set in $G-e$. If $v\notin X$, then we see by the same
argument as above that $X^{\prime}$ is a general position set of $G-e$. It
remains to consider the subcase when $v\in X$. Since ${\rm diam}(G)=2$, the
only way that $X^{\prime}$ is not a general position set in $G-e$ would be
when there is a shortest path $Q$ in $G-e$ containing $v$ and two other
vertices of $X^{\prime}$. Since $Q$ is not a shortest path in $G$, there is a
shortest path in $G$ containing $u$, $v$, and another vertex of $X$, a
contradiction. We can conclude that $X^{\prime}$ is a general position set of
$G-e$ and therefore ${\rm gp}(G-e)\geq{\rm gp}(G)-1$.

Let $Y$ be an arbitrary ${\rm gp}$-set of $G-e$. Assume that $u,v\notin Y$. We
claim that $Y$ is a general position set of $G$. Consider any two vertices
$x,y$ from $Y$ and let $P$ be an arbitrary shortest $x,y$-path in $G$. Then
the path $P$ does not contain the edge $uv$ in $G$ as ${\rm diam}(G)=2$, hence
${\cal P}_{G}(x,y)={\cal P}_{G-e}(x,y)$. We thus have that $Y$ is a general
position set of $G$, and ${\rm gp}(G)\geq{\rm gp}(G-e)$. Assume now that $u\in
Y$. Then we claim that $Y^{\prime}=Y\setminus\\{u\\}$ is a general position
set of $G-e$. If $v\notin Y$, then similarly as above, $Y^{\prime}$ is a
general position set of $G$. It remains to consider the case when $v\in Y$.
Suppose on the contrary that there are three vertices from $Y^{\prime}$ such
that they lie on a common shortest path $P^{\prime}$ in $G$. Then the path
$P^{\prime}$ contains $v$ and two other vertices from $Y^{\prime}$. Since
$P^{\prime}$ is not a shortest path in $G-e$ and ${\rm diam}(G)=2$, there is a
shortest path in $G$ containing $u$, $v$, and two another vertices of
$Y^{\prime}$. It contradicts with the fact that ${\rm diam}(G)=2$. Hence
$Y^{\prime}$ is a general position set of $G$ and we can conclude that ${\rm
gp}(G)\geq{\rm gp}(G-e)-1$.

To show that the lower bound is sharp, consider once fan graphs $F_{n}$, this
time of order $n=3k$, $k\geq 3$, see Fig. 6.

$\ldots$$u$$v$$e$$3k-1$ Figure 6: Fan graph $F_{n}$ with $n=3k$.

By Proposition 2.4 we known that ${\rm gp}(F_{n})=\lceil\frac{2n}{3}\rceil$,
see Fig. 6 where the black vertices form a ${\rm gp}$-set of $F_{n}$. Let $uv$
be the edge of $F_{n}$ as shown in the figure. Then it is straightforward to
check that all the black vertices but $v$ form a ${\rm gp}$-set of $F_{n}-e$,
hence ${\rm gp}(F_{n}-e)={\rm gp}(F_{n})-1$.

To show sharpness of the upper bound, let $m\geq 3$ and let $G_{m}$ be the
graph constructed as follows. Start with $K_{m}$ and let $x,y$ be arbitrary,
fixed vertices of it. Then we set:

$\displaystyle V(G_{m})$
$\displaystyle=V(K_{m})\cup\\{x^{\prime},y^{\prime}\\}\,,$ $\displaystyle
E(G_{m})$
$\displaystyle=E(K_{m})\cup\\{x^{\prime}y^{\prime},x^{\prime}x,y^{\prime}y,x^{\prime}y\\}\,.$

Set $e=xx^{\prime}$. Then ${\rm diam}(G_{m})=2$ and it is easy to verify that
${\rm gp}(G_{m}-e)=m+1={\rm gp}(G_{m})+1$. $\square$

## Acknowledgements

This work was supported by the Slovenian Research Agency ARIS (research core
funding P1-0297 and projects N1-0285, N1-0218).

## Declaration of interests

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## Data availability

Our manuscript has no associated data.

## References

  * [1] A. Ali, T. Došlić, Mostar index: results and perspectives, Appl. Math. Comput. 404 (2021) Paper 126245.
  * [2] N. Almalki, P. Kaemawicharnurat, Independence number and connectivity of maximal connected domination vertex critical graphs, Commun. Comb. Optim. 9 (2024) 185–196.
  * [3] B.S. Anand, U. Chandran S.V., M. Changat, S. Klavžar, E.J. Thomas, Characterization of general position sets and its applications to cographs and bipartite graphs, Appl. Math. Comput. 359 (2019) 84–89.
  * [4] Y. Cao, G.T. Chen, G.M. Jing, S.L. Shan, Independence number of edge-chromatic critical graphs, J. Graph Theory 101 (2022) 288–310.
  * [5] U. Chandran S.V., G.J. Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Combin. 4 (2016) 135–143.
  * [6] M. Ghorbani, S. Klavžar, H.R. Maimani, M. Momeni, F. Rahimi-Mahid, G. Rus, The general position problem on Kneser graphs and on some graph operations, Discuss. Math. Graph Theory 41 (2021) 1199–1213.
  * [7] Q. Huo, L.-T. Yuan, Graphs with large maximum degree containing no edge-critical graphs, European J. Combin. 106 (2022) Paper 103576.
  * [8] V. Iršič, S. Klavžar, G. Rus, J. Tuite, General position polynomials, Results Math. 79 (2024) Paper 110.
  * [9] M. Jakovac, D. Štesl, On game chromatic vertex-critical graphs, Bull. Malays. Math. Sci. Soc. 46 (2023) Paper 27.
  * [10] J. Jerebic, S. Klavžar, D.F. Rall, Distance-balanced graphs, Ann. Combin. 12 (2008) 71–79.
  * [11] S. Klavžar, D. Kuziak, I. Peterin, I.G. Yero, A Steiner general position problem in graph theory, Comput. App. Math. 40 (2021) Paper 223.
  * [12] S. Klavžar, D.F. Rall, I.G. Yero, General $d$-position sets, Ars. Math. Contemp. 21 (2021) Paper #P1.03.
  * [13] S. Klavžar, G. Rus, The general position number of integer lattices, Appl. Math. Comput. 390 (2021) Paper 125664.
  * [14] S. Klavžar, E. Tan, Edge general position sets in Fibonacci and Lucas cubes, Bull. Malays. Math. Sci. Soc. 46 (2023) Paper 120.
  * [15] S. Klavžar, I.G. Yero, The general position problem and strong resolving graphs, Open Math. 17 (2019) 1126–1135.
  * [16] D. Korže, A. Vesel, General position sets in two families of Cartesian product graphs, Mediterr. J. Math. 20 (2023) Paper 203.
  * [17] P. Manuel, S. Klavžar, A general position problem in graph theory, Bull. Aust. Math. Sci. Soc. 98 (2018) 177–187.
  * [18] P. Manuel, S. Klavžar, The graph theory general position problem on some interconnection networks, Fund. Inform. 163 (2018) 339–350.
  * [19] P. Manuel, R. Prabha, S. Klavžar, The edge general position problem, Bull. Malays. Math. Sci. Soc. 45 (2022) 2997–3009.
  * [20] Š. Miklavič, P. Šparl, $\ell$-distance-balanced graphs, Discrete Appl. Math. 244 (2018) 143–154.
  * [21] D. Mubayi, Counting substructures I: Color critical graphs, Adv. Math. 225 (2010) 2731–2740.
  * [22] S. Ovchinnikov, Graphs and Cubes, Springer, New York, 2011.
  * [23] B. Patkós, On the general position problem on Kneser graphs, Ars Math. Contemp. 18 (2020) 273–280.
  * [24] T. Selig, Combinatorial aspects of sandpile models on wheel and fan graphs, European J. Combin. 110 (2023) Paper 103663.
  * [25] E.J. Thomas, U. Chandran S.V., Characterization of classes of graphs with large general position number, AKCE Int. J. Graphs Comb. 17 (2020) 935–939.
  * [26] E.J. Thomas, U. Chandran S.V., J. Tuite, G. Di Stefano, On monophonic position sets in graphs, Discrete Appl. Math. (2023) doi.org/10.1016/j.dam.2023.02.021.
  * [27] J. Tian, S. Klavžar, E. Tan, Extremal edge general position sets in some graphs, Graph Combin. 40 (2024) Paper 40.
  * [28] J. Tian, K. Xu, On the general position number of the $k$-th power graphs, Quaest. Math. (2024) doi.org/10.2989/16073606.2024.2352568.
  * [29] J. Tian, K. Xu, D. Chao, On the general position numbers of maximal outerplane graphs, Bull. Malays. Math. Sci. Soc. 46 (2023) Paper 198.
  * [30] J. Tian, K. Xu, S. Klavžar, The general position number of Cartesian product of two trees, Bull. Aust. Math. Soc. 14 (2021) 1–10.
  * [31] Y. Yao, M. He, S. Ji, On the general position number of two classes of graphs, Open Math. 20 (2022) 1021–1029.
  * [32] M. Zamime, On the $sd_{b}$-critical graphs, Trans. Comb. 13 (2024) 363–375.


International Journal of Group Theory Vol. XX No. X (201X), pp XX-XX.

# On Varietal Capability of Infinite Direct Products of Groups

Hanieh Mirebrahimi∗ and Behrooz Mashayekhy

###### Abstract.

Recently, the authors gave some conditions under which a direct product of
finitely many groups is $\mathcal{V}-$capable if and only if each of its
factors is $\mathcal{V}-$capable for some varieties $\mathcal{V}$. In this
paper, we extend this fact to any infinite direct product of groups. Moreover,
we conclude some results for $\mathcal{V}-$capability of direct products of
infinitely many groups in varieties of abelian, nilpotent and polynilpotent
groups.

MSC(2010): Primary: 20E10; Secondary: , 20K25, 20E34, 20D15, 20F18.
Keywords: Capable group, Direct product, Variety of groups,
$\mathcal{V}-$capable group, direct limit.
Received: 30 April 2009, Accepted: 21 June 2010.
$*$Corresponding author
$\copyright$ 2011 University of Isfahan

Communicated by

##  1\. Introduction

R. Baer [1] initiated an investigation of the question ”which conditions a
group $G$ must fulfill in order to be the group of inner automorphisms of a
group $E$?”, that is $G\cong E/Z(E)$. Following M. Hall and J. K. Senior [5],
such a group $G$ is called capable. Baer [1] determined all capable groups
which are direct sums of cyclic groups. As P. Hall [4] mentioned,
characterizations of capable groups are important in classifying groups of
prime-power order.

F. R. Beyl, U. Felgner and P. Schmid [2] proved that every group $G$ possesses
a uniquely determined central subgroup $Z^{*}(G)$ which is minimal subject to
being the image in $G$ of the center of some central extension of $G$. This
$Z^{*}(G)$ is characteristic in $G$ and is the image of the center of every
stem cover of $G$. Moreover, $Z^{*}(G)$ is the smallest central subgroup of
$G$ whose factor group is capable [2]. Hence $G$ is capable if and only if
$Z^{*}(G)=1$. They showed that the class of all capable groups is closed under
the direct products. Also, they presented a condition in which the capability
of a direct product of finitely many of groups implies the capability of each
of the factors. Moreover, they proved that if $N$ is a central subgroup of
$G$, then $N\subseteq Z^{*}(G)$ if and only if the mapping $M(G)\rightarrow
M(G/N)$ induced by the natural epimorphism, is monomorphism.

Then M. R. R. Moghadam and S. Kayvanfar [10] generalized the concept of
capability to $\mathcal{V}-$capability for a group $G$. They introduced the
subgroup $(V^{*})^{*}(G)$ which is associated with the variety $\mathcal{V}$
defined by a set of laws $V$ and a group $G$ in order to establish a necessary
and sufficient condition under which $G$ can be $\mathcal{V}-$capable. They
also showed that the class of all $\mathcal{V}-$capable groups is closed under
the direct products. Moreover, they exhibited a close relationship between the
groups $\mathcal{V}M(G)$ and $\mathcal{V}M(G/N)$, where $N$ is a normal
subgroup contained in the marginal subgroup of $G$ with respect to the variety
$\mathcal{V}$. Using this relationship, they gave a necessary and sufficient
condition for a group $G$ to be $\mathcal{V}-$capable.

The authors [7] presented some conditions in which the $\mathcal{V}-$capablity
of a direct product of finitely many groups implies the
$\mathcal{V}-$capablity of each of its factors. In this paper, we extend this
fact to direct product of an infinite family of groups. Also, we deduce some
new results about the $\mathcal{V}-$capability of direct product of infinitely
many groups, where $\mathcal{V}$ is the variety of abelian, nilpotent, or
polynilpotent groups.

##  2\. Main Results

Suppose that $\mathcal{V}$ is a variety of groups defined by the set of laws
$V$. A group $G$ is said to be $\mathcal{V}-$capable if there exists a group
$E$ such that $G\cong E/V^{*}(E)$, where $V^{*}(E)$ is the marginal subgroup
of $E$, which is defined as follows [6]:

$\\{g\in E\ |\
v(x_{1},x_{2},...,x_{n})=v(x_{1},x_{2},...,gx_{i},x_{i+1},...,x_{n})\ $
$\forall x_{1},x_{2},...,x_{n}\in E,\ \forall i\in\\{1,2,...,n\\}\\}.$

If $\psi:E\rightarrow G$ is a surjective homomorphism with $ker\psi\subseteq
V^{*}(E)$, then the intersection of all subgroups of the form $\psi(V^{*}(E))$
is denoted by $(V^{*})^{*}(G)$. It is obvious that $(V^{*})^{*}(G)$ is a
characteristic subgroup of $G$ contained in $V^{*}(G)$. If $\mathcal{V}$ is
the variety of abelian groups, then the subgroup $(V^{*})^{*}(G)$ is the same
as $Z^{*}(G)$ and in this case $\mathcal{V}-$capability is equal to capability
[10]. In the following, there are some results which we need them in sequel.

######  Theorem 2.1.

[10] (i) A group $G$ is $\mathcal{V}-$capable if and only if
$(V^{*})^{*}(G)=1$.
(ii) If $\\{G_{i}\\}_{i\in I}$ is a family of groups, then
$(V^{*})^{*}(\prod_{i\in I}G_{i})\subseteq\prod_{i\in I}(V^{*})^{*}(G_{i}).$

As a consequence, if the $G_{i}$’s are $\mathcal{V}-$capable groups, then
$G=\prod_{i\in I}G_{i}$ is also $\mathcal{V}-$capable. In the above theorem,
the equality does not hold in general (see Example $2.3$ of [7]).

######  Theorem 2.2.

[10] Let $\mathcal{V}$ be a variety of groups with a set of laws $V$. Let $G$
be a group and $N$ be a normal subgroup with the property $N\subseteq
V^{*}(G)$. Then $N\subseteq(V^{*})^{*}(G)$ if and only if the homomorphism
induced by the natural map ${\mathcal{V}}M(G)\rightarrow{\mathcal{V}}M(G/N)$
is a monomorphism.

We recall that the Baer-invariant of a group $G$, with the free presentation
$F/R$, with respect to the variety ${\mathcal{V}}$, denoted by
${\mathcal{V}}M(G)$, is

${\mathcal{V}}M(G)=\frac{R\cap V(F)}{[RV^{*}F]}\ ,$

where $V(F)$ is the verbal subgroup of $F$ with respect to $\mathcal{V}$ and

$[RV^{*}F]=<v(f_{1},\ldots,f_{i-1},f_{i}r,f_{i+1},\ldots,f_{n})v(f_{1},\ldots,f_{i},\ldots,f_{n})^{-1}|r\in
R,$ $f_{i}\in F,v\in V,1\leq i\leq n,n\in{\bf N}>\ .$

It is known that the Baer-invariant of a group $G$ is always abelian and
independent of the choice of the presentation of $G$. Also if $\mathcal{V}$ is
the variety of abelian groups, then the Baer-invariant of $G$ will be ${R\cap
F^{\prime}}/{[R,F]}\cong M(G)$, where $M(G)$ is the Schur multiplier of $G$
(see [6]).

######  Theorem 2.3.

[7] Let $\mathcal{V}$ be a variety, $A$ and $B$ be two groups with
${\mathcal{V}}M({A\times
B})\cong{\mathcal{V}}M({A})\times{\mathcal{V}}M({B})$, then
$(V^{*})^{*}(A\times B)=(V^{*})^{*}(A)\times(V^{*})^{*}(B)$. Consequently,
$A\times B$ is $\mathcal{V}$-capable if and only if $A$ and $B$ are both
$\mathcal{V}$-capable.

######  Theorem 2.4.

[8]Let $\\{G_{i};\phi_{i}^{j},I\\}$ be a directed system of groups. Then, for
a given variety ${\mathcal{V}}$, the Baer-invariant preserves direct limit,
that is
${\mathcal{V}}M(\displaystyle{\lim_{\rightarrow}G_{i}})=\displaystyle{\lim_{\rightarrow}{\mathcal{V}}M(G_{i})}$.

######  Lemma 2.5.

For any family of groups $\\{G_{i}\\}_{i\in I}$, consider the directed system
$\\{\mathcal{G}_{I_{\lambda}},\phi^{\lambda^{\prime}}_{\lambda},\Lambda\\}$
consisting of all finite direct products
$\mathcal{G}_{I_{\lambda}}=\prod_{i\in I_{\lambda}}G_{i}$ ($I_{\lambda}$ is a
finite subset of $I$), with the natural embedding homomorphisms
$\phi^{\lambda^{\prime}}_{\lambda}:\mathcal{G}_{I_{\lambda}}\rightarrow\mathcal{G}_{I_{\lambda^{\prime}}}$
($I_{\lambda}\subseteq I_{\lambda^{\prime}}$). Also, the index set $\Lambda$
is ordered in a directed way so that for any
$\lambda,\lambda^{\prime}\in\Lambda$, $\lambda\leq\lambda^{\prime}$ if and
only if $I_{\lambda}\subseteq I_{\lambda^{\prime}}$. Then the direct product
$\mathcal{G}_{I}=\prod_{i\in I}G_{i}$ is a direct limit of this directed
system.

###### Proof.

Let $\mathcal{G}=\displaystyle{\lim_{\rightarrow}\mathcal{G}_{I_{\lambda}}}$
be a direct limit of this directed system, with homomorphisms
$\phi_{\lambda}:\mathcal{G}_{I_{\lambda}}\rightarrow\mathcal{G}$. Also, for
any $\lambda\in\Lambda$, consider the embedding homomorphism
$\tau_{\lambda}:\mathcal{G}_{I_{\lambda}}\rightarrow\mathcal{G}_{I}$. Clearly,
for any $\lambda,\lambda^{\prime}\in\Lambda$ with
$\lambda\leq\lambda^{\prime}$,
$\tau_{\lambda^{\prime}}\tau^{\lambda^{\prime}}_{\lambda}=\tau_{\lambda}$.
Now, by universal property of $\mathcal{G}$, there exists a unique
homomorphism $\phi:\mathcal{G}\rightarrow\mathcal{G}_{I}$ such that for any
$\lambda\in\Lambda$, $\phi\phi_{\lambda}=\tau_{\lambda}$. To define the
inverse homomorphism $\tau:\mathcal{G}_{I}\rightarrow\mathcal{G}$, recall that
for any $x=\\{x_{i}\\}_{i\in I}\in\mathcal{G}_{I}$, there exists a finite
subset $I_{\lambda}$ of $I$ that for any $i\in I\backslash I_{\lambda}$,
$x_{i}$ is trivial in $G_{i}$. Hence we can consider $x$ as an element of
$\mathcal{G}_{I_{\lambda}}$ and define $\tau(x)=\phi_{\lambda}(x)$. It is easy
to see that for any $\lambda\in\Lambda$, $\tau\tau_{\lambda}=\phi_{\lambda}$.
Finally, we see that for any $x\in\mathcal{G}_{I}$,
$\phi\tau(x)=\phi\phi_{\lambda}(x)$, for some ${\lambda}\in\Lambda$; and so
$\phi\tau(x)=\tau_{\lambda}(x)=x$. Conversely, the equation
$\tau\phi=id_{\mathcal{G}}$ holds because of the universal property of the
direct limit $\mathcal{G}$. ∎

By the above notations, we conclude that $\prod_{i\in I}G_{i}$, $\prod_{i\in
I}V^{**}(G_{i})$, and $\prod_{i\in I}G_{i}/V^{**}(G_{i})$ are direct limits of
directed systems $\\{\prod_{i\in
I_{\lambda}}G_{i},\phi^{\lambda^{\prime}}_{\lambda},\Lambda\\}$,
$\\{\prod_{i\in
I_{\lambda}}V^{**}(G_{i}),\bar{\phi}^{\lambda^{\prime}}_{\lambda},\Lambda\\}$,
and $\\{\prod_{i\in
I_{\lambda}}G_{i}/V^{**}(G_{i}),\psi^{\lambda^{\prime}}_{\lambda},\Lambda\\}$
respectively, where $\bar{\phi}^{\lambda^{\prime}}_{\lambda}$’s are
restrictions of $\phi^{\lambda^{\prime}}_{\lambda}$’s and
$\psi^{\lambda^{\prime}}_{\lambda}$’s are quotient homomorphisms induced by
$\phi^{\lambda^{\prime}}_{\lambda}$’s.

Now, suppose that $\\{G_{i}\\}_{i\in I}$ is a family of groups in which for
any $G_{i}$ and $G_{j}$ $(i,j\in I)$, ${\mathcal{V}}M({G_{i}\times
G_{j}})\cong{\mathcal{V}}M({G_{i}})\times{\mathcal{V}}M({G_{j}})$. By Theorem
2.3, $\prod_{i\in
I_{\lambda}}(V^{*})^{*}(G_{i})\subseteq(V^{*})^{*}(\prod_{i\in
I_{\lambda}}G_{i})$, for any finite subset $I_{\lambda}$ of $I$. Thus, using
Theorem 2.2, we have the following monomorphism

${\mathcal{V}}M(\prod_{i\in
I_{\lambda}}G_{i})\hookrightarrow{\mathcal{V}}M(\frac{\prod_{i\in
I_{\lambda}}G_{i}}{\prod_{i\in I_{\lambda}}(V^{*})^{*}(G_{i})}).$

By the fact that direct limit of a directed system preserves exactness of a
sequence [8], we obtain the following monomorphism

$\displaystyle{\lim_{\rightarrow}{\mathcal{V}}M(\prod_{i\in
I_{\lambda}}G_{i})}\hookrightarrow\displaystyle{\lim_{\rightarrow}}{\mathcal{V}}M(\frac{\prod_{i\in
I_{\lambda}}G_{i}}{\prod_{i\in I_{\lambda}}(V^{*})^{*}(G_{i})}).$

Using Theorem 2.4, we conclude the monomorphism

${\mathcal{V}}M(\displaystyle{\lim_{\rightarrow}\prod_{i\in
I_{\lambda}}G_{i}})\hookrightarrow{\mathcal{V}}M(\displaystyle{\lim_{\rightarrow}\frac{\prod_{i\in
I_{\lambda}}G_{i}}{\prod_{i\in I_{\lambda}}(V^{*})^{*}(G_{i})})},$

and so we have the monomorphism

${\mathcal{V}}M(\prod_{i\in
I}G_{i})\hookrightarrow{\mathcal{V}}M(\frac{\prod_{i\in I}G_{i}}{\prod_{i\in
I}(V^{*})^{*}(G_{i})}).$

Finally, by Theorem 2.2, we conclude that

${\prod_{i\in I}(V^{*})^{*}(G_{i})}\subseteq{(V^{*})^{*}(\prod_{i\in
I}G_{i})}.$

Using these notes, we deduce the following theorem.

######  Theorem 2.6.

Let $\mathcal{V}$ be a variety, $\\{G_{i}\\}_{i\in I}$ be a family of groups
such that for any $i,j\in I$, ${\mathcal{V}}M({G_{i}\times
G_{j}})\cong{\mathcal{V}}M({G_{i}})\times{\mathcal{V}}M({G_{j}})$. Then
$(V^{*})^{*}(\prod_{i\in I}G_{i})=\prod_{i\in I}(V^{*})^{*}(G_{i})$.
Consequently, $\prod_{i\in I}G_{i}$ is $\mathcal{V}$-capable if and only if
each $G_{i}$ is $\mathcal{V}$-capable.

######  Remark 2.7.

(i) In the above theorem, the sufficient condition

${\mathcal{V}}M({A\times B})\cong{\mathcal{V}}M({A})\times{\mathcal{V}}M({B})$

is not necessary (see Example $2.3(iii)$ of [7]). Also, this condition is
essential and can not be omitted (see Example $2.3(i),(ii)$ of [7]).
(ii) It is known that for varieties of abelian and nilpotent groups, and for
any groups $A$ and $B$, ${\mathcal{V}}M(A\times
B)\cong{\mathcal{V}}M(A)\times{\mathcal{V}}M(B)\times T$, where $T$ is an
abelian group whose elements are tensor products of the elements of $A^{ab}$
and $B^{ab}$ [3], [9]. Hence in these known varieties, the isomorphism
${\mathcal{V}}M({A\times B})\cong{\mathcal{V}}M({A})\times{\mathcal{V}}M({B})$
holds, where both $A^{ab}$ and $B^{ab}$ have finite exponent with
$(exp(A^{ab}),exp(B^{ab}))=1$.

In the following, using the main theorem and the above remark, we deduce some
corollaries which are generalizations of some results of [7] (Remark
$2.4(ii)$, Corollary $2.5$ and Example $2.2$).

######  Corollary 2.8.

Let $\\{G_{i}\\}_{i\in I}$ be a family of groups whose abelianizations have
mutually coprime exponents. Then $\prod_{i\in I}G_{i}$ is capable
($\mathcal{N}_{c}$-capable) if and only if each $G_{i}$ is capable
($\mathcal{N}_{c}$-capable).

######  Corollary 2.9.

Suppose that $\\{G_{i}\\}_{i\in I}$ is a family of groups whose
abelianizations have mutually coprime exponents. If $\prod_{i\in I}G_{i}$ is
nilpotent of class at most $c_{1}$, then it is
$\mathcal{N}_{c_{1},\cdots,c_{s}}$-capable if and only if every $G_{i}$ is
$\mathcal{N}_{c_{1},\cdots,c_{s}}$-capable.

######  Corollary 2.10.

If $\\{G_{i}\\}_{i\in I}$ is a family of perfect groups, then $\prod_{i\in
I}G_{i}$ is $\mathcal{V}$-capable if and only if each $G_{i}$ is
$\mathcal{V}$-capable, where $\mathcal{V}$ may be each of these three
varieties, 1.variety of abelian groups, 2.variety of nilpotent groups,
3.variety of polynilpotent groups.

## References

  * [1] R. Baer, Groups with preassigned central and central quotient groups, Trans. Amer. Math. Soc., (1938), no. 44, 378-412.
  * [2] F. R. Beyl, U. Felgner, P. Schmid, On groups occurring as center factor groups, J. Algebra, (1979), no. 61, 161-177.
  * [3] G. Ellis, On groups with a finite nilpotent upper central quotient, Arch. Math., (1998), no. 70, 89-96.
  * [4] P. Hall, The classification of prime-power groups, J. reine angew. Math., (1940), no. 182, 130-141.
  * [5] M. Hall, Jr., J. K. Senior, The Groups of Order $2^{n}(n\leq 6)$, Macmillan, New York, 1964.
  * [6] G. Karpilovsky, The Schur Multiplier, London Math. Soc. Monographs, New Series 2, Clarendon Press, Oxford University Press, Oxford, 1987.
  * [7] H. Mirebrahimi, B. Mashayekhy, On varietal capability of direct product of groups, J. Adv. Res. Pure Math., to appear.
  * [8] M. R. R. Moghaddam, The Baer-invarient and the direct limit, Mh. Math., (1980), no. 90, 37-43.
  * [9] M. R. R. Moghaddam, The Baer-invarient of a direct product, Arch. Math., (1980), no. 33, 504-511.
  * [10] M. R. R. Moghaddam, S. Keyvanfar, A new notion derived from varieties of groups. Algebra Colloq., (1997), no. 4:1, 1-11.
  * [11] D. J. S. Robinson, A Course in the Theory of Groups, Second Edition, Springer-Verlag, 1996. mer. Math. Soc., Providence, RI, 2010.

Hanieh Mirebrahimi
Department of Pure Mathematics, Center of Excellence in Analysis on Algebraic
Structures, Ferdowsi University of Mashhad, P. O. Box 1159-91775, Mashhad,
Iran.
Email<EMAIL_ADDRESS>
Behrooz Mashayekhy
Department of Pure Mathematics, Center of Excellence in Analysis on Algebraic
Structures, Ferdowsi University of Mashhad, P. O. Box 1159-91775, Mashhad,
Iran.
Email<EMAIL_ADDRESS>


* [30] X. Meng, J. Li, X. Dai, and J. Dou, “Variable neighborhood search for a colored traveling salesman problem,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 19, no. 4, pp. 1018–1026, 2018.
  * [31] P. He and J. Hao, “Iterated two-phase local search for the colored traveling salesmen problem,” _Engineering Applications of Artificial Intelligence_ , vol. 97, p. 104018, 2021.
  * [32] I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio, “Neural combinatorial optimization with reinforcement learning,” in _The 5th International Conference on Learning Representations, ICLR_ , 2017.
  * [33] Y. L. Goh, W. S. Lee, X. Bresson, T. Laurent, and N. Lim, “Combining reinforcement learning and optimal transport for the traveling salesman problem,” _CoRR_ , vol. abs/2203.00903, 2022.
  * [34] M. Cuturi, “Sinkhorn distances: Lightspeed computation of optimal transport,” in _The 27th Annual Conference on Neural Information Processing Systems, NIPS_ , 2013, pp. 2292–2300.
  * [35] R. Zhang, A. Prokhorchuk, and J. Dauwels, “Deep reinforcement learning for traveling salesman problem with time windows and rejections,” in _2020 International Joint Conference on Neural Networks, IJCNN_ , 2020, pp. 1–8.
  * [36] G. Wu, Z. Zhang, H. Liu, and J. Wang, “Solving time-dependent traveling salesman problem with time windows with deep reinforcement learning,” in _2021 IEEE International Conference on Systems, Man, and Cybernetics, SMC_ , 2021, pp. 558–563.
  * [37] F. Liu and G. Zeng, “Study of genetic algorithm with reinforcement learning to solve the TSP,” _Expert Systems with Applications_ , vol. 36, no. 3, pp. 6995–7001, 2009.
  * [38] P. R. de O. da Costa, J. Rhuggenaath, Y. Zhang, and A. Akcay, “Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning,” in _The 12th Asian Conference on Machine Learning, ACML_ , vol. 129, 2020, pp. 465–480.
  * [39] J. Sui, S. Ding, R. Liu, L. Xu, and D. Bu, “Learning 3-opt heuristics for traveling salesman problem via deep reinforcement learning,” in _The 13th Asian Conference on Machine Learning, ACML_ , vol. 157, 2021, pp. 1301–1316.
  * [40] J. Zhao, M. Mao, X. Zhao, and J. Zou, “A hybrid of deep reinforcement learning and local search for the vehicle routing problems,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 22, no. 11, pp. 7208–7218, 2021.
  * [41] M. Held and R. M. Karp, “The traveling-salesman problem and minimum spanning trees: Part II,” _Mathematical Programming_ , vol. 1, no. 1, pp. 6–25, 1971.
  * [42] Y. Dumas, J. Desrosiers, É. Gélinas, and M. M. Solomon, “An optimal algorithm for the traveling salesman problem with time windows,” _Operations Research_ , vol. 43, no. 2, pp. 367–371, 1995.
  * [43] M. Gendreau, A. Hertz, G. Laporte, and M. Stan, “A generalized insertion heuristic for the traveling salesman problem with time windows,” _Operations Research_ , vol. 46, no. 3, pp. 330–335, 1998.
  * [44] X. Dong, W. Dong, and Y. Cai, “Ant colony optimization for coloured travelling salesman problem by multi-task learning,” _IET Intelligent Transport Systems_ , vol. 12, no. 8, pp. 774––782, 2018.
  * [45] X. Dong, Q. Lin, M. Xu, and Y. Cai, “Artificial bee colony algorithm with generating neighbourhood solution for large scale coloured traveling salesman problem,” _IET Intelligent Transport Systems_ , vol. 13, no. 10, pp. 1483––1491, 2019.