# Lower General Position Sets in Graphs

Gabriele Di Stefano a
<EMAIL_ADDRESS>Sandi Klavžar b,c,d
<EMAIL_ADDRESS>Aditi Krishnakumar e
<EMAIL_ADDRESS>James Tuite e
<EMAIL_ADDRESS>Ismael Yero f
<EMAIL_ADDRESS>
###### Abstract

A subset $S$ of vertices of a graph $G$ is a _general position set_ if no
shortest path in $G$ contains three or more vertices of $S$. In this paper, we
generalise a problem of M. Gardner to graph theory by introducing the _lower
general position number_ $\operatorname{gp}^{-}(G)$ of $G$, which is the
number of vertices in a smallest maximal general position set of $G$. We show
that ${\rm gp}^{-}(G)=2$ if and only if $G$ contains a universal line and
determine this number for several classes of graphs, including Kneser graphs
$K(n,2)$, line graphs of complete graphs, and Cartesian and direct products of
two complete graphs. We also prove several realisation results involving the
lower general position number, the general position number and the geodetic
number, and compare it with the lower version of the monophonic position
number. We provide a sharp upper bound on the size of graphs with given lower
general position number. Finally we demonstrate that the decision version of
the lower general position problem is NP-complete.

a Department of Information Engineering, Computer Science and Mathematics,
University of L’Aquila, Italy

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

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

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

e Department of Mathematics and Statistics, Open University, Milton Keynes, UK

f Departamento de Matemáticas, Universidad de Cádiz, Algeciras, Spain

Keywords: general position number, geodetic number, universal line,
computational complexity, Kneser graphs, line graphs

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

##  1 Introduction

The _general position problem_ originated in a puzzle by Dudeney in his book
[16]. It can be stated as follows: what is the largest number of pawns that
can be placed on an $n\times n$ chessboard such that no three pawns lie on a
straight line? This geometrical problem is also known as the _no-three-in-line
problem_. An obvious upper bound is $2n$, which is achieved for $n\leq 46$.
However, for larger $n$ the problem remains open. Erdős showed how to place
$n-o(n)$ pawns on the chessboard with no three in line (his proof is recorded
in the paper [35] by Roth), which was subsequently improved by Hall et al. to
$\frac{3n}{2}-o(n)$ pawns [21]. It is conjectured that the true answer is
$\frac{\pi n}{\sqrt{3}}-o(n)$ in [20] (see [33] for a correction). The problem
has been called “one of the oldest and most extensively studied geometric
questions concerning lattice points” [7].

The general position problem was generalised to the setting of graph theory
independently in [9, 28, 29] as follows.

######  Definition 1.1.

A set $S\subseteq V(G)$ is in _general position_ if no shortest path in $G$
contains three or more vertices of $S$; such a set is a _general position
set_. The _general position number_ $\operatorname{gp}(G)$ of $G$ is the
number of vertices in a largest general position set. The _general position
problem_ asks for a largest general position set in a given graph.

Papers in this very active field of research include [19, 27, 31, 32, 38, 40,
42]. Several variations of the problem have been considered, including using
the Steiner distance instead of the regular graph distance [24], or confining
attention to shortest paths of bounded length [26]. Games involving general
position sets have also been treated in [10] and [25], a dynamic variant of
the problem was considered in [23] and a local version of general position
sets was studied in [37].

The edge version of the general position problem has also been recently
studied in [30]. A related problem is the _monophonic position problem_
obtained by replacing “shortest path” in the general position problem by
“induced path”, see [39]. Another variant of the general position problem is
the _mutual-visibility problem_ that asks for a largest set of vertices $S$,
such that for each pair of vertices in $S$ there is a shortest path connecting
them that does not contain a third vertex of $S$, see [15].

A new slant on this old problem was given by Martin Gardner (the modern day
Dudeney), who asked the following question in his column in Scientific
American: “Instead of asking for the maximum number of counters that can be
put on an order-$n$ board, no three in line, let us ask for the minimum that
can be placed such that adding one more counter on any vacant cell will
produce three in line” [17]. If a greedy algorithm is used to produce a
general position set, then the answer to Gardner’s problem represents the
worst-case output. This problem was treated in [3, 4, 14]. The most recent of
these articles [4] refers to this problem as the _geometric domination
problem_ and gives a lower bound of $\Omega(n^{\frac{2}{3}})$ and an upper
bound of $2\left\lceil\frac{n}{2}\right\rceil$ for an $n\times n$ grid.

In this paper we extend Gardner’s problem to graph theory by asking for the
smallest maximal general position sets, i.e. the smallest general position
sets that cannot be extended without creating three in a line.

######  Definition 1.2.

A general position set $S$ in a graph $G$ is _maximal_ if there is no general
position set of $G$ containing $S$ as a proper subset. The _lower general
position number_ $\operatorname{gp}^{-}(G)$ of $G$ is the number of vertices
in a smallest maximal general position set of $G$, also called a _lower
general position set_.

An example of these concepts in the context of the Petersen graph $P$ can be
seen in Fig. 1. From [29] we know that $\operatorname{gp}(P)=6$; the set of
white vertices in the figure represents a largest general position set, whilst
the grey vertices form a smallest maximal general position set, so that
$\operatorname{gp}^{-}(P)=4$.

Since any vertex of a (non-trivial) graph $G$ is not a maximal general
position set, for any graph $G$ we have:

$2\leq\operatorname{gp}^{-}(G)\leq\operatorname{gp}(G).$ (1)

It is not difficult to see that for any tree $T$ (or, more generally, any
graph with a bridge) we have $\operatorname{gp}^{-}(T)=2$, so it is possible
to have equality with the lower bound in Inequality 1. In Section 2 we will
take a closer look at the graphs $G$ which satisfy
$\operatorname{gp}^{-}(G)=2$. The upper bound in Inequality 1 is also tight,
since any complete graph $K_{n}$ satisfies
$\operatorname{gp}^{-}(K_{n})=n=\operatorname{gp}(K_{n})$.

Figure 1: The Petersen graph with a maximum general position set (white) and a
lower general position set (grey)

We now provide some necessary definitions. All graphs considered in this paper
are finite, undirected, simple and connected. The order and the size of a
graph $G$ will be denoted by $n(G)$ and $m(G)$, respectively. We will write
$u\sim v$ if vertices $u$ and $v$ are adjacent. The subgraph of $G$ induced by
a subset $S\subseteq V(G)$ will be denoted by $G[S]$. The _distance_
$d_{G}(u,v)$ between vertices $u$ and $v$ of a graph $G$ is the length of a
shortest $u,v$-path. The _interval_ $I[u,v]$ of $u$ and $v$ is the set of
vertices that lie on at least one shortest $u,v$-path. The _geodetic closure_
$I[S]$ of a set $S\subseteq V(G)$ is the union $\bigcup_{u,v\in S}I[u,v]$ and
$S$ is _geodetic_ if $I[S]=V(G)$. The _geodetic number_ $\operatorname{g}(G)$
of $G$ is the number of vertices in a smallest geodetic set of $G$, see [8].

In connection with this last parameter, note that a geodetic set $S$ in a
graph $G$ has the property that no vertex can be added to $S$ without creating
three in a line (although there is no guarantee that $S$ is in itself in
general position). Thus, if a geodetic set is in general position, then it is
also a maximal general position set. This may suggest that a graph with a
small geodetic number might also have a small lower general position number.

The _clique number_ $\omega(G)$ is the number of vertices in a largest clique
(i.e. set of mutually adjacent vertices) of $G$, whilst $\omega^{-}(G)$ will
represent the number of vertices in a smallest maximal clique of $G$. A subset
$S\subseteq V(G)$ is an _independent union of cliques_ if each component of
$G[S]$ is a clique; the number of vertices in a largest independent union of
cliques is the _independent union of cliques number_ $\alpha^{\omega}(G)$,
whereas we will denote the number of vertices in a smallest maximal
independent union of at least two cliques by $\alpha^{\omega^{-}}(G)$ (for
convenience we do not count a clique as an independent union of cliques here).
The join of graphs $G$ and $H$ will be denoted by $G\vee H$. We also adopt the
convention that $[n]$ stands for the set $\\{1,\ldots,n\\}$.

