# On monophonic position sets in graphs

Elias John Thomas<EMAIL_ADDRESS>Ullas Chandran S. V
<EMAIL_ADDRESS>James Tuite<EMAIL_ADDRESS>Gabriele Di Stefano
<EMAIL_ADDRESS>Department of Mathematics, Mar Ivanios College,
University of Kerala, Thiruvananthapuram-695015, Kerala, India  Department of
Mathematics, Mahatma Gandhi College, University of Kerala,
Thiruvananthapuram-695004, Kerala, India  Department of Mathematics and
Statistics, Open University, Walton Hall, Milton Keynes, UK  Department of
Information Engineering, Computer Science and Mathematics, University of
L’Aquila, Italy

###### Abstract

The general position problem in graph theory asks for the largest set $S$ of
vertices of a graph $G$ such that no shortest path of $G$ contains more than
two vertices of $S$. In this paper we consider a variant of the general
position problem called the _monophonic position problem_ , obtained by
replacing ‘shortest path’ by ‘induced path’. We prove some basic properties
and bounds for the monophonic position number of a graph and determine the
monophonic position number of some graph families, including unicyclic graphs,
complements of bipartite graphs and split graphs. We show that the monophonic
position number of triangle-free graphs is bounded above by the independence
number. We present realisation results for the general position number,
monophonic position number and monophonic hull number. Finally we discuss the
complexity of the monophonic position problem.

###### keywords:

general position set , general position number , monophonic position set ,
monophonic position number.

###### MSC:

05C12 , 05C69

††journal: Discrete Applied Mathematics

##  1 Introduction

In 1900 Dudeney, famous for his mathematical puzzles, posed the following
question [15]: what is the largest number of pawns that can be placed on an
$n\times n$ chessboard such that no horizontal or vertical lines contains more
than two pawns? This problem was generalised to the setting of graph theory
independently in [25, 26] and [6] as follows: a set of vertices $S$ in a graph
$G$ is in _general position_ if no shortest path of $G$ contains more than two
vertices of $S$. The problem then consists of finding the largest set of
vertices in general position for a given graph $G$. This has been shown to be
an NP-complete problem [25]. The general position problem has been the subject
of intensive research; for some recent developments see [16, 24, 27, 28, 30].

Some interesting variants of the general position problem have been considered
in the literature. In [22] the authors consider the general position problem
using the _Steiner distance_ instead of the normal graph distance. In [23] the
shortest paths considered are restricted to have length at most $d$, so that a
set $S$ of vertices of a graph $G$ is a _$d$ -position set_ if for any three
vertices $u,v,w\in S$, if $w$ lies on a shortest $u,v$-path, then
$d_{G}(u,v)>d$. The paper [31] discusses the largest general position sets
that are also independent sets. A further recent variant of the general
position problem can be found in [11], which discusses _mutual visibility
sets_ ; a set $M$ of vertices of a graph $G$ is _mutually visible_ if for any
$u,v\in M$ there exists at least one shortest $u,v$-path in $G$ that
intersects $M$ only in the vertices $u,v$. In this paper, we consider a
variation of the general position problem, which we call the _monophonic
position problem_ , obtained by replacing ‘shortest path’ by ‘induced path’.

We now define the terminology that will be used in this paper. By a graph
$G=(V,E)$ we mean a finite, undirected simple graph. The _distance_ $d(u,v)$
between two vertices $u$ and $v$ in a connected graph $G$ is the length of a
shortest $u,v$-path in $G$, any such shortest $u,v$-path is a _geodesic_. A
path $P$ in $G$ is _induced_ or _monophonic_ if $G$ contains no chords between
non-adjacent vertices of $P$.

We will denote the subgraph of $G$ induced by a subset $S\subseteq V(G)$ by
$G[S]$. A vertex is _simplicial_ if its neighbourhood induces a clique; in
particular every leaf is simplicial. We denote the number of simplicial
vertices and leaves of a graph $G$ by ${\rm s}(G)$ and $\ell(G)$ respectively.
The _clique number_ $\omega(G)$ of $G$ is the number of vertices in a maximum
clique in $G$ and the _independence number_ $\alpha(G)$ is the number of
vertices of a maximum independent set. A subset $S\subseteq V(G)$ is an
_independent union of cliques_ of $G$ if $G[S]$ is a disjoint union of
cliques; the number of vertices in a maximum independent union of cliques will
be written as $\alpha^{\omega}(G)$. A graph $G$ is a _block graph_ if every
maximal 2-connected component of $G$ is a clique.

The path of length $\ell$ and order $\ell+1$ will be written as $P_{\ell}$ and
the cycle of length $\ell$ as $C_{\ell}$. The _join_ $G\vee H$ of two graphs
is the graph formed from the disjoint union of $G$ and $H$ by joining every
vertex of $G$ to every vertex of $H$ by an edge. Let $G$ and $H$ be graphs
where $V(G)=\\{v_{1},\dots,v_{n}\\}$; then the _corona product_ $G\odot H$ is
obtained from the disjoint union of $G$ and $n$ disjoint copies of $H$, say
$H_{1},\dots,H_{n}$, by making the vertex $v_{i}$ adjacent to every vertex in
$H_{i}$ for $1\leq i\leq n$. Finally, for graphs $G$ and $H$, the _Cartesian
product_ $G\Box H$, is the graph with vertex set $V(G\Box H)=V(G)\times V(H)$
such that two vertices $(u_{1},v_{1}),(u_{2},v_{2})$ are adjacent in $G\Box H$
if and only if either $u_{1}=u_{2}$ and $v_{1}\sim v_{2}$ in $H$, or else
$v_{1}=v_{2}$ and $u_{1}\sim u_{2}$ in $G$.

For two distinct vertices $u,v$ of a graph $G$, the _monophonic interval_
$K[u,v]$ is the set of all vertices lying on at least one monophonic path
connecting $u$ and $v$. The _monophonic closure_ of a set $M\subseteq V(G)$ is
$K[M]=\bigcup_{{}_{u,v\in M}}K[u,v].$ If $K[M]=M$, then $M$ is _monophonically
convex_ or _m-convex_. A smallest m-convex set containing $M$ is a _m-convex
hull_ of $M$ and is denoted by $[M]_{m}$. It is possible to construct the
monophonic convex hull $[M]_{m}$ from the sequence $\\{K_{k}[M]\\}$, $k\geq
0$, where $K_{0}[M]=M$, $K_{1}[M]=K[M]$ and $K_{k}[M]=K[K_{k-1}[M]]$ for
$k\geq 2$. From some term onwards, the sequence must be constant; if $r$ is
the smallest number such that $K_{r}[M]=K_{r+1}[M]$, then $K_{r}[M]=[M]_{m}$.
A set $M\subseteq V(G)$ is a _monophonic hull set_ if $[M]_{m}=V(G)$. The
_monophonic hull number_ $h_{m}(G)$ of $G$ is the size of a smallest
monophonic hull set of $G$. A vertex $u$ in $M$ is said to be an _m-interior_
vertex of $M$ if $u\in K[M-\\{u\\}]$. The set of all interior vertices of $M$
is denoted by $M^{0}$. For any other graph-theoretical terminology we refer to
[4].

The plan of this paper is as follows. In Section 2 we introduce the monophonic
position number of a graph, determine some simple bounds and discuss the
behaviour of the monophonic position number under some graph operations. In
Section 3 we give a sharp bound for the mp-number of triangle-free graphs and
determine the mp-numbers of unicyclic graphs and the join and corona products
of graphs. In Section 4 we find the mp-numbers of split graphs and complements
of bipartite graphs. Section 5 provides realisation results for the gp-number,
mp-number and monophonic hull number. Finally in Section 6 we consider the
computational complexity of the monophonic position problem.

##  2 Monophonic position sets in graphs

Recall that a set $S$ of vertices in a graph $G$ is a _general position set_ ,
or _gp-set_ for short, if no shortest path in $G$ contains more than two
vertices of $S$. The number of vertices in a largest gp-set of $G$ is called
the _general position number_ of $G$ and is denoted by ${\rm gp}(G)$. We have
the following result for the general position number of graphs with diameter
two.

######  Theorem 2.1 ([2]).

If ${\rm diam}(G)=2$, then ${\rm gp}(G)=\max\\{\omega(G),\eta(G)\\},$ where
$\eta(G)$ is the maximum order of an induced complete multipartite subgraph of
the complement of $G$ and $\omega(G)$ is the clique number of $G$.

We now introduce the following variant of the gp-number.

######  Definition 2.2.

A set $M\subseteq V(G)$ is a _monophonic position set_ or _mp-set_ of $G$ if
no three vertices of $M$ lie on a common monophonic path in $G$. The
_monophonic position number_ or _mp-number_ ${\rm mp}(G)$ of $G$ is the number
of vertices in a largest mp-set of $G$.

For an example of these concepts see Figure 1. Observe that every monophonic
position set $S$ of a graph $G$ is also in general position; it follows that
${\rm mp}(G)\leq{\rm gp}(G)$. Any pair of vertices is in monophonic position,
so for graphs with order $n\geq 2$ we have $2\leq{\rm mp}(G)\leq n$. It is
easily seen that a connected graph satisfies ${\rm mp}(G)=n$ if and only if
$G\cong K_{n}$. Also the mp-numbers of the cycle $C_{n}$ is given by ${\rm
mp}(C_{n})=2$ for $n\geq 4$.