The plan of this paper is as follows. In Section 2 we consider graphs having
lower general position number equal to two. In particular, we show that these
graphs coincide with the graphs that contain a universal line. In Section 3 we
prove several realisation results involving the lower general position number,
the general position number and the geodetic number. We also give an upper
bound on the size of a graph with given lower general position number and
characterise the graphs which attain equality. In Section 4 we prove that the
decision version of the lower general position problem is NP-complete. In
Section 5 we determine the lower general position number of the Kneser graphs
$K(n,2)$, the line graphs of complete graphs, and the Cartesian and direct
products of two complete graphs. In Section 6 we relate the lower general
position number to the lower monophonic position number. Finally in Section 7
we suggest several avenues for further research.

##  2 Graphs $G$ with $\operatorname{gp}^{-}(G)=2$

Based on the trivial lower bound in Inequality (1), it is natural (as with
many other graph parameters) to consider characterising the family of graphs
achieving equality. However, as we now show, this appears to be a very
challenging problem. To see this, let us first invoke the following concept
from the theory of metric spaces. Let $M=(X,d_{M})$ be an arbitrary metric
space and $x,y\in X$. Then the line ${\cal L}_{M}(x,y)$ induced by $x$ and $y$
is the following set of points from $M$:

$\\{z\in X:\ d_{M}(x,y)=d_{M}(x,z)+d_{M}(z,y)\ {\rm or}\
d_{M}(x,y)=|d_{M}(x,z)-d_{M}(z,y)|\\}\,.$

The line ${\cal L}_{M}(x,y)$ is universal if it contains the whole set $X$.
Considering a graph $G$ as a metric space, these definitions transfer directly
to $G$.

Let $\ell(M)$ denote the number of distinct lines in $M$. Chen and Chvátal
[12] conjectured that if $\ell(M)<|X|$, then $M$ has a universal line. The
problem remains open; a summary of what is known about it up to 2018 can be
found in [13]. For the case of graphs, the Chen-Chvátal Conjecture has been
verified in particular for a certain class of graphs containing both chordal
graphs and distance-hereditary graphs [2], for $(q,q-4)$-graphs [36], and for
graphs with no induced house or induced cycle of length at least $5$ [1].

Closely related to the Chen-Chvátal Conjecture is an open problem [34, Problem
1.2] to determine necessary and sufficient conditions for a graph to have a
universal line. It turns out that the existence of a universal line in $G$ is
equivalent to $\operatorname{gp}^{-}(G)=2$.

######  Proposition 2.1.

Let $G$ be a graph. Then $\operatorname{gp}^{-}(G)=2$ if and only if $G$ has a
universal line.

###### Proof.

Suppose first that $\operatorname{gp}^{-}(G)=2$ and let $\\{u,v\\}$ be a
maximal general position set of $G$. Then for every vertex $w\in
V(G)\setminus\\{u,v\\}$, the triple of vertices $u,v,w$ lies on a shortest
path. That is, one of the following equations applies:
$d_{G}(u,v)=d_{G}(u,w)+d_{G}(w,v)$, $d_{G}(u,w)=d_{G}(u,v)+d_{G}(v,w)$ or
$d_{G}(v,w)=d_{G}(v,u)+d_{G}(u,w)$. This in turn implies that ${\cal
L}_{G}(u,v)=V(G)$, hence $G$ has a universal line. Conversely, if $G$ has a
universal line ${\cal L}_{G}(u,v)$, then by the same argument, $\\{u,v\\}$ is
a maximal general position set of $G$. ∎

Therefore the problem of the existence of universal lines considered in [34]
is equivalent to efficiently characterising connected graphs with lower
general position number $2$. Simple sufficient conditions for
$\operatorname{gp}^{-}(G)=2$ to hold are: (i) having a bridge; (ii)
$\operatorname{g}(G)=2$; (iii) being bipartite, see [6]. If $G$ is a block
graph, then $\operatorname{gp}^{-}(G)=2$ if and only if $K_{2}$ is a block of
$G$, see [34, Corollary 3.4]. In the same paper, Rodríguez-Velázquez
characterised Cartesian product graphs having a universal line. (For the
definition of the Cartesian product and its properties we refer to the book
[22].) In view of Proposition 2.1 his result can be reformulated as follows.

######  Theorem 2.2.

[34, Theorem 4.1] Let $G$ and $H$ be non-trivial, connected graphs. Then
$\operatorname{gp}^{-}(G\operatorname{\,\square\,}H)=2$ if and only if one of
the following conditions holds.

  1. (i)

$G$ or $H$ has a maximal general position set consisting of two adjacent
vertices.

  2. (ii)

$\operatorname{g}(G)=2$ and $\operatorname{g}(H)=2$.

Other graphs with lower general position number $2$ are: (i) graphs obtained
from any graph $G$ such that $\operatorname{gp}^{-}(G)=2$ and any graph $H$ by
fixing a vertex $u\in V(G)$ and joining it to at least one vertex in every
component of $H$ and (ii) any complete multipartite graph with a part of
cardinality $2$, cf. Proposition 2.3(ii).

To conclude this section we determine the cycles and complete multipartite
graphs that have lower general position number equal to $2$.

######  Proposition 2.3.

(i) If $n\geq 3$, then

$\operatorname{gp}^{-}(C_{n})=\begin{cases}2;&\text{$n$ even, }\\\
3;&\text{$n$ odd.}\end{cases}$

(ii) If $t\geq 2$ and $r_{1}\geq\dots\geq r_{t}\geq 2$, then

$\operatorname{gp}^{-}(K_{r_{1},\dots,r_{t}})=\min\\{t,r_{t}\\}.$

###### Proof.

(i) If $n$ is even, then $C_{n}$ is bipartite and hence
$\operatorname{gp}^{-}(C_{n})=2$. Now let $n$ be odd. Identify the vertex set
of $C_{n}$ with $\mathbb{Z}_{n}$ in the natural manner. As
$\operatorname{gp}(C_{n})=3$ for $n=3$ and $n\geq 5$, we have
$2\leq\operatorname{gp}^{-}(G)\leq 3$ and the result will follow if we show
that any set of two vertices of $C_{n}$ can be extended to form a general
position set of three vertices. Without loss of generality, let this set be
$S=\\{0,i\\}$, where $i<n-i$. Then it is easily checked that if $i$ is odd,
then the set $\\{0,i,\frac{n+i}{2}\\}$ is in general position and if $i$ is
even, then $\\{0,i,\frac{n+i-1}{2}\\}$ is in general position.

(ii) Each of the partite sets of the complete multipartite graph is a maximal
general position set, so it follows that
$\operatorname{gp}^{-}(K_{r_{1},\dots,r_{t}})\leq r_{t}$. Suppose that $S$ is
a maximal general position set containing vertices from different partite
sets. Then $S$ can contain at most one vertex from each of the $t$ parts;
hence $S$ induces a clique and by maximality $S$ must contain $t$ vertices,
one from each part. Hence
$\operatorname{gp}^{-}(K_{r_{1},\dots,r_{t}})=\min\\{t,r_{t}\\}$. ∎

##  3 Realisation results

In this section we explore the relationship between the lower general position
number, the general position number and the geodetic number. We begin by
proving a realisation result for the lower general position number and
geodetic number of a graph. Recall that it was suggested in Section 1 that a
graph with small geodetic number might be expected to have a small maximal
geodetic set; although this intuition turns out to be true for graphs with
geodetic number two or three, we now show that in general this is not the
case. To this end, we begin by determining the lower general position number
of the join of two graphs. Recall our convention that when finding the
smallest number of vertices in a maximal independent union of cliques
$\alpha^{\omega^{-}}(G)$ we do not allow unions consisting of one clique.

######  Lemma 3.1.

If $G$ and $H$ are graphs, then

$\operatorname{gp}^{-}(G\vee
H)=\min\\{\omega^{-}(G)+\omega^{-}(H),\alpha^{\omega^{-}}(G),\alpha^{\omega^{-}}(H)\\}.$

###### Proof.

Let $S$ be a smallest maximal general position set of $G\vee H$. Suppose that
$S$ contains vertices of both $G$ and $H$; then both $S\cap V(G)$ and $S\cap
V(H)$ must induce cliques, since if $u,u^{\prime}\in V(G),v\in V(H)$ and
$u\not\sim u^{\prime}$, then $u,v,u^{\prime}$ would be a path of length two
contained in $S$. Conversely, any such set is a clique in $G\vee H$ that
cannot be extended to a larger general position set of $G\vee H$. Hence
$|S|\leq\omega^{-}(G)+\omega^{-}(H)$.

Suppose now that $S\cap V(H)=\emptyset$ (the case $S\cap V(G)=\emptyset$ is
symmetrical). As all vertices of $V(G)$ are at distance at most two in $G\vee
H$, $S$ is in general position in $G\vee H$ if and only if it is an
independent union of cliques. However, $S$ will only be a maximal general
position set if it is a maximal independent union of at least two cliques in
$G$ (otherwise we could extend $S$ by adding any vertex from $H$). Thus
$\operatorname{gp}^{-}(G\vee H)\leq\alpha^{\omega^{-}}(G)$.

The result now follows upon taking the minimum amongst these forms of maximal
general position sets in $G\vee H$. ∎

We also use the following known lemma in our comparison of the geodetic number
and lower general position number. Recall that a vertex of a graph is
simplicial if its neighbours induce a complete subgraph.

######  Lemma 3.2.

[11, Theorem A] Every geodetic set of $G$ contains all simplicial vertices of
$G$.

######  Theorem 3.3.

Let $a\geq 2$ and $b\geq 2$ be integers. Then there is a graph $G$ with
$\operatorname{gp}^{-}(G)=a$ and $\operatorname{g}(G)=b$ if and only if $2\leq
a\leq b$ or $4\leq b\leq a$.

###### Proof.

If $a\leq b$, then by Lemma 3.1 the graph $bK_{1}\vee K_{a-1}$ has
$\operatorname{gp}^{-}(bK_{1}\vee K_{a-1})=a$. Moreover, by Lemma 3.2, any
geodetic set of $bK_{1}\vee K_{a-1}$ contains the $b$ vertices of $bK_{1}$;
since this set is geodetic, we obtain $\operatorname{g}(bK_{1}\vee
K_{a-1})=b$. We can thus assume in the remainder of the proof that $b<a$.

If $b=\operatorname{g}(G)=2$, then $G$ has a universal line and hence
$\operatorname{gp}^{-}(G)=2$ by Proposition 2.1. Suppose that
$\operatorname{g}(G)=3$ and let $S=\\{x,y,z\\}$ be a smallest geodetic set, so
that $I[x,y]\cup I[x,z]\cup I[y,z]=V(G)$. Suppose that $S$ is not in general
position, say $y$ lies on a shortest $x,z$-path $P$ in $G$. Then we have
$I[x,y]\cup I[y,z]\subseteq I[x,z]$, so that $\\{x,z\\}$ would be a geodetic
set, a contradiction, implying that $G$ would have a maximal general position
set of order at most three. Thus we cannot have $b<a$ if $b\in\\{2,3\\}$.

Now we deal with the remaining case $4\leq b<a$. Let $X_{1},X_{2},Y$ be
cliques of orders $|X_{1}|=|X_{2}|=a-2>2$ and $|Y|=b-3\geq 1$. Let $x_{1}\in
X_{1}$ and $x_{2}\in X_{2}$ be fixed. We form a graph $H(a,b)$ from these
cliques as follows. Add all possible edges between $X_{1}$ and $Y$, join
$x_{1}$ to every vertex of $X_{2}$ and $x_{2}$ to every vertex of $X_{1}$. Add
a new vertex $w$ and join it to every vertex of $X_{2}$. Finally we construct
$G(a,b)$ by adding a vertex $z$ to $H(a,b)$ and joining it to every other
vertex, i.e. $G(a,b)=H(a,b)\vee K_{1}$. An example is given in Fig. 2.

$X_{2}$$x_{2}$$X_{1}$$x_{1}$$Y$$z$$w$ Figure 2: The graph $G(7,6)$.

Let $R$ be a smallest geodetic set of $G(a,b)$. Now each vertex in
$Y\cup\\{w\\}$ is a simplicial vertex, so Lemma 3.2 yields
$Y\cup\\{w\\}\subseteq R$, and hence $\operatorname{g}(G(a,b))\geq b-2$.
Furthermore it is easily checked that $Y\cup\\{x_{1},x_{2},w\\}$ is a geodetic
set containing $b$ vertices, whilst adding a single vertex to $Y\cup\\{w\\}$
does not yield a geodetic set; it follows that $\operatorname{g}(G(a,b))=b$.

For the lower general position number, Lemma 3.1 implies that
$\operatorname{gp}^{-}(G(a,b))=\min\\{\omega^{-}(H(a,b))+1,\alpha^{\omega^{-}}(H(a,b))\\}$.
The set $X_{2}\cup\\{w\\}$ induces a smallest maximal clique of $H(a,b)$,
hence $\omega^{-}(H(a,b))+1=a$. To calculate $\alpha^{\omega^{-}}(H(a,b))$,
let $S^{\prime}$ be a smallest maximal independent union of at least two
cliques. Suppose that $x_{1}\in S^{\prime}$. Observe that in this case
$S^{\prime}$ cannot contain vertices from both $(X_{1}-\\{x_{1}\\})\cup
Y\cup\\{w\\}$ and $X_{2}$. Hence, if $S^{\prime}$ contains a vertex of
$X_{2}$, then $S^{\prime}$ would be a clique, a contradiction, so it follows
that $S^{\prime}\subseteq X_{1}\cup Y\cup\\{w\\}$; as $X_{1}\cup Y\cup\\{w\\}$
is an independent union of cliques, we would have $S^{\prime}=X_{1}\cup
Y\cup\\{w\\}$ and $|S^{\prime}|=a+b-4\geq a$. Thus we can assume that
$x_{1}\not\in S^{\prime}$ and similarly $x_{2}\not\in S^{\prime}$.

Thus $S^{\prime}\subseteq(X_{1}\cup X_{2}\cup
Y\cup\\{w\\})-\\{x_{1},x_{2}\\}$, from which it follows that
$S^{\prime}=(X_{1}\cup X_{2}\cup Y\cup\\{w\\})-\\{x_{1},x_{2}\\}$ and
$|S^{\prime}|=2a+b-8>a$. Hence $\alpha^{\omega^{-}}(H(a,b))\geq a$ and
$\operatorname{gp}^{-}(G(a,b))=a$. ∎

We next focus on the relationship between the lower general position number
and the classical general position number. By Proposition 2.3 (ii), for any
$2\leq a\leq b$ the complete multipartite graph with one part of cardinality
$b$ and $a-1$ parts of cardinality $a$ has $\operatorname{gp}^{-}(G)=a$,
$\operatorname{gp}(G)=b$ and order $b+(a-1)a$. Also the graph $bK_{1}\vee
K_{a-1}$ from the proof of Theorem 3.3 has $\operatorname{gp}^{-}(bK_{1}\vee
K_{a-1})=a$ and $\operatorname{gp}(bK_{1}\vee K_{a-1})=b$, but a smaller order
$b+a-1$. For $a=b$, trivially $K_{a}$ is the smallest possible such graph. We
next show that for $2\leq a<b$ a smaller graph that fulfills the same
conditions can be constructed.

######  Theorem 3.4.

For any two integers $2\leq a<b$ there is a graph $G$ with
$\operatorname{gp}^{-}(G)=a$, $\operatorname{gp}(G)=b$, and
$n(G)=b+\max\\{1,a-\left\lfloor\frac{b}{2}\right\rfloor\\}$.

###### Proof.

Let $G$ be the join of $K_{c}\cup K_{b-a+c}$ with $K_{a-c}$. Choose $c$ such
that $a\leq b-a+2c\leq b$; then $\operatorname{gp}^{-}(G)=a$ and
$\operatorname{gp}(G)=b$. The smallest possible choice of $c$ is
$\max\\{1,a-\left\lfloor\frac{b}{2}\right\rfloor\\}$. ∎