Figure 1: The Petersen graph with a maximum gp-set (left) and a maximum mp-set
(right)

We begin by noting that for a wide class of graphs the monophonic position
number coincides with the general position number. A graph $G$ is _distance-
hereditary_ if for any connected induced subgraph $H$ of $G$ and vertices
$u,v\in H$ we have $d_{H}(u,v)=d_{G}(u,v)$. Distance-hereditary graphs have
been characterised by Howorka [18] and many works in the literature are
dedicated to them as well as to their generalisations or specialisations (see
e.g. [7, 9, 10, 19]).

######  Observation 2.3.

For any distance-hereditary graph $G$ we have ${\rm mp}(G)={\rm gp}(G)$.

###### Proof.

Consider an induced $u,v$-path $P$ in $G$. Then the subgraph of $G$ induced by
the vertices of $P$ is a path between $u$ and $v$ and, by definition of
distance-hereditary graph, its length is the distance between $u$ and $v$ in
$G$, that is, $P$ is a shortest path in $G$. Hence, by the generality of $P$,
any induced path in $G$ is a shortest path. Since any shortest path is also an
induced path, the definitions of monophonic position set and general position
set coincide for this class of graphs. ∎

Since the class of distance-hereditary graphs includes other well studied
classes of graphs such as cographs, block graphs, trees and Ptolemaic graphs,
results provided for these classes can be seen as a consequence of Observation
2.3 itself. Distance-hereditary graphs $G$ are not characterized by the
relation ${\rm mp}(G)={\rm gp}(G)$. Consider the graph $G=C_{5}\odot K_{1}$,
that is a graph consisting of a cycle with five vertices, each one with a
single pendant vertex. For this graph ${\rm mp}(G)={\rm gp}(G)=5$, but the
graph is not distance-hereditary.

######  Corollary 2.4.

For any block graph $G$ with $s(G)$ simplicial vertices, ${\rm mp}(G)={\rm
s}(G)$. In particular, for any tree $T$ with $\ell(T)$ leaves, we have ${\rm
mp}(T)=\ell(T)$.

###### Proof.

By the result of [25] we have ${\rm gp}(G)={\rm s}(G)$ for any block graph
$G$. As block graphs are distance-hereditary the result follows from
Observation 2.3. In particular any tree $T$ is a block graph and a vertex of
$T$ is simplicial if and only if it is a leaf of $T$. ∎

######  Corollary 2.5.

For integers $r_{1}\geq r_{2}\geq\dots\geq r_{t}$ the mp-number and gp-number
of the complete multipartite graph $K_{r_{1},r_{2},\dots,r_{t}}$ are given by

${\rm gp}(K_{r_{1},r_{2},\dots,r_{t}})={\rm
mp}(K_{r_{1},r_{2},\dots,r_{t}})=\max\\{r_{1},t\\}.$

###### Proof.

The result for the gp-number follows from Theorem 2.1. Complete multipartite
graphs are distance-hereditary, so the result for the mp-number follows from
Observation 2.3. ∎

We now provide some bounds on the monophonic position number of a graph. It
was shown in [6] that the gp-number of a graph with diameter $D$ is bounded
above by $n-D+1$; there is an analogous upper bound for the mp-number of a
graph in terms of the length of its longest induced path.

######  Proposition 2.6.

If $L$ is the length of the longest monophonic path of a graph $G$ with order
$n$, then ${\rm mp}(G)\leq n-L+1$. This bound is sharp.

###### Proof.

Let $P$ be a longest monophonic path in $G$ with length $L$ and let $M$ be a
maximum mp-set. Any induced path in $G$ can contain at most two points of $M$;
therefore at most two points of $M$ lie in $P$, so that at least $L-1$
vertices of $G$ do not lie in $M$. The bound is sharp for cliques and paths. ∎

It follows immediately from Proposition 2.6 that the only connected graphs $G$
with order $n$ and ${\rm mp}(G)=n-1$ are the joins of $K_{1}$ with a disjoint
union of cliques and graphs formed from a clique by deleting between one and
$n-2$ edges incident to a given vertex. In [25] the authors bound the general
position number of a graph $G$ using the _isometric-path number_ , which is
the smallest number of geodesics in $G$ such that each vertex of $G$ is
contained in exactly one of the geodesics. There is a similar upper bound for
the monophonic position number in terms of the _induced path number_
$\rho(G)$, which is defined to be the smallest number of induced paths in $G$
such that each vertex of $G$ is contained in exactly one of the paths. This
parameter was introduced in [8].

######  Lemma 2.7.

The mp-number of a graph $G$ is bounded above by ${\rm mp}(G)\leq 2\rho(G)$.

###### Proof.

Let $P_{1},P_{2},\dots,P_{\rho}$ be a partition of $V(G)$ into $\rho(G)$
induced paths and $M$ be a largest ${\rm mp}$-set. $M$ can intersect each path
$P_{i}$ in at most two vertices, so that $|M|\leq 2\rho(G)$. ∎

It is shown in [1] that the induced path number of any connected cubic graph
$G$ with order $n\geq 7$ is at most $\rho(G)\leq\frac{n-1}{3}$. Thus Lemma 2.7
has the following interesting corollary.

######  Corollary 2.8.

For any connected cubic graph with order $n\geq 7$, the monophonic position
number is at most ${\rm mp}(G)\leq\frac{2(n-1)}{3}$.

We can also bound ${\rm mp}(G)$ above in terms of the number of cut-vertices
in $G$.

######  Lemma 2.9.

Let $G$ be any connected graph of order $n$ and $c(G)$ cut-vertices. Then
there is a maximum monophonic position set without cut-vertices in $G$. Thus
${\rm mp}(G)\leq n-c(G)$.

###### Proof.

Let $M$ be a maximum mp-set of $G$ that contains as few cut-vertices of $G$ as
possible. Suppose for a contradiction that $M$ contains a cut-vertex $v$ of
$G$. Let $W_{1},W_{2},\dots,W_{k},$ $k\geq 2$, be the components of
$G-\\{v\\}$. Then $M$ intersects at most one component, say $W_{1}$, or else
there will be a monophonic path between vertices of $M$ lying in different
components that must pass through $v$.

Let $W$ be the subgraph of $G$ induced by $W_{2}\cup\\{v\\}$. Let $P$ be a
longest path in $W$ with initial vertex $v$. It is easily seen that the
terminal vertex $u$ of $P$ is not a cut-vertex of $G$. The set
$M^{\prime}=(M-\\{v\\})\cup\\{u\\}$ is also a maximum mp-set of $G$, but
contains fewer cut-vertices of $G$ than $M$, contradicting the definition of
$M$. ∎

Lemma 2.9 is sharp for block graphs. We now give a lower bound for ${\rm
mp}(G)$ in terms of the number of simplicial vertices in $G$.

######  Lemma 2.10.

For any graph $G$ we have ${\rm mp}(G)\geq{\rm s}(G)$.

###### Proof.

Let $S$ be the set of simplicial vertices of $G$. Suppose that $u,v,w\in S$
and that $P$ is a monophonic $u,v$-path containing $w$. If ${\rm s}(G)\leq 2$
this is impossible, so we assume that ${\rm s}(G)\geq 3$. The vertex $w$ has
two neighbours $w^{\prime}$ and $w^{\prime\prime}$ on $P$; however by
assumption we have $w^{\prime}\sim w^{\prime\prime}$, so that $P$ is not
induced, a contradiction. ∎

Corollary 2.4 shows that the lower bound in Lemma 2.10 is also sharp for block
graphs. Finally we present two results that show the effect on monophonic
position sets of adding a leaf to a graph.

######  Lemma 2.11.

Let $G^{\prime}$ be a graph obtained from a graph $G$ by adding a pendant edge
$uv$ at a vertex $v$ of $G$. Then ${\rm mp}(G)\leq{\rm mp}(G^{\prime})\leq{\rm
mp}(G)+1$. Moreover, ${\rm mp}(G^{\prime})={\rm mp}(G)+1$ if and only if there
exists a maximum mp-set $M$ of $G$ with $v\not\in M$ such that
$\big{(}M\cup\\{v\\}\big{)}^{0}=\\{v\\}$.

###### Proof.

Since every mp-set of $G$ is also an mp-set of $G^{\prime}$, it follows that
${\rm mp}(G)\leq{\rm mp}(G^{\prime})$. On the other hand, let $M^{\prime}$ be
a maximum mp-set of $G^{\prime}$. Then $M^{\prime}\setminus\\{u\\}$ is an mp-
set of $G$ and so $|M^{\prime}\setminus\\{u\\}|\leq{\rm mp}(G)$. This shows
that ${\rm mp}(G^{\prime})=|M^{\prime}|\leq{\rm mp}(G)+1$.

Suppose that ${\rm mp}(G^{\prime})={\rm mp}(G)+1$. Then ${\rm
mp}(G^{\prime})\geq 3$. If $u\not\in M^{\prime}$, then $M^{\prime}$ is an mp-
set of $G$, which is impossible. Hence $u\in M^{\prime}$. Since
$|M^{\prime}|\geq 3$, it follows that $v\not\in M^{\prime}$, for otherwise $v$
would lie on a monophonic path from $u$ to another member of $M^{\prime}$ in
$G^{\prime}$.