Finding the smallest graph with $\operatorname{gp}^{-}(G)=a$ and
$\operatorname{gp}(G)=b$ remains an open problem. To conclude this section we
prove the following bound on the size of a graph with given lower general
position number.

######  Theorem 3.5.

If $G$ is a graph with $\operatorname{gp}^{-}(G)=k\geq 2$ and $n(G)\geq 2k-1$,
then

$m(G)\leq\binom{n}{2}-k+1.$

Moreover, the unique graph with order $n(G)$ that meets this bound is formed
from a clique $K_{n(G)}$ by deleting $k-1$ edges adjacent to a fixed vertex.

###### Proof.

Let $n\geq 2k-1$ and take a clique $K_{n}$. Choose a set $S$ of $k$ vertices
of $K_{n}$ and for some vertex $u\in S$ delete all edges between $u$ and
$S-\\{u\\}$ to form the graph $G(k)$. We claim that
$\operatorname{gp}^{-}(G(k))=k$. Let $S^{\prime}$ be an arbitrary maximal
general position set of $G(k)$. If $u\not\in S^{\prime}$, then $S^{\prime}$
must be a clique with order $n-1\geq k$, so suppose that $u\in S^{\prime}$. If
$(S-\\{u\\})\cap S^{\prime}=\emptyset$, then $S^{\prime}$ is the clique
induced by $V(G(k))\setminus(S-\\{u\\})$, which contains $n-k+1\geq k$
vertices. If $S^{\prime}$ contains a vertex $v$ of $S-\\{u\\}$, then
$S^{\prime}\cap V(G(k)-S)=\emptyset$, as any vertex $w\in V(G(k)-S)$ is
contained in a shortest path $u,w,v$. Hence, the set $S$ is clearly a maximal
general position set, so it follows that $\operatorname{gp}^{-}(G(k))=k$.

In fact we can show that this is the only graph with size $\binom{n}{2}-k+1$
that has lower general position number $k$. Assume that $G$ is any such graph
and let $M$ be the set of $k-1$ edges deleted from $K_{n}$ to obtain $G$, i.e.
$G=K_{n}-M$. Let $H$ be the subgraph of $K_{n}$ induced by $M$. Also, let $K$
be the set of vertices incident to the edges of $M$. Observe that $|K|\leq
2k-2$. If $H$ is connected, then $|K|\leq k$, and if $H$ is not connected,
then there is a component of $H$ with order at most $k-1$; in either case, let
$H^{\prime}$ be a component of $H$ with minimum order. Let $u$ and $v$ be two
vertices of $H^{\prime}$, so that $u$ and $v$ are non-adjacent in $G$.

Let $S$ be a maximal general position set of $G$ containing $\\{u,v\\}$. $S$
cannot contain any vertex outside $H^{\prime}$, so $H$ must be connected, for
otherwise we have exhibited a maximal general position set of $G$ of order at
most $k-1$. As $\operatorname{gp}^{-}(G)=k$ and $|K|\leq k$, we must have that
$|K|=k$, $S=K$ and $H$ is a tree. If the diameter of $H$ is at least three,
then $H$ would contain a geodesic $u_{0},u_{1},u_{2},u_{3}$, so that
$u_{0},u_{3},u_{1}$ would be a shortest path in $G$ contained in $S$, which is
impossible. We conclude that $H$ must be a star and $G\cong G(k)$.

Suppose now that there is a graph $G$ with $m(G)\geq\binom{n}{2}-k+2$ and
$\operatorname{gp}^{-}(G)=k$. Hence $G$ can be formed by deleting a set $A$ of
at most $k-2$ edges from $K_{n}$. Let $u\sim v$ be any edge of $A$. Let
$A_{1}$ be the set of edges of $A$ incident with $u$ (apart from $u\sim v$)
and $A_{2}$ be the set of edges of $A$ incident with $v$ (again apart from
$u\sim v$). Let $B_{1}$ be the set of endvertices of the edges in $A_{1}$
apart from $u$, and let $B_{2}$ be the set of endvertices of the edges of
$A_{2}$ apart from $v$. There can be overlap between the sets $B_{1}$ and
$B_{2}$, but as we have deleted at most $k-2$ edges we have $|B_{1}\cup
B_{2}\cup\\{u,v\\}|\leq k-1$. Let $S^{\prime}$ be a maximal general position
set of $G$ containing the set $\\{u,v\\}$. $S^{\prime}$ cannot contain any
vertex of $V(G)-(B_{1}\cup B_{2}\cup\\{u,v\\})$ and so $S^{\prime}\subseteq
B_{1}\cup B_{2}\cup\\{u,v\\}$; this shows that $G$ contains a maximal general
position set containing at most $k-1$ vertices, a contradiction. ∎

##  4 Computational complexity

In Section 2 we have seen that $\operatorname{gp}^{-}(G)=2$ if and only if $G$
has a universal line. The problem of characterising graphs that have universal
lines is difficult and was extensively investigated in [34]. In this section
we complement these investigations by proving that the lower general position
problem is NP-complete. To this end, we formally define the decision version
of the problem:

######  Definition 4.1.

Lower General Position
Instance: A graph $G$, a positive integer $k\leq n(G)$.
Question: Is there a lower general position set $S$ for $G$ such that $|S|\leq
k$?

The problem is hard to solve, as shown by the following result.

######  Theorem 4.2.

The Lower General Position problem is NP-complete.

###### Proof.

Let us observe that Lower General Position is in NP since, given a set of
vertices $S$, it can be tested in polynomial time if (1) $S$ is in general
position, (2) if it is maximal and (3) if its cardinality is less than a given
integer.

We prove that Independent Dominating Set polynomially reduces to Lower general
position. Recalling that a dominating set of a graph $G$ is a subset
$V^{\prime}$ of $V(G)$ such that for all $u\in V(G)\setminus V^{\prime}$ there
is a $v\in V^{\prime}$ such that $uv\in E(G)$, we provide a formal definition
of the decision version of the problem:

> An instance of Independent Dominating Set is given by a graph $G$ and a
> positive integer $k\leq n(G)$. The Independent Dominating Set problem asks
> whether $G$ contains a dominating set $K\subseteq V(G)$, of cardinality $k$
> or less, which is also independent.

The NP-completeness of Independent Dominating Set is reported in [18]. We
polynomially transform an instance $(G,k)$ of Independent Dominating Set to an
instance $(G^{\prime},k^{\prime})$ of Lower General Position. In particular,
given $(G,k)$ we must construct a graph $G^{\prime}$ and a positive integer
$k^{\prime}$ such that $G$ has an independent dominating set of cardinality
$k$ or less if and only if $G^{\prime}$ has a lower general position set of
cardinality $k^{\prime}$ or less.

Given an instance $(G,k)$, the graph $G^{\prime}$ is built as follows:

$G^{\prime}=(\overline{G}\cup K_{n(G)+1})\vee K_{1}$

The graph $G^{\prime}$ is thus the join of graphs
$G^{\prime\prime}=\overline{G}\cup K_{n(G)+1}$ and $K_{1}$, where
$G^{\prime\prime}$ is the disjoint union of the complement of $G$ and a
complete graph with $n(G)+1$ vertices. Then the construction of $G^{\prime}$
can be achieved in polynomial time. As for $k^{\prime}$, we set
$k^{\prime}=k+1$.

We have to show that an instance $(G,k)$ of Independent Dominating Set has a
positive answer if and only if $(G^{\prime},k^{\prime})$, the corresponding
instance of Lower General Position, has a positive answer.

By Lemma 3.1, the lower general position number of $G^{\prime}$ is given by

$\operatorname{gp}^{-}(G^{\prime})=\min\\{\omega^{-}(\overline{G}\cup
K_{n(G)+1})+\omega^{-}(K_{1}),\alpha^{\omega^{-}}(\overline{G}\cup
K_{n(G)+1}),\alpha^{\omega^{-}}(K_{1})\\}.$

Considering that $\omega^{-}(K_{1})=1$, that
$\alpha^{\omega^{-}}(\overline{G}\cup
K_{n(G)+1})\geq\omega^{-}(\overline{G}\cup K_{n(G)+1})+1$ and that
$\alpha^{\omega^{-}}(K_{1})$ is not defined, we have that