Let $M=(M^{\prime}\cup\\{v\\})\setminus\\{u\\}$. $M$ is too large to be an mp-
set of $G$, so there must exist three vertices $x,y,z$ of $M$ that lie on a
common monophonic path in $G$. Since
$M^{\prime}\setminus\\{u\\}=M\setminus\\{v\\}$ is an mp-set of $G$, one of
these vertices, say $x$, must be $v$. If $y\in K[v,z]$ in $G$, then we would
have $y\in K[u,z]$ in $G^{\prime}$, contradicting the fact that $M^{\prime}$
is an mp-set of $G^{\prime}$. Therefore $v\in K[y,z]$ and so $v$ is the only
vertex in $M$ such that $v\in M^{0}.$ Thus $M\setminus\\{v\\}$ is the required
set.

Conversely, assume that there exists a maximum mp-set $M$ of $G$ with
$v\not\in M$ and $\big{(}M\cup\\{v\\}\big{)}^{0}=\\{v\\}$. We claim that
$M^{\prime}=M\cup\\{u\\}$ is an mp-set of $G^{\prime}$. Suppose that there
exist $x,y,z\in M^{\prime}$ such that $x\in K[y,z]$ in $G^{\prime}$. As $u$ is
a leaf, $x\not=u$, so we can set $z=u$. Then $x\in K[y,v]$ and hence
$x\in\big{(}M\cup\\{v\\}\big{)}^{0},$ which is impossible. Thus $M^{\prime}$
is an mp-set in $G^{\prime}$ with $|M^{\prime}|={\rm mp}(G)+1$. Now, since
${\rm mp}(G^{\prime})\leq{\rm mp}(G)+1$, we have that $M^{\prime}$ is a
maximum mp-set in $G^{\prime}$. ∎

######  Proposition 2.12.

Let $G^{\prime}$ be a graph obtained from $G$ by adding a pendant vertex $u$
to a vertex $v$ in $G$. If $v$ is a simplicial vertex in $G$, then ${\rm
mp}(G)={\rm mp}(G^{\prime})$.

###### Proof.

By Lemma 2.11 ${\rm mp}(G)\leq{\rm mp}(G^{\prime})\leq{\rm mp}(G)+1$ and if
${\rm mp}(G^{\prime})={\rm mp}(G)+1$, then there exists an mp-set $M$ of $G$
of size ${\rm mp}(G)$ such that $v\not\in M$ and
$\big{(}M\cup\\{v\\}\big{)}^{0}=\\{v\\}$. However, as a simplicial vertex $v$
cannot be an interior vertex of any monophonic path in $G$. Hence ${\rm
mp}(G)={\rm mp}(G^{\prime})$. ∎

##  3 Monophonic position in graph families

In this section we discuss the monophonic position numbers of some common
graph families. In Theorem 3.2 we give a sharp bound for the mp-numbers of
triangle-free graphs. We then give exact expressions for the mp-numbers of
unicyclic graphs and graphs formed as the join or corona product of two
graphs.

We will use the following lemma to find an upper bound for the monophonic
position number of triangle-free graphs.

######  Lemma 3.1.

Let $G$ be a connected graph and $M\subseteq V(G)$ be an mp-set. Then $G[M]$
is a disjoint union of $k$ cliques $G[M]=\bigcup_{i=1}^{k}W_{i}$. If $k\geq
2$, then for each $i\in[k]$ any two vertices of $W_{i}$ have a common
neighbour in $G-M$.

###### Proof.

Let $W_{1},W_{2},\dots,W_{k}$ be the components of $G[M]$. Suppose that for
some $1\leq i\leq k$ the component $W_{i}$ is not a clique. Then $W_{i}$
contains an induced path of length two, say $u,v,w$, which would be an induced
path containing three points of $M$. Therefore $W_{i}$ is a clique for each
$i\in[k]$.

Let $k\geq 2$ and suppose for a contradiction that there is a component, say
$W_{1}$, with $u,v\in V(W_{1})$ such that $u$ and $v$ have no common neighbour
in $G-M$. Let $w$ be any vertex in $W_{2}$ and let $P$ be a $u,w$-monophonic
path $u,u_{1},u_{2},\dots,u_{\ell}=w$ in $G$. Then $\ell\geq 2$. Since $M$ is
an mp-set, it follows that $P$ together with the edge $uv$ is not a monophonic
path in $G$. This shows that $v$ must be adjacent to $u_{j}$ for some $j$ with
$1\leq j\leq\ell-1$. It follows from the choice of $u$ and $v$ that $j\geq 2$.
Let $j$ be the largest suffix for which $v$ is adjacent to $u_{j}$. Then the
$u_{j},w$-subpath of $P$ together with the 2-path $u_{j},v,u$ forms a
monophonic path containing three points of $M$; hence $u$ and $v$ must have a
common neighbour in $G-M$. ∎

######  Theorem 3.2.

The mp-number of a connected triangle-free graph $G$ with order $n\geq 3$
satisfies ${\rm mp}(G)\leq\alpha(G)$. Moreover, if the length of any
monophonic path is at most three, then ${\rm mp}(G)=\alpha(G)$.

###### Proof.

Let $M$ be a maximum mp-set in a triangle-free graph $G$ and let
$W_{1},W_{2},\dots,W_{k}$ be the components of $G[M]$. If $k=1$, then $G[M]$
is a clique and so ${\rm mp}(G)=|M|\leq\omega(G)=2\leq\alpha(G),$ so assume
that $k\geq 2.$ If any component $W_{i}$ of $G[M]$ contains distinct vertices
$u,v$, then by Lemma 3.1 $u$ and $v$ have a common neighbour in $G-M$, so that
$G$ would contain a triangle. It follows that each component of $G[M]$
consists of a single vertex, so that $M$ is an independent set of $G$ and
${\rm mp}(G)\leq\alpha(G)$.

Let $T$ be a maximum independent set of $G$. If three vertices of $T$ lie on a
common monophonic path $P$, then the length of $P$ must be at least four.
Therefore if the longest monophonic path of $G$ has length at most three, then
we have equality in the bound and any maximum independent set of $G$ will be a
maximum mp-set. ∎

The bound in Theorem 3.2 is sharp; it is met by the caterpillar formed by
adjoining one leaf to every internal vertex of a path, complete bipartite
graphs $K_{r,r}$ and the corona product $C_{n}\odot K_{1}$ for $n\geq 4$.
Hence this bound can be achieved by graphs with arbitrarily large diameter,
minimum degree and girth.

Theorem 3.2 can be used to find the monophonic position numbers of some graphs
with large girth. This problem is particularly interesting for the cage
graphs. The unique cubic cages with girths five, six and seven are the
Petersen graph, the Heawood graph and the McGee graph respectively; we omit
the lengthy case argument used to prove the following result.

######  Theorem 3.3.

The monophonic position numbers of the Petersen graph, the Heawood graph and
the McGee graph are three, three and two respectively.

This motivates the following conjecture.

######  Conjecture 3.4.

For sufficiently large $g$, the monophonic position number of a $(d,g)$-cage
$G$ satisfies ${\rm mp}(G)<d$.

We now extend Corollary 2.4 to give a result for unicyclic graphs.

######  Theorem 3.5.

Let $G$ be a unicyclic graph and let $C$ be the unique cycle
$v_{0},v_{1},\dots,v_{s-1}$ of $G$, where $v_{i}\sim v_{i+1}$ for $0\leq i\leq
s-1$ and $v_{0}\sim v_{s-1}$. Define $R=\\{i:0\leq i\leq s-1,d(v_{i})\geq
3\text{ in }G\\}$ and put $r=|R|$. For all $i\in R$ let the component of
$G-\\{v_{i-1},v_{i+1}\\}$ containing $v_{i}$ be denoted by $T_{i}$.

Then

${\rm mp}(G)={\begin{cases}3,&\text{ if }G=K_{3}\\\ \ell(G)+2,&\text{ if
}r=1\text{ or }G=C_{s},s\geq 4,\\\ \ell(G)+1,&\text{ if }r=2,R=\\{i,j\\}\text{
and either }T_{i}\text{ or }T_{j}\text{ is a path},\\\ \ell(G)+1,&\text{ if
}r=2\text{ and }R=\\{i,i+1\\}\text{ for some }0\leq i\leq s-1,\\\
\ell(G),&\text{ otherwise.}\end{cases}}$

###### Proof.

Let $M$ be a maximum mp-set of $G$ containing as many leaves as possible. If
$G=C$, then the result is trivial, so we can suppose that there exists a
vertex on $C$ with degree $\geq 3$ in $G$, so that $R\not=\emptyset$. Clearly
each $T_{i}$ is a tree. Also for $i\in R$ let $T^{\prime}_{i}$ be the set of
leaves of $G$ that lie in $T_{i}$. It is easily verified that for any $i\in R$
the set $T^{\prime}_{i}\cup\\{v_{i-1},v_{i+1}\\}$ is in monophonic position,
so it follows that ${\rm mp}(G)\geq 2+\max\\{|T^{\prime}_{i}|:i\in R\\}$.