$\operatorname{gp}^{-}(G^{\prime})=\omega^{-}(\overline{G}\cup
K_{n(G)+1})+1=\omega^{-}(\overline{G})+1.$ (2)

Moreover, observe that a smallest maximal clique in a given graph is an
independent dominating set in the complement graph. Indeed, a clique is an
independent set in the complement graph and, as the clique is maximal, any
vertex not in the independent set of the complement graph must be adjacent to
a vertex of the independent set, so the independent set is also dominating.

Assume that the instance $(G,k)$ of Independent Dominating Set has a positive
answer. Then in $\overline{G}$ there is a maximal clique having cardinality at
most $k$. Since $k\leq n(G)$, then $\omega^{-}(\overline{G}\cup
K_{n(G)+1})\leq k$ and hence by (2),
$\operatorname{gp}^{-}(G^{\prime})=\omega^{-}(\overline{G}\cup
K_{n(G)+1})+1\leq k+1=k^{\prime}$, which in turn means that
$(G^{\prime},k^{\prime})$, the instance of Lower General Position, has a
positive answer.

Assume now that there is a maximal general position set $S$ in $G^{\prime}$
with cardinality $k^{\prime}$ or less, that is $|S|\leq k^{\prime}$. By (2),
if $S$ contains a vertex in $K_{n(G)+1}$, then, as $|S|$ is maximal, it must
contain all the vertices in $K_{n(G)+1}$ and at least one vertex in
$\overline{G}\vee K_{1}$. So the cardinality of $S$ is at least $n(G)+2\geq
k^{\prime}+1$, a contradiction. Thus $S$ does not contain vertices in
$K_{n(G)+1}$. It now follows from Lemma 3.1 that $S$ consists of the vertex of
$K_{1}$ and a smallest maximal clique in $\overline{G}$, implying that there
exists an independent dominating set in $G$ of cardinality $|S|-1\leq k$. ∎

##  5 Lower general position number of some families

In this section we determine the lower general position number of the Kneser
graphs $K(n,2)$, the line graphs of complete graphs, and the Cartesian and
direct products of two complete graphs.

Recall that the Kneser graph $K(n,2)$ is the graph with vertex set consisting
of all subsets of cardinality two (or $2$-sets for short) of the set $[n]$,
with an edge between two such subsets if and only if they are disjoint.

######  Theorem 5.1.

If $n\geq 3$, then

$\operatorname{gp}^{-}(K(n,2))=\begin{cases}3;&n\in\\{3,6,7\\},\\\
4;&n\in\\{5,8,9\\},\\\ 5;&n\in\\{10,11\\},\\\ 6;&\mbox{\em
otherwise}.\end{cases}$

###### Proof.

The result is trivial for $n=3,4$. The case $n=5$ is the Petersen graph. Hence
we can assume that $n\geq 6$. We divide our argument into three cases
depending on the structure of the general position set. By the result of [5,
Theorem 3.1], any general position set is either a clique or an independent
union of cliques (with a couple of additional technical properties). Let $K$
be any maximal general position set of $K(n,2)$.

Case 1: The subgraph induced by $K$ contains a clique $W$ of order at least
$3$.
Suppose in this case that the subgraph induced by $K$ contains a component
$W^{\prime}$ apart from $W$ and let $\\{a,b\\}$ be a ($2$-set) vertex of
$W^{\prime}$. Without loss of generality, let three vertices of $W$ be
$\\{1,2\\}$, $\\{3,4\\}$ and $\\{5,6\\}$. Then any $2$-set $\\{a,b\\}$ being a
vertex of $W^{\prime}$, must have a non-empty intersection with each of these
$2$-sets $\\{1,2\\}$, $\\{3,4\\}$ and $\\{5,6\\}$, which is impossible. Thus
$K$ consists of a single clique $W$, which is maximal if and only if it
contains $\left\lfloor\frac{n}{2}\right\rfloor$ $2$-sets. Hence in this case
the maximal general position sets have order
$\left\lfloor\frac{n}{2}\right\rfloor$.

Case 2: $K$ is an independent set.
As $K(n,2)$ has diameter two, any independent set is in general position. By
the Erdős-Ko-Rado Theorem, the independence number of $K(n,2)$ is $n-1$. Let
$\\{1,2\\}$ be a ($2$-set) vertex of $K$. Any set containing only vertices of
the form $\\{1,i\\}$ is independent (similarly for a set containing only
vertices of the form $\\{2,i\\}$), but the only maximal such set has
cardinality $n-1$, as given by the Erdős-Ko-Rado Theorem, which is greater
than the maximal general position sets considered in Case 1 (unless $n=5$, in
which case $K(5,2)$ is triangle-free and an independent set of order 4 is best
possible). The only other maximal independent sets of $K(n,2)$ have the
structure $\\{\\{1,2\\},\\{1,3\\},\\{2,3\\}\\}$. However, this is not a
maximal general position set, as the $2$-set $\\{1,4\\}$ can be added to make
a larger general position set.

Case 3: $G[K]$ has a component isomorphic to $K_{2}$.
Without loss of generality, assume that the clique in question is
$\\{\\{1,2\\},\\{3,4\\}\\}$. Then any other vertex of $K$ must be a subset of
$[4]$. The set of $6$ subsets of cardinality $2$ of $[4]$ does form a maximal
general position set isomorphic to $3K_{2}$. In this case the order of the
maximal general position set is thus 6; this is a smallest possible maximal
general position set for $n\geq 12$. ∎

We continue with the line graphs of complete graphs, denoted by $L(K_{n})$.

######  Theorem 5.2.

If $n\geq 2$, then