By Corollary 2.4 each $T_{i}$ can contain at most $\ell(T_{i})$ points in
monophonic position in $G$. Also $v_{i}$ is a leaf of $T_{i}$ if and only if
$d(v_{i})=3$ in $G$. Suppose that $|M\cap T_{i}|=\ell(T_{i})$ and $d(v_{i})=3$
in $G$, so that $v_{i}$ is a leaf of $T_{i}$. Let $P_{i}$ be a maximal path
(possibly with length zero) $x_{0},x_{1},\dots,x_{t}$ in $T_{i}$ such that
$x_{0}=v_{i}$ and $d(x_{j})=2$ in $T_{i}$ for $1\leq j\leq t$. Deleting
$P_{i}$ from $T_{i}$ leaves a tree with $\ell(T_{i})-1$ leaves and, by our
assumption that $M$ contains as many leaves of $G$ as possible, all of the
leaves of $T_{i}-P_{i}$ are contained in $M$; let $x$ be one of these leaves.
Also, as $T_{i}$ contributes $\ell(T_{i})$ vertices to $M$, $P_{i}$ must
contain a vertex $y$ of $M$. Therefore if $M$ contains a vertex $z\in
V(G-T_{i})$, then there will be a monophonic path in $G$ from $x$ to $z$
through $y$. Therefore for any $i\in R$ if $|M\cap T_{i}|=\ell(T_{i})$ and
$d(v_{i})=3$ in $G$ we have ${\rm mp}(G)=\ell(T_{i})$; however, this is
smaller than the lower bound ${\rm mp}(G)\geq 2+\max\\{|T^{\prime}_{i}|:i\in
R\\}$, a contradiction. Therefore each tree $T_{i}$ for $i\in R$ contributes
at most $|T^{\prime}_{i}|$ vertices to $M$. As the cycle $C$ can contain at
most two points of $M$, it follows that $\ell(G)\leq{\rm mp}(G)\leq\ell(G)+2$,
where the first inequality comes from Lemma 2.10.

If $r=1$, then the lower bound ${\rm mp}(G)\geq 2+\max\\{|T^{\prime}_{i}|:i\in
R\\}=\ell(G)+2$ shows that ${\rm mp}(G)=\ell(G)+2$, so we can assume that
$r\geq 2$. We have $|M|=|M\cap(C-R)|+\Sigma_{i=1}^{r}|M\cap T_{i}|$. If $r=s$
(i.e. if each vertex on $C$ has degree $\geq 3$), then as each tree $T_{i}$
can contribute at most $|T^{\prime}_{i}|$ vertices to $M$, it follows
instantly that ${\rm mp}(G)=\ell(G)$.

Suppose that $R$ contains two vertices $v_{i}$ and $v_{j}$ that are not
neighbours on $C$. As there is a monophonic path from any vertex of $T_{i}$ to
any vertex of $T_{j}$ through any vertex of $C$, $M$ cannot contain any
vertices in $V(T_{i})\cup V(T_{j})\cup V(C-R)$; hence we cannot have equality
in ${\rm mp}(G)\leq\ell(G)+2$, so that ${\rm mp}(G)\leq\ell(G)+1$. Furthermore
if ${\rm mp}(G)=\ell(G)+1$, then this reasoning shows that $r=2$, $M$ contains
two vertices of $C$ and $M$ does not intersect one of $T_{i}-\\{v_{i}\\}$ or
$T_{j}-\\{v_{j}\\}$, say $M\cap(T_{j}-\\{v_{j}\\}=\emptyset$, and $T_{j}$ must
be a path; in this case $T^{\prime}_{i}\cup\\{v_{i-1},v_{i+1}\\}$ is an mp-set
containing $\ell(G)+1$ vertices, so that ${\rm mp}(G)=\ell(G)+1$, but if these
conditions are not met, then ${\rm mp}(G)=\ell(G)$.

It remains only to deal with the case $R=\\{i,i+1\\}$ for some
$i\in\mathbb{Z}_{s}$. If both $T_{i}$ and $T_{i+1}$ contain points of $M$,
then $C-R$ can contain at most one point of $M$, so that ${\rm
mp}(G)\leq\ell(G)+1$; conversely the set $\\{v_{i-1}\\}\cup T^{\prime}_{i}\cup
T^{\prime}_{i+1}$ is in monophonic position, so that we have equality, thereby
completing the proof. ∎

In [16] the authors determined the general position number of the join and
corona product of graphs.

######  Theorem 3.6 ([16]).

For graphs $G$ and $H$ the general position number of the join $G\vee H$ and
the corona product $G\odot H$ are given by

${\rm gp}(G\vee
H)=\max\\{\omega(G)+\omega(H),\alpha^{\omega}(G),\alpha^{\omega}(H)\\}$

and if $G$ is connected and has order $n(G)$, then

${\rm gp}(G\odot H)=n(G)\alpha^{\omega}(H).$

We now determine the corresponding relation for the monophonic position
numbers.

######  Proposition 3.7.

Let $G$ be a connected graph with order $n=n(G)$ and let $H$ be any graph.
Then ${\rm mp}(G\odot H)=n(G){\rm mp}(H)$.

###### Proof.

Let $V(G)=\\{v_{1},\dots,v_{n}\\}$ and let $H_{1},\dots,H_{n}$ be the
corresponding copies of $H$ in $G\odot H$. Let $M$ be a maximum mp-set of
$G\odot H$. By Lemma 2.9 we can assume that $M$ does not contain any cut-
vertices of $G\odot H$. Observe that every vertex of $G$ is a cut-vertex in
$G\odot H$, so that we can take $M$ to lie entirely in $H_{1}\cup
H_{2}\cup\dots\cup H_{n}$. It is easily seen that each set $M\cap V(H_{i})$
must be in monophonic position; it follows that $|M|\leq n(G){\rm mp}(H)$.
Conversely, if $S$ is a maximum mp-set of $H$ and for each $i\in[n]$ the
corresponding set in $H_{i}$ is $S_{i}$, then $S_{1}\cup S_{2}\cup\dots\cup
S_{n}$ is in monophonic position. Therefore ${\rm mp}(G\odot H)=n(G){\rm
mp}(H)$. ∎

######  Proposition 3.8.

The monophonic position number of the join $G\vee H$ of graphs $G$ and $H$ is
related to the monophonic position numbers of $G$ and $H$ by

${\rm mp}(G\vee H)=\max\\{\omega(G)+\omega(H),{\rm mp}(G),{\rm mp}(H)\\}.$

###### Proof.

It is evident that an mp-set in $G$ is an mp-set in $G\vee H$, so that ${\rm
mp}(G\vee H)\geq{\rm mp}(G)$ and likewise ${\rm mp}(G\vee H)\geq{\rm mp}(H)$.
Also the union of a clique in $G$ and a clique in $H$ is a clique in $G\vee H$
and is hence an mp-set in $G\vee H$, so it follows that ${\rm mp}(G\vee
H)\geq\max\\{\omega(G)+\omega(H),{\rm mp}(G),{\rm mp}(H)\\}$. For the opposite
direction, let $M$ be a maximum mp-set in $G\vee H$ and set $M_{1}=M\cap V(G)$
and $M_{2}=M\cap V(H)$. If $M_{1}=\emptyset$ or $M_{2}=\emptyset$, then
trivially ${\rm mp}(G\vee H)\leq\max\\{{\rm mp}(G),{\rm mp}(H)\\}$, so suppose
that $M_{1}$ and $M_{2}$ are both non-empty. Suppose that there exist distinct
$x_{1},x_{2}\in M_{1}$ such that $x_{1}\not\sim x_{2}$; in this case if $y\in
M_{2}$, then $x_{1},y,x_{2}$ would be a monophonic path in $G\vee H$, a
contradiction. Therefore $M_{1}$ and $M_{2}$ must both induce cliques in $G$
and $H$ respectively, so that ${\rm mp}(G\vee H)\leq\omega(G)+\omega(H)$. ∎

##  4 Complements of bipartite graphs and split graphs

_Cographs_ are induced $P_{4}$-free graphs. As cographs are distance-
hereditary, the mp- and gp-numbers of these graphs are equal by Observation
2.3. It is therefore of interest to study the mp-numbers of induced
$P_{5}$-free graphs. The 5-cycle $C_{5}$ is induced $P_{5}$-free, but ${\rm
mp}(C_{5})=2$ and ${\rm gp}(C_{5})=3$, which shows that in this more general
class of graphs equality does not necessarily hold for the mp- and gp-numbers.
We therefore consider two well-known classes of induced $P_{5}$-free graphs,
namely the complement of connected bipartite graphs and split graphs. Since
the complement of the complete bipartite graph $K_{m,n}$ is disconnected,
clearly ${\rm mp}(\overline{K}_{m,n})=m+n$.

Let $G$ be a connected bipartite graph with bipartition $(A,B)$ and let
$S\subseteq V(G)$. Fix $S_{A}=S\cap A$ and $S_{B}=S\cap B$. A set $X\subseteq
A$ (or $B$) is _uniform_ in $G$ if $N_{G}(u)=N_{G}(v)$ for all $u,v\in X$; we
call $S\subseteq V(G)$ a _uniform set_ if both $S_{A}$ and $S_{B}$ are uniform
in $G$. Let $\psi(G)$ denote the maximum order of a uniform set in $G$.

######  Theorem 4.1.

If $G$ is a connected bipartite graph with bipartition $(A,B)$, then ${\rm
mp}(\overline{G})=\max\\{\alpha(G),\psi(G)\\}.$

###### Proof.

Let $S$ be a maximum monophonic position set in $\overline{G}$. Then both
$S_{A}$ and $S_{B}$ are cliques in $\overline{G}$. If $S_{A}=\emptyset$ or
$S_{B}=\emptyset$, then it is clear that
$|S|\leq\omega(\overline{G})=\alpha(G)$. So assume that $S_{A}\not=\emptyset$
and $S_{B}\not=\emptyset$. If there is an edge between $S_{A}$ and $S_{B}$ in
$\overline{G}$, then it is easily seen that each vertex of $S_{A}$ is adjacent
to all vertices of $S_{B}$. Thus $S$ induces a clique in $\overline{G}$ and so
$|S|\leq\omega(\overline{G})=\alpha(G)$. Hence in the following we can assume
that there is no edge between $S_{A}$ and $S_{B}$ in $\overline{G}$. Thus $S$
induces a complete bipartite subgraph in $G$.

Next, we claim that $S$ is uniform. Assume to the contrary that there exist
vertices $u,v\in S_{A}$ and $w\in B$ such that $w$ is adjacent to $v$ but not
to $u$ in $G$. Then $w\notin S_{B}$. Choose $x\in S_{B}$ arbitrarily. Then the
path $v,u,w,x$ is a $(v,x)$-monophonic path in $\overline{G}$ containing the
vertex $u$, a contradiction to the fact that $S$ is an mp-set of
$\overline{G}$. Thus $S$ must be uniform in $G$ and so $|S|\leq\psi(G)$.
Therefore, whether or not $S_{A}$ or $S_{B}$ are empty, we have ${\rm
mp}(\overline{G})\leq\max\\{\alpha(G),\psi(G)\\}$.

On the other hand, it is clear that ${\rm
mp}(\overline{G})\geq\omega(\overline{G})=\alpha(G)$. Choose $S\subseteq V(G)$
to be a maximum uniform set in $G$. Then both $S_{A}$ and $S_{B}$ are cliques
in $\overline{G}$. If there is no edge between $S_{A}$ and $S_{B}$ in $G$,
then $S$ induces a clique in $\overline{G}$, so that $S$ is in monophonic
position and ${\rm mp}(\overline{G})\geq|S|=\psi(G)$. Hence we can assume that
there is an edge between $S_{A}$ and $S_{B}$ in $G$. Since $S$ is uniform it
follows that each vertex of $S_{A}$ is adjacent to all the vertices of $S_{B}$
in $G$. Hence there is no edge between $S_{A}$ and $S_{B}$ in $\overline{G}$.
Again, since $S$ is uniform, it follows that each vertex in $A$ is either
adjacent to all the vertices of $S_{B}$ or is not adjacent to any vertex of
$S_{B}.$ Similarly, each vertex in $B$ is either adjacent to all vertices of
$S_{A}$ or is not adjacent to any vertex of $S_{A}$. This shows that $S$ is an
mp-set in $\overline{G}$. Hence ${\rm mp}(\overline{G})\geq|S|=\psi(G)$. This
lower bound completes the proof. ∎

For any tree $T$ with diameter at least three, it is clear that $N(u)\neq
N(v)$ for any pair of non-adjacent vertices $u$ and $v$ in $T$. Hence
$\psi(T)=2\leq\alpha(T)$. This proves the following corollary.

######  Corollary 4.2.

If $T$ is a tree with order $n\geq 3$, then

${\rm mp}(\overline{T})={\begin{cases}n,&\text{ if }{\rm diam}(T)\leq 2,\\\
\alpha(T),&\text{ otherwise.}\end{cases}}$

A similar argument yields the following results.

######  Corollary 4.3.

If $n,m\geq 2,$ then

${\rm mp}(\overline{P_{n}\Box P_{m}})={\begin{cases}4,&\text{ if }n=m=2,\\\
\alpha({P_{n}\Box
P_{m}})=\lceil\frac{n}{2}\rceil\lceil\frac{m}{2}\rceil+\lfloor\frac{n}{2}\rfloor\lfloor\frac{m}{2}\rfloor,&\text{
otherwise.}\end{cases}}$

######  Corollary 4.4.

If $k\geq 3$, then ${\rm mp}(\overline{Q_{k}})=2^{k-1}$, where $Q_{k}$ is the
hypercube with order $2^{k}$.

A graph is a _split graph_ if the vertex set can be partitioned into a clique
$C$ and an independent set $I$. If there is a vertex $v$ that is adjacent to
every vertex of $C\setminus\\{v\\}$ and non-adjacent with every vertex of
$I\setminus\\{v\\}$ we will say that $v$ is _divided_. Obviously there cannot
be divided vertices in both $C$ and $I$. If there are no divided vertices,
then $\omega(G)=|C|$ and $\alpha(G)=|I|$. If $G$ contains a divided vertex
$v$, then by moving $v$ from $C$ into $I$ if necessary, we can assume that any
divided vertices lie in $I$ and $\omega(G)=|C|+1$ and $\omega(G)=|I|$. We
define a separated subgraph $(C^{\prime},I^{\prime})$ of the split graph
$G=(C,I)$ as follows.

######  Definition 4.5.

Let $C^{\prime}\subseteq C$ and $I^{\prime}\subseteq I$. Then
$G^{\prime}=(C^{\prime},I^{\prime})$ is a separated subgraph of the split
graph $G=(C,I)$ if and only if it satisfies one of the following two
conditions:

  * 1.

there is no edge from $C^{\prime}$ to $I^{\prime}$ in $G$ or

  * 2.

$|I^{\prime}|=1$ and $C^{\prime}\cup I^{\prime}$ induces a clique in $G$.

Let $\phi(G)$ denote the order of a largest separated subgraph of $G$.

Note that any separated subgraph induces a complete split subgraph in the
complement $\overline{G}$ of $G$, but there can be subgraphs of $G$ with this
property that are not separated.

The subgraph induced by $C$ is trivially separated, as is the subgraph induced
by $I$. If there is a divided vertex $v$ in $I$, then $(C,\\{v\\})$ is
separated. This shows that we always have
$\phi(G)\geq\max\\{\omega(G),\alpha(G)\\}$.

######  Theorem 4.6.

Let $G=(C,I)$ be a connected split graph. Then ${\rm mp}(G)=\phi(G)$.

###### Proof.

Let $G^{\prime}=(C^{\prime},I^{\prime})$ be any separated subgraph of
$G=(C,I)$. It is easily verified that $V(G^{\prime})$ is an mp-set of $G$, so
that ${\rm mp}(G)\geq\phi(G)$.

Conversely let $M$ be any maximum mp-set of $G$. If $M$ is contained entirely
in $C$ or $I$, then $|M|\leq\max\\{\omega(G),\alpha(G)\\}\leq\phi(G)$, so we
assume that $M$ intersects both $C$ and $I$. Write $C^{\prime}=M\cap C$ and
$I^{\prime}=M\cap I$. We show that $(C^{\prime},I^{\prime})$ is a separated
subgraph of $G$. Suppose that there is an edge between a vertex $u$ of
$C^{\prime}$ and a vertex $v$ of $I^{\prime}$ in $G$. If $v$ is not adjacent
to some $u^{\prime}\in C^{\prime}$, then $v,u,u^{\prime}$ would be a
monophonic path contained in $M$, so $v$ must be adjacent to every vertex of
$C^{\prime}$. If there is a vertex $v^{\prime}\in I^{\prime}-\\{v\\}$, then
there must be an edge from $v^{\prime}$ to $C$ and hence there is a monophonic
$v,v^{\prime}$-path through $C^{\prime}$, a contradiction, so that we must
have $|I^{\prime}|=1$ in this case. Therefore $(C^{\prime},I^{\prime})$ is
separated and ${\rm mp}(G)\leq\phi(G)$. ∎

We noted before that for any split graph $G$ we have ${\rm
mp}(G)=\phi(G)\geq\max\\{\omega(G),\alpha(G)\\}$. We now characterise the
cases in which equality holds. For $X\subseteq V(C)$ and $Y\subseteq V(I)$
write $N_{I}(X)=I\cap(\bigcup_{x\in X}N(x))$ and $N_{C}(Y)=C\cap(\bigcup_{y\in
Y}N(y))$. We make use of Hall’s Theorem. If $G$ is a bipartite graph with
partite sets $X,Y$, then a _matching_ in $G$ is a set of independent edges
between $X$ and $Y$. The matching _saturates_ $X$ if every vertex of $X$ is
incident with an edge in the matching (and similarly for $Y$).

######  Theorem 4.7 ([17]).

Let $G$ be a bipartite graph with bipartition $(X,Y)$. There is a matching
that saturates $X$ if and only if for every subset $S\subseteq X$ we have
$|N(S)|\geq|S|$.

We can consider any split graph $G=(C,I)$ as a bipartite graph $G^{*}$ by
deleting all edges in $C$ and taking the partite sets of $G^{*}$ to be $C$ and
$I$. By a matching between $C$ and $I$ in $G$ we will mean a matching in the
bipartite graph $G^{*}$.

######  Theorem 4.8.

If $G=(C,I)$ is a connected split graph with no divided vertices (so that
$|C|=\omega(G)$ and $|I|=\alpha(G)$), then

${\rm mp}(G)=\phi(G)=\max\\{\omega(G),\alpha(G)\\}$

if and only if there exists a matching in $G$ between $C$ and $I$ that
saturates either $C$ or $I$. If $G$ contains a divided vertex $v$ then we have
equality if and only if there is a matching between $C-\\{v\\}$ and
$I-\\{v\\}$ that saturates either $C-\\{v\\}$ or $I-\\{v\\}$.

###### Proof.

Let $G=(C,I)$ be a connected split graph. If $G$ has divided vertices, then we
will assume without loss of generality that they lie in $I$.

Let $G=(C^{\prime},I^{\prime})$ be an arbitrary largest separated subgraph of
$G$. If $C^{\prime}\cup I^{\prime}$ induces a clique, then trivially
$\phi(G)=\omega(G)\geq\alpha(G)$. By Hall’s Theorem [17], if there is no
matching between $C$ and $I$ that saturates $I$, then there is a subset
$J\subseteq I$ such that $|N_{C}(J)|<|J|$. Then $(C\setminus N_{C}(J),J)$ is
separated and has order $>|C|=\omega(G)$. Therefore there must be a divided
vertex in $I$ and $\omega(G)=|C|+1$.

Suppose in this case that there is no matching from $I-\\{v\\}$ to $C$ that
saturates $I-\\{v\\}$. Again by Hall’s Theorem there is a subset $J\subseteq
I-\\{v\\}$ such that $|N_{C}(J)|<|J|$, so that $(C-N_{C}(J),J)$ is separated
and has size $>|C|$ and hence has size exactly $|C|+1=\omega(G)$. This
separated subgraph does not contain $v$ and so adding $v$ to this subgraph
does not yield an mp-set, which implies that $|C|\leq 1$ and
$2\geq\omega(G)\geq\alpha(G)$. The only such connected split graphs are
$P_{1},P_{2}$ and $P_{3}$ and the result is easily verified for these graphs.
Therefore we can assume that there is no edge between $C^{\prime}$ and
$I^{\prime}$.

Suppose that there is a matching between $C$ and $I$ that saturates $C$. We
have $N_{I}(C^{\prime})\subseteq I-I^{\prime}$. By Hall’s Theorem it follows
that $|C^{\prime}|\leq|N_{I}(C^{\prime})|\leq|I-I^{\prime}|.$ This shows that
$\phi(G)=|C^{\prime}|+|I^{\prime}|\leq|I|\leq\alpha(G)$. Now let there be a
matching between $C$ and $I$ that saturates $I$. Then again by Hall’s Theorem
we have $|N_{C}(I^{\prime})|\geq|I^{\prime}|$ and also
$N_{C}(I^{\prime})\subseteq C-C^{\prime}$ and $\phi(G)\leq\omega(G)$. A
similar argument gives the result if $G$ has a divided vertex.

Conversely, assume that $\phi(G)=\max\\{\omega(G),\alpha(G)\\}$. If $G$ has no
divided vertices, suppose for a contradiction that $G$ has no matching between
$C$ and $I$ that saturates $C$ or $I$. Let $\omega(G)\geq\alpha(G)$. By Hall’s
Theorem there is a subset $J\subseteq I$ such that $|N_{C}(J)|<|J|$. Then
$(C\setminus N_{C}(J),J)$ is separated in $G$, so that
$\phi(G)\geq|C|+1\geq|I|+1$, a contradiction. The case
$\alpha(G)\geq\omega(G)$ is similar.

Lastly let $\phi(G)=\max\\{\omega(G),\alpha(G)\\}$ and suppose that there is a
divided vertex $v$ in $I$. If $\omega(G)\geq\alpha(G)$, then $(C,\\{v\\})$ is
separated and gives a maximum mp-set, which is a case that we have already
considered. Hence we can assume that $\alpha(G)>\omega(G)$. As there is no
matching between $C$ and $I-\\{v\\}$ that saturates $C$, there is a subset
$K\subseteq C$ with $|N_{I-\\{v\\}}(K)|<|K|$, so that
$(K,I-(N_{I}(K)\cup\\{v\\}))$ is separated and has size $\alpha(G)$, but does
not contain $v$. Again the fact that $v$ cannot be added to this set to give
an mp-set yields a contradiction. ∎

##  5 Realisation results

In this paper we have presented some properties of the monophonic position
number of graphs. In some respects this graph parameter behaves like the more
widely studied general position number. It is therefore of interest to ask
whether there is a relation between the two numbers other than the trivial
inequality ${\rm mp}(G)\leq{\rm gp}(G)$? We will show that these two
parameters are independent by proving the following realisation result: for
any pair $a,b\in\mathbb{N}$ such that $2\leq a\leq b$ there exists a graph $G$
with ${\rm mp}(G)=a$ and ${\rm gp}(G)=b$. Firstly observe that if $a=b$, then
trivially the complete graph $K_{a}$ has the required properties, so in the
following we will assume that $a<b$.

######  Theorem 5.1.

For any $b\geq 2$ there exists a graph $G$ with ${\rm mp}(G)=2$ and ${\rm
gp}(G)=b$.

###### Proof.

The 5-cycle $C_{5}$ has ${\rm mp}(C_{5})=2,{\rm gp}(C_{5})=3$, so we can
assume that $b\geq 4$. We define the _half-wheel_ graph $H_{r}$ for $r\geq 2$
as follows. Take a cycle $C_{2r}$ of length $2r$ and label the vertices
$1,2,3,\dots,2r$ in the natural manner. Add an extra vertex $x$ and join $x$
to all vertices in $C_{2r}$ with even labels. An example is shown in Figure 2.

$1$$2$$3$$4$$5$$6$$7$$8$$x$ Figure 2: $H_{4}$ with a maximum gp-set

We will show that for $r\geq 4$ $H_{r}$ has ${\rm mp}(H_{r})=2$ and ${\rm
gp}(G)=r$. First let $M$ be an mp-set in $H_{r}$. As the cycle $C_{2r}$ in
$H_{r}$ has no chords $M$ contains at most two points in $C_{2r}$. Therefore
${\rm mp}(H_{r})\leq 3$ and equality holds only if $M$ contains $x$ and two
vertices of the cycle, call them $i$ and $j$, where $i,j\in[2r]$. If $i$ and
$j$ are both even, then $i,x,j$ is a monophonic path passing through three
points of $M$, so we can take $j$ to be odd. Suppose that $i$ is even. If $i$
and $j$ are neighbours on $C_{2r}$, then $j,i,x$ is a monophonic path
containing three points of $M$. If $j$ is not a neighbour of $i$ on $C_{2r}$,
then $d(i,j)=3$ in $H_{r}$ and $i,x,j+1,j$ (where addition is taken modulo
$2r$) is again a monophonic $i,j$-path through $x$. Hence $i$ and $j$ must
both be odd. If $d(i,j)=2$, then we can take $j=i+2$ (again modulo $2r$) and
$i,i-1,x,j+1,j$ is a monophonic $i,j$-path through $x$. Otherwise we must have
$d(i,j)=4$ and $i,i+1,x,j-1,j$ is a monophonic path. This shows that ${\rm
mp}(H_{r})=2$.

The set of all even integers on $C_{2r}$ is a gp-set, so ${\rm gp}(H_{r})\geq
r$. Suppose that there is a gp-set $K$ in $H_{r}$ with $r+1$ elements. Suppose
that $x\not\in K$. Then $K$ contains two vertices that are neighbours on
$C_{2r}$, without loss of generality say $i$ and $i+1$ where $i$ is even. Then
the distance from $i+1$ to any even vertex $j$ of $C_{2r}$ apart from $i$ and
$i+2$ is $3$ and $i+1,i,x,j$ is a geodesic. Also $i+2\not\in K$, as
$i,i+1,i+2$ is a geodesic. Therefore $K$ must consist of the set of odd
vertices of $C_{2r}$ together with $\\{i\\}$. However $i-1,i,i+1$ would then
be a geodesic containing three points of $K$.

Hence we can assume that $x\in K$. Suppose that $K$ contains an even vertex
$i$ of $C_{2r}$. Between any two even vertices of $C_{2r}$ there is a geodesic
passing through $x$, so $K$ can contain no other even vertex of $C_{2r}$. Also
$K$ cannot contain $i+1$ or $i-1$, as $i$ is contained in $(i-1),x$\- and
$(i+1),x$-geodesics. Therefore $K$ would have size at most $2+(r-2)=r$, a
contradiction. Hence $K$ consists of $x$ and the odd vertices of $C_{2r}$;
however, $1,2,x,4,5$ is a geodesic containing three points of $K$. It follows
that for $r\geq 4$ we have ${\rm gp}(H_{r})=r$. ∎

We now turn to the case of larger $a$.

######  Theorem 5.2.

For any $a,b\in\mathbb{N}$ such that $3\leq a\leq b$ there exists a graph $G$
with ${\rm mp}(G)=a$ and ${\rm gp}(G)=b$.

###### Proof.

Let $3\leq a<b$. Suppose firstly that $b\geq a+2$. Join $a-2$ pendant vertices
to the central vertex $x$ of the half-wheel graph $H_{b-a+2}$ to give a graph
$H_{b,a}$. By Theorem 5.1 there are at most two points in monophonic position
and at most $b-a+2\geq 4$ vertices in general position in $H_{b-a+2}$, so,
counting the pendant vertices, we have ${\rm mp}(H_{b,a})\leq a$ and ${\rm
gp}(H_{b,a})\leq b$. On the other hand it is easily seen that the $a-2$
pendant vertices together with any two even vertices on the cycle $C_{2r}$
constitute an mp-set of $H_{b,a}$, whilst the $b-a+2$ even vertices on
$C_{2r}$ and the pendant vertices form a gp-set of $H_{b,a}$ of size $b$.

Now let $b=a+1$ and $a\geq 3$. Let $W_{5}$ be the wheel graph of order six
with central vertex $x$ with $d(x)=5$. Label the vertices of the outer 5-cycle
of $W_{5}$ by the elements of $\mathbb{Z}_{5}$ in the natural way. Let $W(a)$
be the graph formed from $W_{6}$ by attaching $a-2$ pendant vertices to $x$.
Let $M$ be a largest mp-set of $W(a)$. The outer cycle $C_{5}$ of $W_{5}$ can
contain at most two vertices of $M$. If $x\in M$, then $M$ cannot contain both
pendant vertices and vertices on the cycle $C_{5}$ of $W_{5}$, so that
$|M|\leq 3$. Therefore $|M|\leq 2+(a-2)=a$. Conversely the pendant vertices
together with any two vertices of $C_{5}$ yield an mp-set of size $a$, so
${\rm mp}(W(a))=a$.

Let $K$ be a maximum gp-set of $W(a)$. The 5-cycle contains at most three
vertices in general position. Similarly to the previous case we can assume
that $x\not\in K$, so that $|K|\leq 3+(a-2)=a+1$. As the vertices $0,1,3$ of
$C_{5}$ and the $a-2$ pendant vertices form a gp-set of size $a+1$, we have
${\rm gp}(W(a))=a+1$. This completes the existence proof. ∎

Combining these constructions, we have completely classified the pairs $(a,b)$
such that there exists a graph $G$ with monophonic position number $a$ and
general position number $b$.

######  Corollary 5.3.

There exists a graph $G$ with ${\rm mp}(G)=a$ and ${\rm gp}(G)=b$ if and only
if $2\leq a\leq b$ or $a=b=1$.

The _independent position number_ of a graph $G$, which we will denote by
${\rm igp}(G)$, is the largest number of vertices in a maximum set $S\subseteq
V(G)$ that is both independent and in general position. This parameter was
studied in [31]. If we define the _independent monophonic position number_
${\rm imp}(G)$ to be the number of vertices in a maximum subset $S\subseteq
V(G)$ such that $S$ is independent and in monophonic position, then we have
both ${\rm imp}(G)\leq{\rm mp}(G)\leq{\rm gp}(G)$ and ${\rm imp}(G)\leq{\rm
igp}(G)\leq{\rm gp}(G)$. This raises the question whether there is a
relationship between ${\rm mp}(G)$ and ${\rm igp}(G)$. We can easily answer
this in the negative.

######  Theorem 5.4.

For any $1\leq a,b$ there exists a graph $G$ with ${\rm igp}(G)=a$ and ${\rm
mp}(G)=b$ if and only if $1=a\leq b$ or $2\leq a,b$.

###### Proof.

The only graph with ${\rm mp}$-number one is $K_{1}$, which implies the
necessity of the conditions. For $n\geq 1$ we have ${\rm igp}(K_{n})=1$ and
${\rm mp}(K_{n})=n$, so we can assume that $2\leq a,b$. For the case $a\leq
b$, for $r\geq 0$ and $s\geq 1$, define $R(r,s)$ to be the graph formed by
attaching $r$ leaves to one vertex of a copy of $K_{s+1}$; then we have ${\rm
mp}(R(r,s))=r+s$ and ${\rm igp}(R(r,s))=r+1$, so that the graph $R(a-1,b-a+1)$
has the required properties.

Consider now the case $a>b$. Let the graph $K_{s,s}^{-}$ be the complete
bipartite graph $K_{s,s}$ with a perfect matching deleted. Form the graph
$P(r,s)$ by adding an extra vertex $x$ to $K_{s,s}^{-}$ and joining $x$ by an
edge to each vertex of one of the partite sets of $K_{s,s}^{-}$, then adding
$r$ leaves to $x$. This graph satisfies ${\rm mp}(P(r,s))=r+2$ and ${\rm
igp}(P(r,s))=r+s$. Hence the graph $P(a-2,b-a+2)$ has the necessary
parameters. ∎

The graph $R(r,s)$ from the proof of Theorem 5.4 can also be used to answer
Question 2 from [23]. The _dissociation number_ ${\rm diss}(G)$ of a graph $G$
is the number of vertices in a largest subset $S\subseteq V(G)$ such that
$G[S]$ has maximum degree at most one, whilst the _$2$ -position-number_ ${\rm
gp_{2}}(G)$ is the number of vertices in a largest set $K\subset V(G)$ such
that no shortest path in $G$ of length two contains three vertices of $K$. It
is easily seen that any dissociation set is in $2$-general position, so that
${\rm diss}(G)\leq{\rm gp_{2}}(G)$. Furthermore for $2\leq a\leq b$ we have
${\rm diss}(R(a-2,b-a+2))=a$ and ${\rm gp_{2}}(R(a-2,b-a+2))=b$.

The _hull number_ $h(G)$ of a graph $G$ is the smallest number of vertices in
a set $S\subseteq V(G)$ such that every vertex of $G$ lies on a shortest path
between members of $S$. The hull number has been widely studied, for example
in [3, 5, 13]. In [6] it was shown that for any $a,b\in\mathbb{N}$ such that
$2\leq a\leq b$ there exists a graph $G$ with $h(G)=a$ and ${\rm gp}(G)=b$.
The monophonic hull number $h_{m}(G)$ has been studied in [12, 14, 20, 29]. We
now prove a realisation theorem for the monophonic hull number and the
monophonic position number. We will use the following two results in our
analysis.

######  Theorem 5.5 ([29]).

Every monophonic hull set of a graph $G$ contains all its simplicial vertices.

######  Observation 5.6.

Let $M$ be a minimum monophonic hull set of a connected graph $G$ and let
$a,b\in M$. If a vertex $c\not=a,b$ lies on an $a,b$-monophonic path then
$c\not\in M$.

It follows from Observation 5.6 that every minimum monophonic hull set of a
connected graph $G$ is an mp-set in $G$. Consequently, $2\leq h_{m}(G)\leq{\rm
mp}(G)\leq n$. In view of this inequality, we have the following realisation
result.

######  Theorem 5.7.

For all $n,a,b\geq 1$ there exists a connected graph $G$ with $h_{m}(G)=a$,
${\rm mp}(G)=b$ and order $n$ if and only if $a=b=n=1$ or $2\leq a=b\leq n-1$.

###### Proof.

The only graph with $h_{m}(G)=1$ or ${\rm mp}(G)=1$ is $K_{1}$, so assume that
$a\geq 2$. If $b=n$, then $G$ must be a clique, so that $a=b=n$. It remains
only to prove the existence of a graph $G$ with order $n$, $h_{m}(G)=a$ and
${\rm mp}(G)=b$ for all $2\leq a\leq b\leq n-1$.

Let $W$ be a clique of order $b$ and $P_{\ell}$ be a path with length $\ell$
and vertices $x_{0},x_{1},\dots,x_{\ell}$ such that $x_{i}\sim x_{i+1}$ for
$0\leq i\leq\ell-1$. For $1\leq a\leq b$, let $G(a,b,\ell)$ be the graph
formed from $W$ and $P_{\ell}$ by joining $x_{0}$ to $b-a+1$ vertices of $W$.
Write $X=V(W)\cap N(x_{0})$ and $Y=V(W)\cap N(x_{0})$, so that $|X|=a-1$ and
$|Y|=b-a+1$. The order of $G(a,b,\ell)$ is $b+\ell+1$. By Observation 5.6, any
monophonic hull set of $G(a,b,n)$ must contain $X\cup\\{x_{\ell}\\}$;
conversely, this subset is a monophonic hull set, so $h_{m}(G(a,b,\ell))=a$.
As the clique number of $G(a,b,\ell)$ is $b$, we have ${\rm
mp}(G(a,b,\ell))\geq b$. For the converse, let $M$ be a maximum mp-set of
$G(a,b,\ell)$. By Corollary 2.4 $M$ contains at most two vertices of
$P_{\ell}$ and if $|M\cap V(P_{\ell})|=2$, then $M\cap W=\emptyset$ and
$|M|\leq b$. If $|M\cap V(P_{\ell})|=1$, then $M$ cannot contain vertices of
both $X$ and $Y$, so that $|M|\leq\max\\{a,b-a+2\\}\leq b$. Thus $|M|=b$ and
${\rm mp}(G(a,b,\ell))=b$. Therefore the graph $G(a,b,n-b-1)$ has the required
properties. ∎

##  6 Computational complexity

In this section, we study the computational complexity of the problem of
finding the monophonic position number of a general graph. To this end, we
formally define the decision version of the problem:

######  Definition 6.1.

Monophonic position set
Instance: A graph $G$, a positive integer $k\leq|V(G)|$.
Question: Is there a monophonic position set $S$ for $G$ such that $|S|\geq
k$?

The problem is hard to solve as shown by the next theorem.

######  Theorem 6.2.

The Monophonic position set problem is NP-hard.

###### Proof.

We prove that the Clique problem polynomially reduces to Monophonic position
set. Here a definition of the decision version of the problem:

> An instance of Clique is given by a graph $G$ and a positive integer
> $k\leq|V|$. The Clique problem asks whether $G$ contains a clique
> $K\subseteq V(G)$ of size $k$ or more.

The NP-completeness of Clique is well known, as it is one of the original list
of 21 NP-complete problems presented in [21]. We polynomially transform an
instance $(G,k)$ of Clique to an instance $(G^{\prime},k^{\prime})$ of
Monophonic position set. In particular, given $(G,k)$ we must construct a
graph $G^{\prime}$ and a positive integer $k^{\prime}$ such that $G$ has a
clique of size $k$ or more if and only if $G^{\prime}$ has a monophonic
position set of size $k^{\prime}$ or more.

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

$V(G^{\prime})=\\{v^{\prime},v^{\prime\prime}~{}|~{}v\in V(G)\\}$ (1)
$E(G^{\prime})=\\{u^{\prime}v^{\prime}~{}|~{}uv\in
E(G)\\}\cup\\{u^{\prime}v^{\prime\prime}~{}|~{}u,v\in
V(G)\\}\cup\\{u^{\prime\prime}v^{\prime\prime}~{}|~{}u,v\in V(G)\\}$ (2)

In words, $G^{\prime}$ contains a subgraph $H$ isomorphic to $G$ and a clique
graph $H^{\prime}$ of size $n=|V(G)|$ such that $G^{\prime}=H\vee H^{\prime}$.
As for $k^{\prime}$, we set $k^{\prime}=n+k$. Clearly, this construction can
be achieved in polynomial time. It remains to show that an instance $(G,k)$ of
Clique has a positive answer if and only if $(G^{\prime},k^{\prime})$,
instance of Monophonic position set, has a positive answer.

As a preliminary results, note that $\omega(G^{\prime})=\omega(G)+n$. Indeed,
if $S$ is any clique in $G$, then $S^{\prime}=\\{s^{\prime}~{}|~{}s\in S\\}$
is a clique in $H$, and $S^{\prime}\cup V(H^{\prime})$ is a clique in
$G^{\prime}$, since any vertex in $H^{\prime}$ is a universal vertex of
$G^{\prime}$. Then $\omega(G^{\prime})\geq\omega(G)+n$. On the contrary, if
$S$ is any clique of $G^{\prime}$, then $|S\cap V(H)|\leq\omega(G)$ and
$|S\cap V(H^{\prime})|\leq n$. Hence $\omega(G^{\prime})\leq\omega(G)+n$.

By Proposition 3.8, ${\rm mp}(G^{\prime})={\rm mp}(H\vee
H^{\prime})=\max\\{\omega(H)+\omega(H^{\prime}),{\rm mp}(H),{\rm
mp}(H^{\prime})\\}$. We have that $\omega(H^{\prime})={\rm mp}(H^{\prime})=n$
for $H^{\prime}$ is a clique; ${\rm mp}(H)={\rm mp}(G)$ and
$\omega(H)=\omega(G)\leq n$ for $H$ is isomorphic to $G$. Then ${\rm
mp}(G^{\prime})=\max\\{\omega(H)+n,{\rm mp}(H),n\\}=\omega(H)+n$, being ${\rm
mp}(H)\leq n$.

Now assume that an instance $(G,k)$ of Clique has a positive answer, then
$\omega(G)=\omega(H)\geq k$. This implies that ${\rm
mp}(G^{\prime})=\omega(H)+n\geq k+n=k^{\prime}$, and hence Monophonic position
set has a positive answer. On the other hand, if the instance $(G,k)$ of
Clique has a negative answer then $\omega(G)=\omega(H)<k$, which in turn
implies that Monophonic position set has a negative answer, since ${\rm
mp}(G^{\prime})=\omega(H)+n<k+n$. ∎

By the proof of Theorem 6.2, it is not clear if Monophonic position set is NP-
complete. However if we restrict the problem to instances $(G,k)$ with
$k>|V(G)|/2$ and $G=H\vee K$, where $H$ is a generic graph and $K$ is a clique
graph having the same order of $H$, the problem is NP-complete; indeed, given
a solution, it can be tested in polynomial time if it is a clique and if its
size is larger than $k$.

## Acknowledgements

The first author thanks the University of Kerala for providing JRF. The third
author gratefully acknowledges funding support from EPSRC grant EP/W522338/1
and London Mathematical Society grant ECF-2021-27 and thanks the Open
University for an extension of funding during lockdown. The authors thank Dr.
Erskine for help with computation of the mp-numbers of cubic cages.

## References

  * [1] Akbari, S., Horsley, D. & Wanless, I.M., _Induced path factors of regular graphs._ J. Graph Theory 97 (2) (2021), 260-280.
  * [2] Anand, B.S., Chandran S.V., U., Changat, M., Klavžar, S. & Thomas E.J., _Characterization of general position sets and its applications to cographs and bipartite graphs._ Appl. Math. Comput. 359 (2019), 84-89.
  * [3] Araujo, J., Campos, V., Giroire, F., Nisse, N., Sampaio, L. & Soares, R., _On the hull number of some graph classes._ Theor. Comput. Sci. 475 (2013), 1-12.
  * [4] Bondy, J.A. & Murty, U.S.R., _Graph Theory with Applications_ London: Macmillan, Vol. 290 (1976).
  * [5] Cagaanan, G.B. & Canoy Jr., S.R., _On the hull sets and hull number of the Cartesian product of graphs._ Discrete Math. 287 (1-3) (2004), 141-144.
  * [6] Chandran S.V., U. & Parthasarathy, G.J., _The geodesic irredundant sets in graphs._ Int. J. Math. Comb. 4 (2016), 135-143.
  * [7] Cicerone, S. & Di Stefano, G., _Networks with small stretch number._ J. Discrete Algorithms 2 (4) (2004), 383-405.
  * [8] Chartrand, G., McCanna, J., Sherwani, N., Hossain, M. & Hashmi, J., _The induced path number of bipartite graphs._ Ars Comb. 37 (1994), 191-208.
  * [9] Cornelsen, S. & Di Stefano, G. _Treelike comparability graphs._ Discrete Appl. Math. 157 (8) (2009), 1711-1722.
  * [10] Di Stefano, G. _Distance-hereditary comparability graphs._ Discrete Appl. Math. 160 (18) (2012), 2669-2680.
  * [11] Di Stefano, G., _Mutual visibility in graphs._ Appl. Math. Comput. 419 (2022), 126850.
  * [12] Dourado, M.C., Protti, F. & Szwarcfiter, J.L., _Algorithmic aspects of monophonic convexity._ Electron. Notes Discrete Math. 30 (2008), 177-182.
  * [13] Dourado, M.C., Gimbel, J.G., Kratochv’il, J., Protti, F. & Szwarcfiter, J.L., _On the computation of the hull number of a graph._ Discrete Math. 309 (18) (2009), 5668-5674.
  * [14] Dourado, M.C., Protti, F. & Szwarcfiter, J.L., _Complexity results related to monophonic convexity._ Discrete Appl. Math. 158 (12) (2010), 1268-1274.
  * [15] Dudeney, H.E., _Amusements in mathematics._ Nelson, Edinburgh (1917).
  * [16] Ghorbani, M., Maimani, H.R., Momeni, M., Mahid, F.R., Klavžar, S. & Rus, G., _The general position problem on Kneser graphs and on some graph operations._ Discuss. Math. Graph T. 41 (4) (2019), 1199-1213.
  * [17] Hall, P., _On Representatives of subsets._ J. London Math. Soc., 10.1 (1935), 26-30.
  * [18] Howorka, E., _A characterization of distance-hereditary graphs._ Q. J. Math. 28 (4) (1977), 417-420.
  * [19] Howorka, E., _A characterization of Ptolemaic graphs._ J. Graph Theory 5 (3) (1981), 323-331.
  * [20] Hernando, C., Mora, M., Pelayo, I. & Seara, C., _On monophonic sets in graphs._ Discrete Math., submitted (2003).
  * [21] Karp, R.M., _Reducibility Among Combinatorial Problems._ In Complexity of Computer Computations (1972), 85-103.
  * [22] Klavžar, S., Kuziak, D., Peterin. I. & Yero, I.G., _A Steiner general position problem in graph theory._ Comput. Appl. Math. 40 (6) (2021), 1-15.
  * [23] Klavžar, S., Rall, D.F. & Yero, I.G., _General $d$-position sets._ Ars Math. Contemp. 21 (1) (2021), 1-03.
  * [24] Klavžar, S. and Yero, I.G., _The general position problem and strong resolving graphs._ Open Math. 17 (1) (2019), 1126-1135.
  * [25] Manuel, P. & Klavžar, S., _A general position problem in graph theory._ Bull. Aust. Math. Soc. 98 (2) (2018), 177-187.
  * [26] Manuel, P. & Klavžar, S. _The graph theory general position problem on some interconnection networks._ Fundam. Inform. 163 (4) (2018), 339-350.
  * [27] Neethu, P.K., Chandran S.V., U., Changat, M. & Klavžar, S., _On the general position number of complementary prisms._ Fundam. Inform. 178 (3) (2021), 267-281.
  * [28] Patkós, B., _On the general position problem on Kneser graphs._ Ars Math. Contemp. 18 (2) (2020), 273-280.
  * [29] Pelayo, I.M., _Geodesic convexity in graphs._ New York: Springer (2013).
  * [30] Thomas, E.J. & Chandran S.V., U., _Characterization of classes of graphs with large general position number._ AKCE Int. J. Graphs Comb. (2020), 1-5.
  * [31] Thomas, E.J. & Chandran S.V., U., _On independent position sets in graphs._ Proyecciones (Antofagasta) 40 (2) (2021), 385-398.