$\operatorname{gp}^{-}(L(K_{n}))=\left\\{\begin{array}[]{lr}\frac{n}{2};&n\
{\rm even},\\\\[4.26773pt] \frac{n+3}{2};&n\ {\rm odd.}\end{array}\right.$

###### Proof.

The result is easily verified for $n\leq 4$, so we assume that $n\geq 5$. Let
$S$ be a lower general position set of $L(K_{n})$. It is shown in [19] that
the vertices of a maximal general position set of $L(K_{n})$ correspond to
edges in $K_{n}$ that induce a disjoint union of triangles and stars
containing either one or at least three edges (since any star with two edges
can be completed to a triangle). Let $r$ be the number of stars in $S$.
Observe that if $n$ is even, then a perfect matching in $K_{n}$ is a maximal
general position set of $L(K_{n})$, whilst if $n$ is odd the disjoint union of
a triangle and a matching of cardinality $\frac{n-3}{2}$ is a maximal general
position set of $L(K_{n})$. This shows that
$\operatorname{gp}^{-}(L(K_{n}))\leq\frac{n}{2}$ if $n$ is even and
$\operatorname{gp}^{-}(L(K_{n}))\leq\frac{n+3}{2}$ if $n$ is odd.

Suppose that $S$ does not contain any stars of $K_{n}$. Then either $n\equiv
0\pmod{3}$ and $S$ consists entirely of triangles, in which case $|S|=n$, or
else $n\equiv 1\pmod{3}$ and $S$ corresponds to a union of $\frac{n-1}{3}$
triangles and one isolated vertex, in which case $|S|=n-1$. In either case,
$|S|$ is no smaller than the claimed bounds. Hence we may assume that $S$
contains at least one star.

Suppose that there is a vertex of $K_{n}$ that is not covered by an edge of
$S$; since this vertex could be joined to the centre of a star to form a
larger general position set, this would contradict the maximality of $S$. It
follows that every vertex of $K_{n}$ is incident with an edge in $S$ and hence
$|S|=n-r$. If $n$ is even, it follows that $r\leq\frac{n}{2}$, so that
$|S|\geq\frac{n}{2}$. Now suppose that $n$ is odd. If $S$ contains no
triangles, then there must be a star in $S$ on an odd number of vertices of
$K_{n}$; by the preceding discussion, such a star must be incident to at least
five vertices of $K_{n}$, so that $S$ can contain at most
$1+\frac{n-5}{2}=\frac{n-3}{2}$ stars, so that $|S|\geq\frac{n+3}{2}$. Thus we
can assume that $S$ contains a triangle, in which case we again have
$r\leq\frac{n-3}{2}$. ∎

We now consider the Cartesian product of two complete graphs $K_{r}$ and
$K_{s}$ with $r,s\geq 2$, also known as rook graphs.

######  Theorem 5.3.

If $r,s\geq 2$, then

$\operatorname{gp}^{-}(K_{r}\operatorname{\,\square\,}K_{s})=\min\\{r,s\\}.$

###### Proof.

Since the vertices of any copy of $K_{r}$ or $K_{s}$ in
$K_{r}\operatorname{\,\square\,}K_{s}$ form a maximal general position set,
trivially
$\operatorname{gp}^{-}(K_{r}\operatorname{\,\square\,}K_{s})\leq\min\\{r,s\\}$.
Now, assume that there is a maximal general position set $S$ of
$K_{r}\operatorname{\,\square\,}K_{s}$ of cardinality smaller than
$\min\\{r,s\\}$. First note that by maximality $S$ cannot be a proper subset
of the vertex set of any copy of $K_{r}$ or of $K_{s}$. Also, there must exist
a copy of $K_{r}$, say $K_{r}^{(i)}$, and a copy of $K_{s}$, say
${}^{(j)}K_{s}$, which do not contain any vertex of $S$. This immediately
allows us to observe that, independently of the structure of $S$, the unique
vertex of $K_{r}\operatorname{\,\square\,}K_{s}$ belonging to both copies
$K_{r}^{(i)}$ and ${}^{(j)}K_{s}$, together with the set $S$ would also form a
general position set of $K_{r}\operatorname{\,\square\,}K_{s}$. Therefore, $S$
is not maximal, which leads to the desired equality. ∎

Theorem 5.3 should be compared with [19, Theorem 3.2], which asserts that if
$r,s\geq 2$, then
$\operatorname{gp}(K_{r}\operatorname{\,\square\,}K_{s})=r+s-2$.

Continuing the theme of products of complete graphs, the direct product is
also of interest. Given two graphs $G$ and $H$, the direct product of $G$ and
$H$ is the graph $G\times H$ whose vertex set is $V(G)\times V(G)$ and two
vertices $(g,h),(g^{\prime},h^{\prime})\in V(G\times H)$ are adjacent in
$G\times H$ if and only if $gg^{\prime}\in E(G)$ and $hh^{\prime}\in E(H)$.
For any $g\in V(G)$ we call the subgraph of $G\times H$ induced by
$\\{g\\}\times H$ a _$H$ -layer_ of $G\times H$ (and similarly if $h\in V(H)$
the subgraph induced by $G\times\\{h\\}$ is a _$G$ -layer_). Note that, unlike
the case of Cartesian products, a $G$-layer will be isomorphic to $G$ only if
$G$ is an empty graph.

######  Theorem 5.4.

If $r,s\geq 2$ with $(r,s)\neq(2,2)$, then

$\operatorname{gp}^{-}(K_{r}\times K_{s})=\min\\{r,s,4\\}.$

###### Proof.

We can assume without loss of generality that $2\leq r\leq s$ and $s\geq 3$. A
subset $W$ of $V(K_{r}\times K_{s})$ induces a clique if and only if all
vertices of $W$ lie in distinct layers of $K_{r}\times K_{s}$, whereas a
subset $A\subseteq V(K_{r}\times K_{s})$ is independent if and only if it lies
within a single layer.

We show first that any maximum clique $W$ is a maximal general position set.
Let $(x,y)\in V(K_{r}\times K_{s})\setminus W$; we must show that
$W\cup\\{(x,y)\\}$ is not in general position. If $r\geq 3$, then $W$ contains
vertices $(x,j_{1})$ and $(i_{2},j_{2})$ such that $i_{2}\neq x$ and
$j_{2}\neq y$; then the vertices $(x,y),(i_{2},j_{2}),(x,j_{1})$ induce a
shortest path and $(x,y)$ cannot be added to $W$ to make a larger general
position set. If $r=2$, let $W=\\{(i_{1},j_{1}),(i_{2},j_{2})\\}$. Without
loss of generality, $x=i_{1}$. If $y\neq j_{2}$, then the vertices
$(i_{1},j_{1}),(i_{2},j_{2}),(i_{1},y)$ induce a shortest path, whereas if
$j_{2}=y$, then for $j\in V(K_{s})\setminus\\{j_{1},j_{2}\\}$ the path
$(i_{2},j_{2}),(i_{1},j_{1}),(i_{2},j),(i_{1},j_{2})=(x,y)$ is a geodesic.
This shows that $\operatorname{gp}^{-}(K_{r}\times K_{s})\leq\min\\{r,s\\}$.
For $r=2$, this yields $\operatorname{gp}^{-}(K_{2}\times
K_{s})=2=\min\\{2,s,4\\}$ and $K_{2}\times K_{s}$ has a universal line, whilst
for $r=3$ we have $\operatorname{gp}^{-}(K_{3}\times K_{s})\leq 3$.

For $r\geq 3$ the set of vertices of any layer is a maximal general position
set in $K_{r}\times K_{s}$. Suppose that $\\{i\\}\times K_{s}$ is a
$K_{s}$-layer (the argument for $K_{r}$-layers is identical). The vertices of
$\\{i\\}\times K_{s}$ lie at distance $2$ from each other, so the set is in
general position, whilst if we add any vertex $(i^{\prime},j)$,
$i^{\prime}\neq i$, then for $j_{1},j_{2}\in V(K_{s})\setminus\\{j\\}$ the
path on vertices $(i,j_{1}),(i^{\prime},j),(i,j_{2})$ is a geodesic.

Therefore, as any pair of vertices either forms an independent set or a
clique, for $r\geq 3$ any set of two vertices of $K_{r}\times K_{s}$ can be
extended to a larger general position set and $K_{r}\times K_{s}$ does not
have a universal line, so that $\operatorname{gp}^{-}(K_{r}\times K_{s})\geq
3$. In particular, it follows that $\operatorname{gp}^{-}(K_{3}\times
K_{s})=3=\min\\{3,s,4\\}$ and we can assume that $r\geq 4$.

Consider the set
$S=\\{(i,j),(i,j^{\prime}),(i^{\prime},j),(i^{\prime},j^{\prime})\\}$ with
$i\neq i^{\prime}$ and $j\neq j^{\prime}$. First observe that $K_{r}\times
K_{s}$ has edges $(i,j)\sim(i^{\prime},j^{\prime})$ and
$(i,j^{\prime})\sim(i^{\prime},j)$ and that none of the four vertices of $S$
belongs to a shortest path between two of the remaining ones. Thus, $S$ is a
general position set of $K_{r}\times K_{s}$. Moreover, any other vertex
$(x,y)$ of $K_{r}\times K_{s}$ not in $S$ belongs to a shortest path between
two vertices of $S$ (without loss of generality $x\neq i$ and $y\neq j$, so
$(x,y)$ lies on a path of length $2$ between either $(i,j)$ and
$(i,j^{\prime})$ or $(i,j)$ and $(i^{\prime},j)$). Consequently, $S$ is a
maximal general position set of $K_{r}\times K_{s}$, which leads to
$3\leq\operatorname{gp}^{-}(K_{r}\times K_{s})\leq 4$.

Suppose that $K_{r}\times K_{s}$ has a maximal general position set $S$ of
order $3$. As $r\geq 4$, by the preceding argument if $S$ is a clique or an
independent set, then $S$ could be extended to a larger set, so, since a
general position set is an independent union of cliques [5], $S$ must induce a
graph isomorphic to $K_{1}\cup K_{2}$ (a graph on three vertices with only one
edge). If $(i,j)$ and $(i^{\prime},j^{\prime})$ are the vertices of the
induced $K_{2}$ in $S$, then the vertex corresponding to the $K_{1}$ must be
either $(i^{\prime},j)$ or $(i,j^{\prime})$, say $(i^{\prime},j)$; however, in
this case $S$ could be extended by adding $(i,j^{\prime})$ to give a general
position set of order $4$ with the form discussed above. Therefore for $r\geq
4$ we have $\operatorname{gp}^{-}(K_{r}\times K_{s})=4=\min\\{r,s,4\\}$ and
the result is proven. ∎

##  6 Connection with lower monophonic position number

In this section we relate the lower general position number to the monophonic
position number mentioned in Section 1. The monophonic position number was
introduced in [39] as follows. A path $P$ in a graph $G$ is _induced_ or
_monophonic_ if $G$ contains no chords between non-consecutive vertices of
$P$. A set $M\subseteq V(G)$ is in _monophonic position_ if no induced path in
$G$ contains three or more vertices of $M$; the _monophonic position number_
$\operatorname{mp}(G)$ of $G$ is the number of vertices in a largest
monophonic position set. It was shown in [39] that for any graph $G$ we have
$\operatorname{mp}(G)\leq\operatorname{gp}(G)$ and that for any $2\leq a\leq
b$ there exists a graph with $\operatorname{mp}(G)=a$ and
$\operatorname{gp}(G)=b$. This question was explored further in [41], which
asked for the smallest possible order of a graph $G$ with
$\operatorname{mp}(G)=a$ and $\operatorname{gp}(G)=b$ for given $a\leq b$.

Figure 3: The Petersen graph with a lower monophonic position set (grey)

By analogy with the lower general position number, we define the lower
monophonic position number $\operatorname{mp}^{-}(G)$ of $G$ to be the number
of vertices in a smallest maximal monophonic position set of $G$. For any
graph $G$ with order $n\geq 2$ we have $\operatorname{mp}^{-}(G)\geq 2$ and it
is easily verified that the construction of Theorem 3.4 shows that for any
$2\leq a\leq b$ there is a graph $G$ with $\operatorname{mp}^{-}(G)=a$ and
$\operatorname{mp}(G)=b$. For an example of this concept, see Figure 3, which
displays a lower monophonic position set in the Petersen graph $P$. Recall
that $\operatorname{gp}^{-}(P)=4$, so that in this case
$\operatorname{mp}^{-}(P)<\operatorname{gp}^{-}(P)$. Intuition might suggest
that the relation $\operatorname{mp}^{-}(G)\leq\operatorname{gp}^{-}(G)$ holds
generally, as with the “ordinary” general and monophonic position numbers.
Interestingly, this turns out to be false.

######  Theorem 6.1.

For $a,b\geq 1$, there exists a graph $G$ with $\operatorname{mp}^{-}(G)=a$
and $\operatorname{gp}^{-}(G)=b$ if and only if $a=b$, $2\leq a<b$ or $3\leq
b<a$.

###### Proof.

If $a=b$ then obviously the clique $K_{a}$ will suffice, so we can assume that
$a\neq b$. If $a$ or $b$ is one, then the graph has order one and $a=b=1$.
Also observe that if $b=2$, then the graph has a universal line, which will
also be a maximal monophonic position set, so that $a=2$. It remains only to
prove that the required graphs exist for $2\leq a<b$ and $3\leq b<a$.

We first deal with the case $2\leq a<b$. Take a cycle of length $6$ and
identify its vertex set with $\mathbb{Z}_{6}$ in the natural way. Now expand
each vertex $i$ into a clique $W_{i}$ and add all possible edges between
$W_{i}$ and $W_{i+1}$ for $0\leq i\leq 5$ $\pmod{6}$.

Suppose that $a$ is even. Choose the cliques such that
$|W_{0}|=|W_{2}|=\frac{a}{2}$ and all other cliques have order
$b-\frac{a}{2}$. In Fig. 4 the construction for $a=4$ and $b=6$ is presented.

Figure 4: Construction for $a=4$ and $b=6$: the lower gp-set

As the monophonic position number of a cycle of length $6$ is $2$, it follows
that the lower monophonic position number of this graph is the sum of the
orders of the two smallest cliques $W_{i}$; as $b\geq a$ the lower monophonic
position number is $a$. Similarly it follows by Proposition 2.3 that the
maximal general position sets are $W_{i}\cup W_{i+1}$ for $0\leq i\leq 5$ and
the sum $i+1$ done mod $6$; $W_{i}\cup W_{i+3}$ for $0\leq i\leq 2$; and
$W_{i}\cup W_{i+2}\cup W_{i+4}$ for $i=0,1$. The smallest such sets have order
$b$. Therefore this graph has the required parameters. If $a$ is odd, then it
can be verified that the graph with $|W_{0}|=\frac{a+1}{2}$,
$|W_{2}|=\frac{a-1}{2}$ and all other parts of size $b-\frac{a-1}{2}$ works.

Now we prove existence for $3\leq b<a$. Define the graph $Z(w,r,s)$ as follows
(see the example in Fig. 5). Take a clique $W$ and divide it into four parts
$W$, $R$, $S_{1}$ and $S_{2}$, where $|R|=r\geq 1$, $|S_{1}|=|S_{2}|=s\geq 1$
and $|W|=w\geq s$. The graph $Z(w,r,s)$ is formed by introducing two new
vertices $x_{1}$ and $x_{2}$ and joining $x_{1}$ to every vertex in $S_{1}\cup
R$ and $x_{2}$ to every vertex in $S_{2}\cup R$. We claim that
$S=\\{x_{1},x_{2}\\}\cup S_{1}$ is a smallest maximal general position set of
$Z(w,r,s)$. The graph $Z(w,r,s)$ has diameter two and so a subset of
$V(Z(w,r,s))$ is in general position if and only if it is a disjoint union of
cliques, so the set $S$ is a maximal general position set.

Figure 5: A graph $Z(2,2,1)$ with $\operatorname{mp}^{-}(G)=4$ (left) and
$\operatorname{gp}^{-}(G)=3$ (right)

Without loss of generality, apart from $\\{x_{1},x_{2}\\}\cup S_{1}$ there are
just four types of independent unions of cliques to consider (since all the
vertices within one of $W$, $S_{1}$, $S_{2}$ and $R$ are twins, it is easily
seen that maximality requires taking the whole set), namely $W\cup R\cup
S_{1}\cup S_{2}$, $R\cup S_{1}\cup\\{x_{1}\\}$, $W\cup S_{2}\cup\\{x_{1}\\}$
and $W\cup\\{x_{1},x_{2}\\}$, which have orders $w+r+2s$, $r+s+1$, $w+s+1$ and
$w+2$ respectively, all of which are at least $s+2$. Thus $S$ is a smallest
possible maximal general position set of $Z(w,r,s)$.

Now we deal with the monophonic position sets. Using our observation on twins,
we can confine our attention to the same sets as the previous paragraph;
however, the set $S_{1}\cup\\{x_{1},x_{2}\\}$ is not in monophonic position
(if $s_{1}\in S_{1},s_{2}\in S_{2}$, then $x_{1},s_{1},s_{2},x_{2}$ is an
induced path), leaving us with the sets $W\cup R\cup S_{1}\cup S_{2}$, $R\cup
S_{1}\cup\\{x_{1}\\}$, $W\cup S_{2}\cup\\{x_{1}\\}$ and
$W\cup\\{x_{1},x_{2}\\}$, all of which are maximal monophonic position sets.
The smallest of these has order $\min\\{w+2,r+s+1\\}$. It follows that if
$a>b\geq 3$, then the graph $Z(a-2,a-b+1,b-2)$ has the required properties. ∎

##  7 Concluding remarks

In this paper we considered general position sets of smallest cardinality that
are maximal with respect to the set inclusion property. We conclude by
mentioning some promising directions for future research suggested by our
results.

  * •

For $2\leq a,b$, what is the smallest possible order of a graph with
$\operatorname{mp}^{-}(G)=a$ and $\operatorname{gp}^{-}(G)=b$? What is the
smallest order of a graph with $\operatorname{gp}^{-}(G)=a$ and
$\operatorname{gp}(G)=b$?

  * •

In connection with Inequality (1) and the difficult problem of characterising
graphs $G$ with $\operatorname{gp}^{-}(G)=2$, it could be interesting to
determine further families of graphs that satisfy this property.

  * •

Also in connection with Inequality (1), is it possible to characterise all
graphs $G$ with $\operatorname{gp}^{-}(G)=\operatorname{gp}(G)$?

  * •

Most of the graphs studied in Section 5 have diameter two. The general
position numbers of graphs with diameter two were determined in [5]. This
suggests studying lower general position sets of graphs of diameter two in
general.

  * •

Cartesian products with universal lines were characterised in [34]. It would
therefore be of interest to study the value of the lower general position
numbers of Cartesian products.

  * •

As discussed in Section 1, there are several noteworthy variations of the
general position number in the literature, including the mutual visibility
number [15], $d$-position sets [26], vertex position numbers [37], Steiner
position numbers [24], edge general position numbers [30], mobile position
sets [23], etc. We suggest studying lower versions of these parameters.

## Acknowledgements

Sandi Klavžar was supported by the Slovenian Research Agency (ARRS) under the
grants P1-0297, J1-2452, and N1-0285. James Tuite gratefully acknowledges
funding support from EPSRC grant EP/W522338/1. Aditi Krishnakumar conducted
this research with funding from an Open University research internship. I. G.
Yero has been partially supported by the Spanish Ministry of Science and
Innovation through the grant PID2019-105824GB-I00. The authors thank the two
anonymous reviewers for their helpful suggestions. There are no datasets
associated with the article.

## References

  * [1] P. Aboulker, L. Beaudou, M. Matamala, J. Zamora, Graphs with no induced house nor induced hole have the de Bruijn-Erdős property, J. Graph Theory 100 (2022) 638–652.
  * [2] P. Aboulker, M. Matamala, P. Rochet, J. Zamora, A new class of graphs that satisfies the Chen-Chvátal conjecture, J. Graph Theory 87 (2018) 77–88.
  * [3] M.A. Adena, D.A. Holton, P.A. Kelly, Some thoughts on the no-three-in-line problem, Lecture Notes in Math. 403 (1974) 6–17.
  * [4] O. Aichholzer, D. Eppstein, E.M. Hainzl, Geometric dominating sets-a minimum version of the No-Three-In-Line Problem, Comput. Geom. 108 (2023) Paper 101913.
  * [5] 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.
  * [6] L. Beaudou, A. Bondy, X. Chen, E. Chiniforooshan, M. Chudnovsky, V. Chvátal, N. Fraiman, Y. Zwols, A De Bruijn-Erdős theorem for chordal graphs, Electron. J. Combin. 22 (2015) Paper 1.70.
  * [7] P. Brass, W. Moser, J. Pach, Packing lattice points in subspaces. Research Problems in Discrete Geometry. Springer, New York (2005) 417–421.
  * [8] U. Chandran S.V., M.C. Dourado, M.G.S. Thankachy, Computational and structural aspects of the geodetic and the hull numbers of shadow graphs, Discrete Appl. Math. 319 (2022) 499–510.
  * [9] U. Chandran S.V., G.J. Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Combin. 4 (2016) 135–143.
  * [10] U. Chandran S.V., S. Klavžar, P.K. Neethu, R. Sampaio, The general position avoidance game and hardness of general position games, arXiv:2205.03526 [math.CO].
  * [11] G. Chartrand, P. Zhang, Extreme geodesic graphs, Czechoslovak Math. J. 52 (2002) 771–780.
  * [12] X. Chen, V. Chvátal, Problems related to a De Bruijn-Erdős theorem, Discrete Appl. Math. 156 (2008) 2101–2108.
  * [13] V. Chvátal, A de Bruijn-Erdős theorem in graphs? Graph theory–favorite conjectures and open problems. 2. Probl. Books in Math., Springer, Cham, (2018) 149–176.
  * [14] A.S. Cooper, O. Pikhurko, J.R. Schmitt, G.S. Warrington, Martin Gardner’s minimum no-3-in-a-line problem, Amer. Math. Monthly 121 (2014) 213–221.
  * [15] G. Di Stefano, Mutual visibility in graphs, Appl. Math. Comput. 419 (2022) Paper 126850.
  * [16] H.E. Dudeney, Amusements in Mathematics, Nelson, Edinburgh (1917).
  * [17] M. Gardner, Mathematical games: combinatorial problems, some old, some new and all newly attacked by computer, Sci. Amer. 235 (1976) 131–137.
  * [18] M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman and Co. (1979).
  * [19] M. Ghorbani, H.R. Maimani, M. Momeni, F.R. Mahid, S. Klavžar, G. Rus, The general position problem on Kneser graphs and on some graph operations, Discuss. Math. Graph Theory 41 (2021) 1199–1213.
  * [20] R.K. Guy, P.A. Kelly, The no-three-in-line problem, Can. Math. Bull. 11 (1968) 527–531.
  * [21] R.R. Hall, T.H. Jackson, A. Sudbery, K. Wild, Some advances in the no-three-in-line problem, J. Comb. Theory Ser. A. 18 (1975) 336–341.
  * [22] W. Imrich, S. Klavžar, D.F. Rall, Topics in Graph Theory. Graphs and their Cartesian Product, A K Peters, Ltd., Wellesley, MA, (2008).
  * [23] S. Klavžar, A. Krishnakumar, J. Tuite, I.G. Yero, Traversing a graph in general position, Bull. Aust. Math. Soc. (2023) 1–13.
  * [24] S. Klavžar, D. Kuziak, I. Peterin, I.G. Yero, A Steiner general position problem in graph theory, Comput. Appl. Math. 40 (2021) 1–15.
  * [25] S. Klavžar, P.K. Neethu, U. Chandran S.V., The general position achievement game played on graphs, Discrete Appl. Math. 317 (2022) 109–116.
  * [26] S. Klavžar, D.F. Rall, I.G. Yero, General $d$-position sets. Ars Math. Contemp. 21 (2021) Paper P1.03.
  * [27] S. Klavžar, I.G. Yero, The general position problem and strong resolving graphs, Open Math. 17 (2019) 1126–1135.
  * [28] J. Körner, On the extremal combinatorics of the Hamming space, J. Comb. Theory Ser. A 71 (1995) 112–126.
  * [29] P. Manuel, S. Klavžar, A general position problem in graph theory, Bull. Aust. Math. Soc. 98 (2018) 177–187.
  * [30] P. Manuel, R. Prabha, S. Klavžar, The edge general position problem, Bull. Malays. Math. Sci. Soc. 45 (2022) 2997–3009.
  * [31] P.K. Neethu, U. Chandran S.V., M. Changat, S. Klavžar, On the general position number of complementary prisms, Fund. Inform. 178 (2021) 267–281.
  * [32] B. Patkós, On the general position problem on Kneser graphs, Ars Math. Contemp. 18 (2020) 273–280.
  * [33] E. Pegg Jr., Math Games. Chessboard Tasks. https://www.mathpuzzle.com/MAA/36-Chessboard\%20Tasks/mathgames\\_04\\_11\\_05.html, accessed on February 18, 2023.
  * [34] J.A. Rodríguez-Velázquez, Universal lines in graphs, Quaest. Math. 45 (2022) 1485–1500.
  * [35] K.F. Roth, On a problem of Heilbronn, J. London Math. Soc. 26 (1951) 198–204.
  * [36] R. Schrader, L. Stenmans, A de Bruijn-Erdős theorem for $(q,q-4)$-graphs, Discrete Appl. Math. 279 (2020) 198–201.
  * [37] M. Thankachy, U. Chandran S.V., J. Tuite, E.J. Thomas, G. Di Stefano, G. Erskine, On the vertex position number of graphs, Discuss. Math. Graph Theory (In Press) (2023) arXiv preprint arXiv:2209.00359
  * [38] E.J. Thomas, U. Chandran S.V., Characterization of classes of graphs with large general position number, AKCE Int. J. Graphs Comb. (2020) 1–5.
  * [39] E.J. Thomas, U. Chandran S.V., J. Tuite, G. Di Stefano, On monophonic position sets of graphs, Discrete Appl. Math. (2023) doi.org/10.1016/j.dam.2023.02.021.
  * [40] J. Tian, K. Xu, The general position number of Cartesian products involving a factor with small diameter, Appl. Math. Comput. 403 (2021) Paper 126206.
  * [41] J. Tuite, E.J. Thomas, U. Chandran S.V., On some extremal position problems for graphs, Ars Math. Contemp. (2023), doi:10.26493/1855-3974.3094.bc6
  * [42] Y. Yao, M. He, S. Ji, On the general position number of two classes of graphs, Open Math. 20 (2022) 1021–1029.