# On the General Position Number of Mycielskian 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 for graphs was inspired by the no-three-in-line
problem and the general position subset selection problem from discrete
geometry. A set $S$ of vertices of a graph $G$ is a _general position set_ if
no shortest path between two vertices of $S$ contains a third element of $S$;
the general position number of $G$ is the size of a largest general position
set. In this note we investigate the general position numbers of the
Mycielskian of graphs, which are of interest in chromatic graph theory. We
give tight upper and lower bounds on the general position number of the
Mycielskian of a graph $G$ and investigate the structure of the graphs meeting
these bounds. We determine this number exactly for common classes of graphs
including cubic graphs and a wide range of trees.

###### keywords:

Mycielskian graph , general position set , general position number

###### MSC:

05C12 , 05C69

††journal:

##  1 Introduction

A _graph_ $G$ consists of a set of _vertices_ $V(G)$ connected by _edges_ ,
which are unordered pairs of vertices. All graphs used here are undirected,
simple and finite. For any subsets $V_{1},V_{2}\subseteq V(G)$ we will denote
the set of edges of $G$ from $V_{1}$ to $V_{2}$ in $G$ by $(V_{1},V_{2})$. A
_path_ of length $\ell$ in $G$ is a sequence $v_{0},v_{1},\dots,v_{\ell}$ of
distinct vertices such that $v_{i}v_{i+1}$ is an edge for $0\leq i\leq\ell-1$;
we will denote a path of length $\ell$ by $P_{\ell+1}$. A cycle $C_{\ell}$ of
length $\ell$ is a sequence of vertices $v_{0},v_{1},\dots,v_{\ell-1}$ such
that $v_{i}\sim v_{i+1}$ for $0\leq i\leq\ell-2$ and also $v_{0}\sim
v_{\ell-1}$. The _distance_ $d(u,v)$ between vertices $u$ and $v$ of $G$ is
the length of a shortest path from $u$ to $v$; a shortest path from $u$ to $v$
is also called a _$u,v$ -geodesic_. The _girth_ $g(G)$ of $G$ is the length of
a shortest cycle in $G$; if $G$ is acyclic, then we set $g(G)=\infty$. An
independent set in $G$ is a set of mutually non-adjacent vertices, i.e. a set
of vertices that induces an empty subgraph of $G$; the order $\alpha(G)$ of a
largest independent set in $G$ is the _independence number_ of $G$. A
_matching_ $M$ in $G$ is an independent set of edges, i.e. if $e_{1},e_{2}$
are two distinct edges of $M$, then $e_{1}$ and $e_{2}$ do not have an
endvertex in common; the size of the largest matching in $G$ is the _matching
number_ of $G$ and is denoted by $\nu(G)$. A _leaf_ of $G$ is a vertex with
degree one in $G$ and we define the _leaf number_ $\ell(G)$ to be the number
of leaves in $G$. If $U\subseteq V$ is a set of vertices of $G$, then the
subgraph induced by $U$ will be written $\langle U\rangle$. A vertex of degree
$n-1$ in a graph with order $n$ is _universal_. For all other graph-
theoretical terminology we take [5] as our standard.

The _general position problem_ originated in Dudeney’s well-known no-three-in-
line problem and the general position subset selection problem from discrete
geometry [8, 10, 15]. The general position problem was generalised to graph
theory in a natural manner in [12] (and independently in [6] using different
terminology) as follows. A set $S$ of vertices in a graph $G$ is a _general
position set_ , or is in _general position_ , if there are no three distinct
vertices $u,v,w\in S$ such that $w$ lies on a $u,v$-geodesic in $G$. A general
position set of $G$ of largest cardinality is called a _gp-set_ and its size
${\rm gp}(G)$ is the _general position number_ of $G$ (or _gp-number_ for
short). Recent developments on the general position numbers of graphs can be
seen in [2, 14, 17].

In this note we discuss the general position numbers of an important graph
construction from chromatic graph theory. For a graph $G=(V,E)$, the
Mycielskian of $G$ is the graph $\mu(G)$ with vertex set $V\cup
V^{\prime}\cup\\{u^{*}\\}$ where $V^{\prime}=\\{u^{\prime}:u\in V\\}$, and
edge set $E\cup\\{uv^{\prime}:uv\in E\\}\cup\\{v^{\prime}u^{*}:v^{\prime}\in
V^{\prime}\\}$. The vertex $u^{\prime}$ is called the _twin_ of $u$ (and
conversely $u$ is also the twin of $u^{\prime}$) and the vertex $u^{*}$ is
called the _root_ of $\mu(G)$. For any set $X=\\{x_{1},x_{2},\dots,x_{t}\\}$
of vertices of $G$ we denote the set of twins of the vertices in $X$ by
$X^{\prime}=\\{x_{1}^{\prime},x_{2}^{\prime},\dots,x_{t}^{\prime}\\}$. The
Mycielskian graph of $P_{8}$ is shown in Figure 1.1 and the Mycielskian of the
cycle $C_{5}$ in Figure 4.2.

$u_{0}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$$u_{7}$$u_{8}$$u_{0}^{\prime}$$u_{1}^{\prime}$$u_{2}^{\prime}$$u_{3}^{\prime}$$u_{4}^{\prime}$$u_{5}^{\prime}$$u_{6}^{\prime}$$u_{7}^{\prime}$$u_{8}^{\prime}$$u^{*}$
Figure 1.1: The Mycielskian of a path of length eight

This construction was introduced by Mycielski in [13] in order to construct
triangle-free graphs and arbitrarily large chromatic number. As a construction
of independent interest, several other graph parameters of the Mycielskian
construction have been investigated, for example dominator colouring number
[1], connectivity [3], energy [4], $L(2,1)$-labelling number [7], circular
chromatic number [9], Gromov hyperbolicity [11], wide diameter [16] and
Italian domination number [19], amongst many others.

In this note we study the general position number of the Mycielskian of a
graph. In Section 2 we show that for any non-complete graph $G$ there exists a
gp-set of $\mu(G)$ that does not contain the root vertex $u^{*}$. In Section 3
we derive a tight upper bound for the general position number of $\mu(G)$ in
terms of the order and independence number of $G$ and give exact results for
some common families of graphs. Section 4 gives a bound on the gp-number of
the Mycielskian of regular graphs, which we use to classify the gp-numbers of
cubic graphs and all sufficiently large regular graphs. Finally in Section 5
we determine the gp-numbers of the Mycielskians of a wide class of trees.

##  2 General position in the Mycielskian of complete graphs

To begin our study of the gp-numbers of Mycielskian graphs, we first give the
following result concerning the existence of gp-sets in Mycielskian graphs
that contain the root vertex $u^{*}$ of $\mu(G)$.

######  Lemma 1.

Let $G=(V,E)$ be a graph with order $n\geq 3$ and no isolated vertices. Then
the root vertex $u^{*}$ of $\mu(G)$ belongs to every gp-set of $\mu(G)$ if and
only if $G$ is isomorphic to $K_{n}$.

###### Proof.

First suppose that $G$ is a complete graph. Then the set $V\cup\\{u^{*}\\}$ is
a general position set of $\mu(K_{n})$ of size $n+1$, and so ${\rm
gp}(\mu(K_{n}))\geq n+1$. Let $S$ be a gp-set of $\mu(K_{n})$ and assume for a
contradiction that $u^{*}\not\in S$. If there is no vertex $u$ of $G$ such
that both $u$ and its twin $u^{\prime}$ are contained in $S$, then we would
have $|S|\leq n$, a contradiction; therefore assume that
$\\{u,u^{\prime}\\}\subseteq S$. Let $v\in V\setminus\\{u\\}$. Then
$u,v,u^{\prime}$ is a geodesic in $S$ and so $v\not\in S$; since $|S|\geq
n+1$, we must have $S=V^{\prime}\cup\\{u\\}$. As $n\geq 3$, there are vertices
$v,w\in V\setminus\\{u\\}$ and $v^{\prime},u,w^{\prime}$ is a geodesic in
$\mu(G)$ containing three points of $S$, which is impossible. Therefore we
must have $u^{*}\in S$. If a vertex of $V^{\prime}$, say $u^{\prime}$, lies in
$S$, then for any $v\not=u$ the paths $v,u^{\prime},u^{*}$ and
$u^{\prime},u^{*},v^{\prime}$ are geodesics, which would imply that $|S|\leq
3$, which is too small; therefore $V\cup\\{u^{*}\\}$ is the unique gp-set of
$\mu(K_{n})$.

Conversely, suppose that every gp-set of $\mu(G)$ contains $u^{*}$ and assume
for a contradiction that $G$ is non-complete. We must have ${\rm
gp}(\mu(G))\geq n+1$, for otherwise $V^{\prime}$ would be a gp-set not
containing $u^{*}$. Let $S$ be any gp-set of $\mu(G)$ and suppose that there
is a vertex $u$ of $G$ such that $u^{\prime}\in S$. As $u^{*}\in S$, no vertex
of $V^{\prime}\setminus\\{u^{\prime}\\}$ is contained in $S$. Furthermore, if
$u\sim v$ in $G$ then $v,u^{\prime},u^{*}$ is a geodesic in $\mu(G)$, so
$S\cap N_{G}(u)=\emptyset$. Thus $n+1\leq|S|\leq n+2-d_{G}(u)$. There are no
isolated vertices in $G$ and hence we conclude that $|S|={\rm gp}(\mu(G))=n+1$
and $u$ is a leaf of $G$. Let the neighbour of $u$ in $G$ be $v$. All vertices
of $V\setminus\\{v\\}$ lie in $S$; in particular the subgraph of $G$ induced
by $V\setminus\\{u,v\\}$ must be a clique. There is a path of length three
from $u^{\prime}$ to any vertex of $V\setminus\\{u,v\\}$ via $u^{*}$. As any
such path cannot be a geodesic and there is no edge from $u^{\prime}$ to
$V\setminus\\{u,v\\}$, there must be a path of length two from $u^{\prime}$ to
any vertex $w\in V\setminus\\{u,v\\}$, which implies that $v$ is adjacent in
$G$ to every vertex of $V\setminus\\{u,v\\}$. Hence $G$ is isomorphic to
$K_{n-1}$ with a pendent vertex $u$ attached. However in this case
$V^{\prime}\cup\\{u\\}$ is a gp-set of size $n+1$ not containing $u^{*}$, a
contradiction. Therefore $S=V\cup\\{u^{*}\\}$. As every vertex of $V$ is
contained in $S$, $G$ must be a complete graph. ∎

We record separately the following corollary of the above theorem.

######  Corollary 2.

For any integer $n\geq 3$, ${\rm gp}(\mu(K_{n}))=n+1$ and the unique gp-set of
$\mu(K_{n})$ is $V\cup\\{u^{*}\\}$.

Notice that Mycielskian of $K_{2}$ is the cycle $C_{5}$. Thus ${\rm
gp}(\mu(K_{n}))=n+1$ also holds for $n=2$, although the gp-set is no longer
unique.

##  3 General position sets in Mycielskian graphs

Thanks to Lemma 1, we can now confine our attention to non-complete graphs and
assume that there is a gp-set of $\mu(G)$ that does not contain the root
$u^{*}$. In this section we present sharp upper and lower bounds on the
general position number of the Mycielskian of a graph. First we observe the
connection between shortest paths in the base graph $G$ and the shortest paths
in the Mycielskian $\mu(G)$.

######  Definition 3.

The _projection_ of a path $P=u_{0},u_{1},\dots,u_{\ell}$ in
$V(\mu(G))\setminus\\{u^{*}\\}$ is the path with all vertices of $P$ that lie
in $V^{\prime}$ replaced by the corresponding twin vertices in $V$. For
example in Figure 1.1 the projection of the path
$u_{0},u_{1}^{\prime},u_{2},u_{3},u_{4}^{\prime}$ is
$u_{0},u_{1},u_{2},u_{3},u_{4}$. If $Q$ is a path in $V(G)$, then an
_expansion_ of $Q$ is any path in $\mu(G)$ with projection equal to $Q$.

######  Observation 4.

If $u,v\in V(G)$ and $d_{G}(u,v)\leq 3$, then a $u,v$-path in $\mu(G)$ is a
shortest path in $\mu(G)$ if and only if it is an expansion of a shortest path
in $G$. If $d_{G}(u,v)\geq 4$ and $P$ is a shortest $u,v$-path in $\mu(G)$,
then either $d_{G}(u,v)=4$ and $P$ is an expansion of a $u,v$-path of length
four in $G$, or else $P$ has the form
$u,w^{\prime}_{1},u^{*},w^{\prime}_{2},v$, where $u\sim w_{1}$ and $v\sim
w_{2}$ in $G$. If $u\not=v$, then the $u,v^{\prime}$-geodesics in $\mu(G)$ are
either expansions of $u,v$-geodesics in $G$ or have the form
$u,w^{\prime},u^{*},v^{\prime}$, where $u\sim w$ in $G$.

This observation concerning shortest paths in $\mu(G)$ allows us to give a
characterisation of the gp-sets in $\mu(G)$ in terms of an associated
partition of the vertex set of $G$. Lemma 1 shows that for any non-complete
graph $G$ there exists a gp-set $S$ of $\mu(G)$ that does not contain the root
vertex $u^{*}$ of $\mu(G)$; with any such gp-set we can associate a partition
$\pi(G)=(V_{1},V_{2},V_{3},V_{4})$ of $V(G)$ into four (possibly empty) parts
by setting $V_{1}=\\{u\in V(G):u,u^{\prime}\in S\\}$, $V_{2}=\\{u\in
V(G):u^{\prime}\in S,u\not\in S\\}$, $V_{3}=\\{u\in V(G):u^{\prime}\not\in
S,u\in S\\}$ and $V_{4}=\\{u\in V(G):u,u^{\prime}\not\in S\\}$. If we let
$n_{i}=|V_{i}|$ for $i=1,2,3,4$, then we have ${\rm
gp}(\mu(G))=n+n_{1}-n_{4}$. This motivates the following definition.

######  Definition 5.

A partition $\pi(G)=(V_{1},V_{2},V_{3},V_{4})$ of $V(G)$ into four (possibly
empty) sets is a _Mycielski partition_ if and only if it satisfies the
following conditions:

  1. 1.

if $e$ is an edge in $\langle V_{1}\cup V_{3}\rangle$, then $e$ has both
endpoints in $V_{3}$,

  2. 2.

if a vertex $u$ in $V_{1}\cup V_{3}$ has a neighbour $v$ in $V_{2}$, then
$d(u,w)=2$ for all $w\in(V_{1}\cup V_{2})\setminus\\{u,v\\}$ and $d(u,w)\leq
3$ for all $w\in V_{3}\setminus\\{u\\}$, and

  3. 3.

if $u,v\in V_{1}\cup V_{2}\cup V_{3}$ and $P$ is a shortest $u,v$-path in $G$
with length $\ell(P)\leq 4$ and $P$ passes through another point of $V_{1}\cup
V_{2}\cup V_{3}$, then either $u,v\in V_{2}$ and $\ell(P)\geq 3$, or else
either $P$ or the reverse of $P$ has one of the following forms: i)
$u_{0},u_{1},u_{2},u_{3},u_{4}$, where $u_{0}\in V_{2}$ and $u_{4}\in
V_{1}\cup V_{3}$ and $u_{3}\not\in V_{1}\cup V_{2}$, ii)
$u_{0},u_{1},u_{2},u_{3}$, where $u_{0},u_{1}\in V_{2}$ and $u_{3}\in
V_{1}\cup V_{3}$ or iii) $u_{0},u_{1},u_{2}$, where $u_{0},u_{1}\in V_{2}$.

We note the following three important consequences of the conditions in
Definition 5.

######  Lemma 6.

If $(V_{1},V_{2},V_{3},V_{4})$ is a Mycielski partition of $G$, then $V_{1}$
is an independent set of $G$, $(V_{1},V_{3})=\emptyset$ and $(V_{1},V_{2})$ is
a matching.

###### Proof.

That $V_{1}$ is independent and $(V_{1},V_{3})=\emptyset$ follows immediately
from Condition 1 in Definition 5. We now show that $(V_{1},V_{2})$ is a
matching. By Condition 2 of Definition 5 a vertex $u\in V_{1}$ can be at
distance one from at most one vertex of $V_{2}$, so each vertex of $V_{1}$ has
at most one neighbour in $V_{2}$. Suppose now that there is a vertex $w\in
V_{2}$ with distinct neighbours $u,v\in V_{1}$; as $V_{1}$ is independent,
$u,w,v$ would be a shortest path in $G$ of the form forbidden by Condition 3.
It follows that the edges in $(V_{1},V_{2})$ are independent. ∎

We now complete our characterisation of gp-sets of Mycielskians. We use the
following convention: given a set $S$ of vertices of a graph, we will call a
geodesic containing at most two points of $S$ _sound_ and a shortest path
containing at least three points of $S$ _unsound_.

######  Theorem 7.

Let $G$ be a non-complete graph with order $n$. For $1\leq i\leq 4$ set
$n_{i}=|V_{i}|$. Then ${\rm gp}(\mu(G))$ is the largest value of
$n+n_{1}-n_{4}$ over all Mycielski partitions of $G$.

###### Proof.

Let $\pi(G)=(V_{1},V_{2},V_{3},V_{4})$ be a Mycielski partition of $G$ and
consider the set $S=V_{1}\cup V_{1}^{\prime}\cup V_{2}^{\prime}\cup V_{3}$; we
will show that this set is in general position in $\mu(G)$ so that ${\rm
gp}(\mu(G))\geq n+n_{1}-n_{4}$. We need to verify that all geodesics $P(u,v)$
in $\mu(G)$ are sound.

First let $u,v\in V_{1}\cup V_{3}$. By Condition 3 of Definition 5 no
expansion of a $u,v$-geodesic with length $\leq 4$ of $G$ contains a third
point of $S$. Furthermore if $d_{G}(u,v)\geq 4$ then by Observation 4 the only
other geodesics to consider are the paths of the form
$u,w^{\prime}_{1},u^{*},w^{\prime}_{2},v$, where $u\sim w_{1}$ and $v\sim
w_{2}$ in $G$. Neither of the vertices $w_{1},w_{2}$ can lie in $V_{2}$; if
say $w_{1}\in V_{2}$, then by Condition 2 of Definition 5 we would have
$d_{G}(u,v)\leq 3$, so that $u,w^{\prime}_{1},u^{*},w^{\prime}_{2},v$ would
not be a shortest path. Hence this path will only fail to be sound if either
$w_{1}$ or $w_{2}$ is in $V_{1}$; however Condition 1 shows that this is not
the case, so these paths are also sound.

Now suppose that $u^{\prime},v^{\prime}\in V_{1}^{\prime}\cup V_{2}^{\prime}$.
A geodesic $P(u^{\prime},v^{\prime})$ in $\mu(G)$ has length two and $P$ is
unsound only if it passes through a common neighbour of $u$ and $v$ in
$V_{1}\cup V_{3}$; by Condition 2 and Lemma 6 this is impossible. We can thus
assume that any unsound geodesic $P$ has one endpoint in $V_{1}\cup V_{3}$ and
the other in $V_{1}^{\prime}\cup V_{2}^{\prime}$. If $u\in V_{1}$, the
$u,u^{\prime}$-geodesics in $\mu(G)$ are the paths $u,w,u^{\prime}$, where
$u\sim w$ in $G$; by Lemma 6 the vertex $w$ does not lie in $S$. Hence we can
assume that the endpoints of $P$ are not twins of each other; let us denote
them by $u,v^{\prime}$, where $u\in V_{1}\cup V_{3}$ and $v\in V_{1}\cup
V_{2}$ and $u\not=v$. By Condition 2 of Definition 5 $P$ cannot have length
two, so by Observation 4 the $u,v^{\prime}$-geodesics in $\mu(G)$ are either
expansions of shortest paths of length three in $G$, or else have the form
$u,w^{\prime},u^{*},v^{\prime}$, where $u\sim w$ in $G$. By Condition 3 the
former geodesics are sound and the latter are sound by Condition 2. This shows
that $S$ is in general position.

Conversely, suppose that $S$ is in general position in $\mu(G)$ and does not
include the root vertex $u^{*}$ and let $\pi(G)=(V_{1},V_{2},V_{3},V_{4})$ be
the partition associated with $S$ as above; we claim that $\pi(G)$ obeys the
conditions of Definition 5, so that $\pi(G)$ is a Mycielski partition. To
verify Condition 1, suppose that there is an edge $u\sim v$ in $\langle
V_{1}\cup V_{3}\rangle$, where $u$ and $v$ do not both lie in $V_{3}$. If
$u,v\in V_{1}$, then the path $u,v,u^{\prime}$ would be unsound. Similarly, if
$u\in V_{1},v\in V_{3}$, then $u,v,v_{1}$ is unsound.

To verify Condition 2, suppose that a vertex $u\in V_{1}$ has a neighbour
$v\in V_{2}$. By Condition 1, $u$ has no neighbours in $V_{1}$. Furthermore if
$u$ had a second neighbour $v_{2}\not=v$ in $V_{2}$, then the path
$v^{\prime},u,v_{2}^{\prime}$ would be unsound. Thus $d(u,w)\geq 2$ for each
$w\in(V_{1}\cup V_{2}\setminus\\{u,v\\}$. Suppose that there is a
$w\in(V_{1}\cup V_{2})\setminus\\{u,v\\}$ such that $d(u,w)\geq 3$; then
$u,v^{\prime},u^{*},w^{\prime}$ would be an unsound geodesic. Therefore
$d(u,w)=2$ for all $w\in(V_{1}\cup V_{2})\setminus\\{u,v\\}$. Also if $w\in
V_{3}$ is such that $d(u,w)\geq 4$, then $u,v^{\prime},u^{*},w_{1}^{\prime},w$
would be an unsound path, where $w_{1}$ is any neighbour of $w$ in $G$. This
proves our statement for edges in $(V_{1},V_{2})$; the argument for edges in
$(V_{2},V_{3})$ is very similar.

Finally we turn to Condition 3. Suppose that $P$ is a geodesic
$u_{0},u_{1},\dots,u_{\ell}$ in $G$ with length $\ell\leq 4$ that has both
endpoints and an internal vertex in $V_{1}\cup V_{2}\cup V_{3}$. If $P$ has
both endpoints in $V_{1}\cup V_{3}$, then $P$ has an unsound expansion that is
a geodesic in $\mu(G)$, so we can assume that the initial vertex $u_{0}$ of
$P$ is in $V_{2}$. Suppose firstly that $\ell=2$; then we must have $u_{1}\in
V_{2}$, for if $u_{1}\in V_{1}\cup V_{3}$, then $u_{0}^{\prime},u_{1},u_{2}$
is unsound if $u_{2}\in V_{1}\cup V_{3}$ and
$u_{0}^{\prime},u_{1},u_{2}^{\prime}$ is unsound if $u_{2}\in V_{2}$. Now
suppose that $P$ has length $\ell\geq 3$ and the terminal vertex $u_{\ell}$
lies in $V_{1}\cup V_{3}$. Let $\ell=3$. As $u_{0}^{\prime},u_{1},u_{2},u_{3}$
and $u_{0}^{\prime},u^{*},u_{2}^{\prime},u_{3}$ are shortest paths in
$\mu(G)$, we see that $u_{1},u_{2}\not\in V_{1}\cup V_{3}$ and $u_{2}\not\in
V_{2}$, so that $P$ must have the form in variant ii) of Condition 3. Lastly,
let $\ell=4$; then $u_{0},u^{*},u_{3}^{\prime},u_{4}$ is a shortest path in
$\mu(G)$, so that $u_{2}\not\in V_{1}\cup V_{2}$. This completes the proof of
the claimed duality between general position sets of $\mu(G)$ and Mycielski
partitions of $G$. ∎

We now use Theorem 7 to derive tight upper and lower bounds for ${\rm
gp}(\mu(G))$. We start with the lower bound.

######  Corollary 8.

If $\alpha_{gp}(G)$ is the size of the largest independent set of $G$ that is
also in general position in $G$, then

${\rm gp}(\mu(G))\geq\max\\{n,2\alpha_{gp}(G)\\}.$

###### Proof.

Let $A$ be a largest subset of $V(G)$ that is both an independent set and is
in general position in $G$. Setting $V_{1}=A$ and $V_{4}=V(G)\setminus A$
gives a Mycielski partition of $G$, yielding ${\rm gp}(\mu(G))\geq
2\alpha_{gp}$ by Theorem 7. The set $V^{\prime}$ is trivially in general
position, implying that ${\rm gp}(\mu(G))\geq n$; this is equivalent to using
the trivial Mycielski partition $V_{2}=V(G)$ in Theorem 7. ∎

We will call any non-complete graph $G$ with order $n$ and ${\rm
gp}(\mu(G))=\max\\{n,2\alpha_{gp}(G)\\}$ _meagre_ ; otherwise $G$ is
_abundant_. We now show that the lower bound in Corollary 8 is tight by
exhibiting two families of meagre graphs: the graphs $K_{n}^{-}$ for $n\geq
4$, i.e. a complete graph with one edge deleted, and the complete multipartite
graphs.

######  Theorem 9.

For $n\geq 4$ we have ${\rm gp}(\mu(K_{n}^{-}))=n$.

###### Proof.

Suppose for a contradiction that ${\rm gp}(\mu(K_{n}^{-}))\geq n+1$ and let
$S$ be a gp-set of $\mu(K_{n}^{-})$ not containing $u^{*}$ with corresponding
Mycielski partition $(V_{1},V_{2},V_{3},V_{4})$. By Lemma 6, $V_{1}$ is an
independent set; as $\alpha(K_{n}^{-})=2$, this shows that $n_{1}\leq 2$. By
the same lemma, $(V_{1},V_{3})=\emptyset$; since there is just one edge
missing in $K_{n}^{-}$, it follows that if $n_{1}=1$, then $n_{3}\leq 1$ and
if $n_{1}=2$, then $n_{3}=0$.

Suppose firstly that $n_{1}=1$ and $n_{4}=0$. Let $V_{1}=\\{u\\}$. If
$n_{3}=1$, then the missing edge in $K_{n}^{-}$ must be between $V_{1}$ and
$V_{3}$. Thus $u$ is adjacent to every vertex of $V_{2}$. The edge set
$(V_{1},V_{2})$ is a matching, so $n_{2}=1$ and $n=3$, which is too small. If
$n_{3}=0$, then for the same reason we would have $n\leq 3$.

Now suppose that $n_{1}=2$ and $n_{4}\leq 1$. The only missing edge of
$K_{n}^{-}$ is accounted for by the independent set $V_{1}$, so we must have
$V_{3}=\emptyset$ and as $(V_{1},V_{2})$ is a matching we also have
$V_{2}=\emptyset$. However, this again implies that $n\leq 3$, a
contradiction. ∎

######  Theorem 10.

Let $K_{r_{1},r_{2},\dots,r_{k}}$ be a complete $k$-partite graph, where
$2\leq k<n$ and $r_{1}\geq r_{2}\geq\dots\geq r_{k}$. Then

${\rm gp}(\mu(K_{r_{1},r_{2},\dots,r_{k}}))=\max\\{n,2r_{1}\\}.$

###### Proof.

Suppose that ${\rm gp}(\mu(K_{r_{1},r_{2},\dots,r_{k}}))\geq n+1$, where
$n=r_{1}+r_{2}+\dots+r_{k}$. Then $n_{1}\geq 1$ and as $V_{1}$ is an
independent set it must be contained entirely within one of the partite sets
of $K_{r_{1},r_{2},\dots,r_{k}}$; call this partite set $X$. By Theorem 7
there are no edges from $V_{1}$ to $V_{3}$, so we have $V_{1}\cup
V_{3}\subseteq X$. If $V_{2}$ lies entirely in $X$, then ${\rm
gp}(\mu(K_{r_{1},r_{2},\dots,r_{k}}))\leq
2r_{1}=\alpha(K_{r_{1},r_{2},\dots,r_{k}})$, so assume that there is a vertex
$y\in V_{2}\setminus X$. Then the vertex $y$ is adjacent to every vertex of
$X$; as $(V_{1},V_{2})$ is a matching by Lemma 6, we must have $n_{1}=n_{2}=1$
and hence $n_{4}=0$. As $V_{3}\subset X$, $y$ is also adjacent to every vertex
of $V_{3}$. If $V_{3}\not=\emptyset$, then as $(V_{1},V_{3})=\emptyset$ the
shortest path from the sole vertex of $V_{1}$ to the vertices of $V_{3}$ has
length two and passes through $y$, violating Condition 3 of the Definition 5.

Now suppose that there exists a vertex $y$ in $V_{2}$ that belongs to a
different partite set of $K_{r_{1},r_{2},\dots,r_{k}}$. Then if $x\in V_{1}$
and $z\in V_{3}$ the path $x\sim y^{\prime}\sim z$ would be a geodesic in
$\mu(K_{r_{1},r_{2},\dots,r_{k}})$ and hence $V_{3}=\emptyset$; however, as
the resulting graph has order two, this contradicts $k<n$. It follows that the
graph is meagre. ∎

We will see other examples of meagre graphs: all cycles apart from $C_{3}$ and
$C_{5}$ (Theorem 15), all cubic graph with two exceptions (Theorem 16) and
paths (Lemma 22). It also follows from Corollary 11 below that for $n\geq 2$
the star graph $S_{n}$ (a tree of order $n$ with a universal vertex) is meagre
(in fact for this graph the bounds in Corollaries 8 and 11 coincide). We now
derive a tight upper bound on ${\rm gp}(\mu(G))$ in terms of the independence
number $\alpha(G)$.

######  Corollary 11.

For any non-complete graph $G$ with order $n$, independence number $\alpha$
and minimum degree $\delta\geq 1$ we have

${\rm gp}(\mu(G))\leq n+\max\\{0,\alpha-\delta+1\\}.$ (1)

This bound is sharp for $\delta\geq 2$. Moreover for any non-complete graphs
we have ${\rm gp}(\mu(G))\leq n+\alpha-1$.

###### Proof.

Let $(V_{1},V_{2},V_{3},V_{4})$ be the Mycielski partition associated with a
gp-set $S$ of $G$. If $V_{1}$ is empty, then ${\rm gp}(\mu(G))\leq n$, so
assume that $V_{1}\not=\emptyset$. By Lemma 6 any vertex $u\in V_{1}$ has at
most one neighbour in $V_{2}$ and no neighbours in $(V_{1}\cup
V_{3})\setminus\\{u\\}$; thus $u$ has at least $d(u)-1$ neighbours in $V_{4}$,
so that $n_{4}\geq d(u)-1\geq\delta-1$. $V_{1}$ is an independent set, so by
Theorem 7 we have ${\rm gp}(\mu(G))=n+n_{1}-n_{4}\leq n+\alpha-\delta+1$.
Furthermore this argument shows that if a graph meets this bound, then $V_{1}$
is a maximum independent set. This shows that every vertex of $V(G)\setminus
V_{1}$ has a neighbour in $V_{1}$ and so it follows from Lemma 6 that
$V_{3}=\emptyset$. Furthermore since $n_{4}=\delta-1$, we have that each
vertex in $V_{1}$ has degree $\delta$. This in turn implies that the matching
$(V_{1},V_{2})$ saturates $V_{1}$. Again since $V_{1}$ is a maximum
independent set, we have that the matching $(V_{1},V_{2})$ also saturates
$V_{2}$.

Now, let $u_{1},u_{2}\in V_{1}$; then it follows from the definition of
Mycielski partition that $u_{1}$ and $u_{2}$ have a common neighbour in
$V_{4}$, so that we must have $\delta\geq 2$ and so ${\rm gp}(\mu(G))\leq
n+\alpha-1$. On the other hand if $G$ has a leaf, then the above arguments
shows that ${\rm gp}(\mu(G))<n+\alpha-\delta+1=n+\alpha$. For $\delta\geq 2$
the graph $\alpha K_{2}\vee K_{\delta-1}$ meets the bound. ∎

We now characterise the graphs that meet this upper bound.

######  Theorem 12.

A non-complete graph $G$ with order $n$ and no isolated vertices has ${\rm
gp}(\mu(G))=n+\alpha(G)-1$ if and only if it is isomorphic to either i) a
clique $K_{n-1}$ with a leaf attached or ii) a star, or else $V(G)$ can be
partitioned into four sets $V_{1,1}$, $V_{1,2}$, $V_{2}$ and $\\{x\\}$ with
the following properties:

  * 1.

$V_{1,1}\cup V_{1,2}$ is an independent set,

  * 2.

each vertex of $V_{1,1}$ is a leaf attached to $x$,

  * 3.

$x$ is adjacent to every vertex of $V_{1,2}$,

  * 4.

$(V_{1,2},V_{2})$ is a matching of size $\geq 1$ that saturates both $V_{1,2}$
and $V_{2}$,

  * 5.

if $V_{1,1}\not=\emptyset$, then $x$ is a universal vertex of $G$, whilst if
$V_{1,1}=\emptyset$, then $x$ is adjacent to every vertex $w\in V_{2}$ that is
not adjacent to every other vertex of $V_{2}$.

A corresponding Mycielski partition is $(V_{1,1}\cup
V_{1,2},V_{2},\emptyset,\\{x\\})$. Examples of these graphs are given in
Figure 3.1.

###### Proof.

Let $G$ be a non-complete graph with no isolated vertices such that ${\rm
gp}(\mu(G))=n+\alpha(G)-1$. Let $S$ be a gp-set of $\mu(G)$ not containing
$u^{*}$ with associated Mycielski partition $(V_{1},V_{2},V_{3},V_{4})$. By
Theorem 7 we have either $n_{1}=\alpha(G)-1$ and $n_{4}=0$, or else $V_{1}$ is
a maximum independent set and $n_{4}=1$.

Suppose that $n_{1}=\alpha(G)-1$ and $n_{4}=0$. As $G$ has no isolated
vertices, each of the vertices in $V_{1}$ has an edge to $V_{2}$, so it
follows by Definition 5 that all vertices in $V_{1}$ are leaves of $G$ and are
connected by a matching to $V_{2}$. By Condition 2 of Definition 5 the
vertices of $V_{1}$ must lie at distance two from each other; observing that
no vertices of $V_{1}$ have a common neighbour in this case, it follows that
$n_{1}=1$ and $\alpha(G)=2$. Let $V_{1}=\\{u\\}$ and $v$ be the neighbour of
$u$ in $V_{2}$. As $G$ has independence number two, $(V_{2}\cup
V_{3})\setminus\\{v\\}$ induces a clique. By Condition 2 of Definition 5 $u$
is at distance two from every vertex of $V_{2}\setminus\\{v\\}$ and so $v$ has
an edge to every vertex of $V_{2}\setminus\\{v\\}$, so that $V_{2}$ induces a
clique. Suppose that $V_{3}\not=\emptyset$. By Definition 5 $u$ is at distance
at most three from the vertices of $V_{3}$, so there is an edge from $V_{2}$
to $V_{3}$, which implies by Definition 5 that $d(u,w)=2$ for each $w\in
V_{3}$, so that $v$ is adjacent to each vertex of $V_{3}$; however in this
case for any $w\in V_{3}$ $u,v^{\prime},w$ is an unsound path forbidden by
Condition 3 of Definition 5. Thus $V_{3}=\emptyset$ and $G$ is isomorphic to a
leaf added to an $(n-1)$-clique. Conversely $V_{1}=\\{u\\},V_{2}=V(K_{n-1})$
is a Mycielski partition by Definition 5.

Otherwise we have $n_{1}=\alpha$ and $n_{4}=1$. Let $V_{4}=\\{x\\}$. As
$V_{1}$ is a maximum independent set, every vertex in $V\setminus V_{1}$ has
an edge to $V_{1}$; in particular, by Lemma 6 we have $V_{3}=\emptyset$ and
the matching $(V_{1},V_{2})$ saturates $V_{2}$. Let $V_{1,1}$ be the subset of
vertices of $V_{1}$ with no edge to $V_{2}$ and $V_{1,2}$ be the subset of
vertices of $V_{2}$ with edges to $V_{2}$. Hence $|V_{1,2}|=n_{2}$ and each
vertex of $V_{1,1}$ is a leaf adjacent to $x$. If $V_{1,2}=\emptyset$, then
$G$ is isomorphic to a star and setting $V_{1}$ as the set of leaves and
$V_{4}$ as the central vertex gives a Mycielski partition. Hence we assume
that $n_{2}\geq 1$. Label $V_{1,2}=\\{u_{1},u_{2},\dots,u_{n_{2}}\\}$ and
$V_{2}=\\{v_{1},\dots,v_{n_{2}}\\}$ such that $u_{i}\sim v_{i}$ for $1\leq
i\leq n_{2}$. Suppose that $V_{1,1}\not=\emptyset$; then for any $u\in
V_{1,1}$ the path $u,x,u_{i},v_{i}^{\prime}$ cannot be a shortest path by
Condition 3 of Definition 5, so that $x$ must be adjacent to each vertex of
$V_{2}$ and hence is universal (and by Theorem 7 the corresponding partition
is Mycielski). Thus assume that $V_{1,1}=\emptyset$ and suppose that a vertex
$v_{i}\in V_{2}$ is not universal in $\langle V_{2}\rangle$. Let $v_{j}\in
V_{2}$ be such that $v_{i}\not\sim v_{j}$ in $G$; as
$u_{i},x,u_{j},v_{j}^{\prime}$ is not a shortest path by Condition 3 of
Definition 5 we must have $x\sim v_{i}$. If $x$ is adjacent to every vertex of
$V_{2}$ that is not universal in $\langle V_{2}\rangle$, then the partition is
Mycielski. ∎

Figure 3.1: Two graphs with ${\rm gp}(\mu(G))=n+\alpha-1$.

##  4 Regular graphs

It was indicated in the previous section that the regular graphs provide a
rich source of meagre graphs. In this section we will see that there is a
strong natural upper bound on ${\rm gp}(\mu(G))$ for regular graphs $G$ and
that for any $d$ there are at most finitely many abundant $d$-regular graphs.

######  Theorem 13.

If $G$ is a $d$-regular graph, then

${\rm gp}(\mu(G))\leq n+\frac{d-1}{2}+\frac{1}{d}.$

###### Proof.

Let $G$ be a $d$-regular graph and let $S$ be a gp-set of $G$ that does not
include $u^{*}$. Suppose that $(V_{1},V_{2})=\emptyset$; then all neighbours
of vertices in $V_{1}$ lie in $V_{4}$ and we must have $n_{4}d\geq n_{1}d$,
yielding $n_{4}\geq n_{1}$, so that ${\rm gp}(\mu(G))=n$.

Hence we may assume that $|(V_{1},V_{2})|=r>0$. As $(V_{1},V_{2})$ is a
matching, there are $n_{1}d-r$ edges in $(V_{1},V_{4})$, implying that
$n_{4}\geq n_{1}-\frac{r}{d}$ and thus

${\rm gp}(\mu(G))=n+n_{1}-n_{4}\leq n+\frac{r}{d}.$

By Theorem 7 if $u\in V_{1}$ has an edge to a vertex $v\in V_{2}$, then all
vertices of $V_{1}\cup V_{2}\setminus\\{u,v\\}$ lie in $N^{2}(u)$. There are
at least $2r$ vertices in $V_{1}\cup V_{2}$ and at most $d^{2}-d$ vertices in
$N^{2}(u)$ and so $2r-2\leq d^{2}-d$. It follows that

${\rm gp}(\mu(G))\leq n+\frac{d-1}{2}+\frac{1}{d}.$

In particular, for $d\geq 3$ we have ${\rm gp}(\mu(G))\leq n+\frac{d-1}{2}$. ∎

Theorem 13 suggests the following construction of abundant regular graphs.

######  Theorem 14.

For all $d\geq 2$ there is a $d$-regular graph $G(d)$ with order $n=3d-1$ and
${\rm gp}(\mu(G(d)))=n+1$.

###### Proof.

We form the graph $G(d)$ as follows. Take three sets $V_{1},V_{2},V_{4}$ of
vertices, where $|V_{1}|=|V_{2}|=d$ and $|V_{4}|=d-1$. Draw the complete
bipartite graph $K_{d,d-1}$ with partite sets $V_{1}$ and $V_{4}$. Make
$V_{2}$ into a copy of $K_{d}$ by adding every possible edge between members
of $V_{2}$. Finally join $V_{1}$ and $V_{2}$ by a matching of size $d$. The
graph $G(5)$ is shown in Figure 4.1. As suggested by our labelling of the
sets, $(V_{1},V_{2},\emptyset,V_{4})$ is a Mycielski partition of $G(d)$. As
$\alpha(G(d))=d$ these graphs are abundant.

Figure 4.1: A 5-regular graph $G$ with ${\rm gp}(\mu(G))=n+1$

∎

We now classify the abundant $2$\- and $3$-regular graphs. It turns out that
the graphs $G(2)$ and $G(3)$ are the only abundant regular graphs with degree
$\leq 3$.

######  Theorem 15.

For $n\geq 3$ the Mycielskian of the cycle $C_{n}$ has general position number

${\rm gp}(\mu(C_{n}))={\begin{cases}n+1,&\text{ if }n=3\text{ or }5\\\
n,&\text{ otherwise.}\end{cases}}$

###### Proof.

The result for $n=3$ follows from Corollary 2. For $n\geq 4$ let $S$ be a gp-
set of $\mu(C_{n})$ that does not include $u^{*}$ and consider the
corresponding Mycielski partition $(V_{1},V_{2},V_{3},V_{4})$ of $V(C_{n})$.
Suppose that ${\rm gp}(\mu(C_{n}))\geq n+1$. By Theorem 13 we have ${\rm
gp}(\mu(C_{n}))\leq n+1$, so we must have exactly ${\rm gp}(\mu(C_{n}))=n+1$.
As we have equality in the bound of Theorem 13 it follows that the matching
$(V_{1},V_{2})$ has size $r=2$ and $n_{4}=n_{1}-1$. Let $u_{1},u_{2}\in V_{1}$
and $v_{1},v_{2}\in V_{2}$, where $u_{1}\sim v_{1}$, $u_{2}\sim v_{2}$ are the
edges of $(V_{1},V_{2})$ . It follows from Theorem 13 that
$\\{u_{2},v_{2}\\}\subset N^{2}(u_{1})$; as $u_{2}\sim v_{2}$, the cycle has
length at most five, so all cycles with length $n\geq 6$ are meagre. Also as
$u_{1}$ has a neighbour in $V_{4}$ the cycle must contain at least five
vertices, so $C_{4}$ is meagre. However, as can be seen in Figure 4.2, this
argument does yield a gp-set of size six in the Grötzsch graph $\mu(C_{5})$;
notice that $C_{5}$ is isomorphic to $G(2)$ from Theorem 14.

∎

Figure 4.2: A gp-set for $\mu(C_{5})$

######  Theorem 16.

The graph $G(3)$ is the unique non-complete abundant cubic graph.

###### Proof.

Let $G$ be a non-complete cubic graph with order $n$ and ${\rm gp}(\mu(G))\geq
n+1$. Theorem 13 shows that ${\rm gp}(\mu(G))=n+1$ and the matching
$(V_{1},V_{2})$ has size $r=3$ or $4$.

Suppose firstly that $r=4$ and let $u_{i}\sim v_{i}$ for $i=1,2,3,4$ be the
edges of $(V_{1},V_{2})$. By Condition 2 of Definition 5 we have
$\\{u_{2},u_{3},u_{4},v_{2},v_{3},v_{4}\\}\subseteq N^{2}(u_{1})$; as there at
most six vertices in $N^{2}(u_{1})$, it follows that
$\\{u_{2},u_{3},u_{4},v_{2},v_{3},v_{4}\\}=N^{2}(u_{1})$, $n_{1}=n_{2}=4$ and
$n_{4}=3$. Again by Condition 2 of Definition 5 any vertex $w$ of $V_{3}$ lies
in $N^{3}(u)$; however, a shortest $u_{1},w$-path would pass through
$V_{1}\cup V_{2}$, which is forbidden by Condition 3 of Definition 5. Thus
$V_{3}=\emptyset$. However, this implies that $G$ has order
$n=n_{1}+n_{2}+n_{4}=11$, whereas any cubic graph has even order, a
contradiction.

Hence we can assume that $r=3$. Write
$V_{1}=\\{u_{1},u_{2},\dots,u_{n_{1}}\\}$ and
$V_{2}=\\{v_{1},v_{2},\dots,v_{n_{2}}\\}$, where $u_{i}\sim v_{i}$ are the
edges of the matching $(V_{1},V_{2})$ for $i=1,2,3$. We have $n_{1}+n_{2}\leq
8$ and $n_{1},n_{2}\geq r=3$, so that $3\leq n_{1}\leq 5$. If $n_{1}+n_{2}=8$,
then as above by Definition 5 it follows that $N^{2}(u_{1})\subset V_{1}\cup
V_{2}$, so that $V_{3}$ is empty.

Suppose that $n_{1}=5$, so that $n_{2}=3$ and $n_{4}=4$. As $n_{1}+n_{2}=8$,
we have $n_{3}=0$, giving $n=12$. For $i=1,2,3$ we have $V_{1}\cup
V_{2}=\\{u_{i},v_{i}\\}\cup N^{2}(u_{i})$. As each member of $V_{2}$ has one
edge to $V_{1}$, the neighbours of $v_{i}$ at distance two from $u_{i}$ must
both lie in $V_{2}$, so that $V_{2}$ induces a triangle in $G$. Hence
$d(v_{1},u_{4})=3$ and there is a path $v_{1},u_{1},w,u_{4}$, where $w\in
V_{4}$. However there can be no such path by Condition 3 of Definition 5.

Now suppose that $n_{1}=4$. If $n_{2}=4$, then $n_{3}=0$ and $n_{4}=3$, giving
$n=11$, whereas $G$ must have even order, so suppose that $n_{1}=4$ and
$n_{2}=n_{4}=3$. There is just one vertex of $N^{2}(u_{i})$ that does not
belong to $V_{1}\cup V_{2}$ for $i=1,2,3$, so it follows that $n_{3}=0$ or
$2$. If $n_{3}=2$, then, writing $V_{3}=\\{x_{1},x_{2}\\}$ and
$V_{4}=\\{w_{1},w_{2},w_{3}\\}$, we can suppose that $w_{1},w_{2}\in N(u_{1})$
and there is a shortest path $u_{1},w_{2},w_{3}$ and $x_{1},x_{2}\in
N(w_{3})$, giving the configuration shown in Figure 4.3. However, at least one
vertex of $\\{u_{2},u_{3}\\}$ (say $u_{2}$) lies in $N(w_{1})$ and so $u_{2}$
has no edge to $\\{w_{2},w_{3}\\}$ and hence the required path from $u_{2}$ to
the vertices of $V_{3}$ does not exist.

$u_{1}$$w_{1}$$w_{2}$$v_{1}$$u_{2}$$u_{4}$$w_{3}$$u_{3}$$x_{1}$$x_{2}$ Figure
4.3: Configuration for $n_{1}=4,n_{2}=3,n_{3}=2,n_{4}=3$.

Thus suppose that $n_{1}=4$, $n_{2}=n_{4}=3$ and $n_{3}=0$. Then
$|(V_{1},V_{2})|=3$ and hence $|(V_{1},V_{3})|=9$ and every vertex of $V_{4}$
has neighbourhood entirely contained in $V_{1}$; in particular $u_{4}$ is
adjacent to every vertex of $V_{1}$. Hence each vertex of $V_{2}$ must have
one neighbour in $V_{1}$ and two neighbours in $V_{2}$, so $V_{2}$ induces a
triangle. This implies that $G$ is isomorphic to the graph in Figure 4.4;
however, this graph contains a shortest path $v_{1},u_{1},w_{3},u_{4}$,
contradicting Condition 3 in Definition 5.

$u_{4}$$u_{1}$$w_{1}$$u_{2}$$w_{2}$$u_{3}$$w_{3}$$v_{1}$$v_{2}$$v_{3}$ Figure
4.4: Cubic graph for $n_{1}=4,n_{2}=3,n_{3}=0,n_{4}=3$.

Finally, let $n_{1}=n_{2}=3$ and $n_{4}=2$. Then $|(V_{1},V_{4})|=6$, so both
vertices of $V_{4}$ have neighbourhood contained in $V_{1}$; thus
$N(u_{i})=V_{4}\cup\\{v_{i}\\}$ for $i=1,2,3$. For $u_{i}$ to reach each
vertex of $V_{2}$ in distance $\leq 2$, we see that $V_{2}$ must induce a
triangle in $G$, so that $V_{3}=\emptyset$. Hence $G$ is isomorphic to $G(3)$,
completing the proof. ∎

######  Theorem 17.

Any $d$-regular graph with order $\geq d^{3}-2d^{2}+2d+2$ is meagre.

###### Proof.

Let $G$ be an abundant $d$-regular graph. We can assume that
$r=|(V_{1},V_{2})|\geq d>0$. Let $u_{1}\sim v_{1}$ be an edge of the matching
$(V_{1},V_{2})$, where $u_{1}\in V_{1}$, $v_{1}\in V_{2}$. Consider a breadth-
first search tree $T$ of depth three rooted at $u$. By Condition 2 in
Definition 5 all vertices of $(V_{1}\cup V_{2})\setminus\\{u,v\\}$ are
contained in $N^{2}(u)$ and $V_{3}$ is contained in $N^{2}(u)\cup N^{3}(u)$.
There are at most $d^{2}-d$ vertices at distance two from $u_{1}$ and at most
$d(d-1)^{2}$ vertices in $N^{3}(u_{1})$.

Moreover there are at least $2d-2$ vertices of $V_{1}\cup V_{2}$ in $N^{2}(u)$
and no such vertex can have descendants at distance three from $u_{1}$ in
$V_{3}$ by Condition 3 in Definition 5. Therefore we see that

$|V_{1}\cup V_{2}\cup V_{3}|\leq
2+d^{2}-d+[d^{2}-d-(2d-2)](d-1)=d^{3}-3d^{2}+4d.$

As there are at least $d$ vertices of $V_{2}$ and so as $G$ is abundant we
must have

$n_{4}\leq n_{1}-1\leq 1+(d^{2}-d)-(d-1)-1=d^{2}-2d+1.$

In total then the order of $G$ is bounded above by $d^{3}-2d^{2}+2d+1$. ∎

In particular this shows that for any value of $d$ there are only a finite
number of abundant $d$-regular graphs.

##  5 The Mycielskian of trees and graphs with large girth

We will now investigate the general position number of the Mycielskian of
trees and, as a by-product, give a new upper bound on this number for graphs
without short cycles. Let $T$ be any tree with order $n\geq 3$ and $L$ be the
set of all $\ell(T)$ leaves of $T$. Recall that $T$ is _abundant_ if ${\rm
gp}(\mu(T))>\max\\{n,2\alpha_{gp}(T)\\}$ and otherwise is _meagre_. It was
shown in [6] that ${\rm gp}(T)=\ell(T)$; as $L$ is an independent set in
general position in $T$, it follows that ${\rm
gp}(\mu(T))\geq\\{n,2\ell(T)\\}$ and $T$ is abundant if strict inequality
holds. It turns out that many trees are abundant; we present an exact
expression for ${\rm gp}(\mu(T))$ for a wide class of trees.

A vertex of $T$ is _next-to-terminal_ , or _NT_ for short, if it is adjacent
to a leaf of $T$. We will denote the set of NT vertices of $T$ by
$W(T)=\\{y_{1},y_{2},\dots,y_{w}\\}$ and the number of NT vertices of $T$ by
$w=|W(T)|$, whilst $K=\\{z_{1},z_{2},\dots,z_{k}\\}$ is the set of vertices in
$V(T)\setminus(L\cup W)$, so that $n=\ell+w+k$. We will associate with each NT
vertex $y_{i}$ the set $L_{i}$ of leaves to which it is adjacent in $T$. Let
$D_{T}=\min\\{d_{T}(l,l^{\prime}):l\in L_{i},l^{\prime}\in L_{j},i\not=j\\}$,
where $d_{T}$ represents the distance in $T$. If there is just one NT vertex
in $T$, then $T$ is a star and by Theorem 12 we have ${\rm
gp}(\mu(T))=2\ell(T)$, so that $T$ is meagre. Hence we can assume that $w\geq
2$ and $D_{T}$ is defined.

We begin with a lower bound on ${\rm gp}(\mu(T))$ for trees with NT vertices
at distance at least three from each other. We will then proceed to prove that
this bound is sharp.

######  Lemma 18.

If $T$ has $\ell$ leaves and $w$ NT vertices and also $D_{T}\geq 5$, then the
general position number of the Mycielskian $\mu(T)$ satisfies

${\rm gp}(\mu(T))\geq n+\ell-w.$

###### Proof.

Recall that $L$ is the set of leaves of $T$ (and $L^{\prime}$ their twins in
$\mu(T)$) and $K$ is the subset of vertices of $T$ that are neither leaves nor
NT vertices. It follows from Theorem 7 that $S=L\cup L^{\prime}\cup
K^{\prime}$ is in general position in $\mu(T)$, implying that ${\rm
gp}(\mu(T))\geq 2\ell+k=n+\ell-w$. ∎

In the following let $T$ be an abundant tree and $S$ be a gp-set of $\mu(T)$,
which we can assume does not contain $u^{*}$ by Lemma 1. We now present an
upper bound on ${\rm gp}(\mu(G))$ for graphs with girth at least six; recall
by our convention that the girth of a tree is set as $\infty$, so the
following result applies in particular to trees.

######  Theorem 19.

Let $G$ be a graph with order $n\geq 4$, girth $g(G)\geq 6$ and matching
number $\nu(G)$. Then

${\rm gp}(\mu(G))\leq 2n-2\nu(G).$

Also if $G$ satisfies ${\rm gp}(\mu(G))>n$ and
$\pi(G)=(V_{1},V_{2},V_{3},V_{4})$ is a Mycielski partition corresponding to a
gp-set $S$ of $\mu(G)$ that does not contain $u^{*}$, then
$(V_{1},V_{2})=(V_{2},V_{3})=\emptyset$.

###### Proof.

Let $G$, $S$ and $\pi(G)$ be as described. Suppose that the matching
$(V_{1},V_{2})$ contains an edge $u\sim v$, where $u\in V_{1}$ and $v\in
V_{2}$. By Condition 2 of Definition 5 all vertices of $(V_{1}\cup
V_{2})\setminus\\{u,v\\}$ are contained in $N^{2}(u)$. Suppose that $n_{1}\geq
2$ and let $w\in V_{1}\setminus\\{u\\}$. If $w\in N(v)$, then we cannot have
$w\in N(u)$, or else $G$ would contain a cycle of length $\leq 4$; therefore
$u,v,w$ is a shortest path, which is forbidden by Condition 3 of Definition 5.
Thus $G$ contains a path $w,x,u,v$, where $x\in N(u)\setminus\\{v\\}$. Again
by Condition 3 this cannot be a shortest path, so there must be a path of
length $\leq 2$ from $w$ to $v$, implying the existence of a cycle of length
$\leq 5$, a contradiction. Thus in this case $n_{1}=1$. Thus if ${\rm
gp}(\mu(G))>n$, then $n_{4}=0$. As $u$ has no neighbours in $V_{3}\cup V_{4}$
and just one neighbour in $V_{2}$, $u$ is a leaf. Therefore by Conditions 2
and 3 of Definition 5 we have $N(v)=\\{u\\}\cup(V_{2}\setminus\\{v\\})$ and
any vertices of $V_{3}$ must lie in $N^{3}(u)$; however, if there is such a
vertex $x\in V_{3}$ the shortest path $u,x$ path in $G$ would violate
Condition 3. As $G$ is triangle-free, it follows that $G$ is a star. However,
by Corollary 11 the star $S_{n}$ has ${\rm gp}(\mu(S_{n}))=2n-2$, whereas in
the partition described above all but one vertex of $G$ lies in $V_{2}$; since
$S$ is assumed to be a gp-set, this implies that ${\rm gp}(\mu(G))=n+1=2n-2$,
yielding $n=3$.

Suppose now that there is an edge $v\sim w$ in $G$, where $v\in V_{2}$ and
$w\in V_{3}$. By Condition 3 of Definition 5 all vertices of $V_{1}$ lie in
$N^{2}(v)$; as above, if $u\in V_{1}$, whether or not $u$ lies in $N(v)$ we
either create a short cycle or a path forbidden by Condition 3; thus $n_{1}=0$
and ${\rm gp}(\mu(G))=n$, a contradiction.

If ${\rm gp}(\mu(G))=n$, then the claimed bound certainly holds, so assume
that ${\rm gp}(\mu(G))>n$. Let $M$ be a maximum matching of $G$. If $x\sim y$
is any edge in $M$, then it follows from
$(V_{1},V_{2})=(V_{1},V_{3})=\emptyset$ that the vertices
$\\{x,y,x^{\prime},y^{\prime}\\}$ of $\mu(G)$ can contribute at most two to
${\rm gp}(\mu(G))$; summing over all edges of $M$, we see that the vertices
saturated by $M$ and their twins contribute at most $2\nu(G)$ to ${\rm
gp}(\mu(G))$. Assuming that every other vertex lies in $V_{1}$, we obtain the
upper bound ${\rm gp}(\mu(G))\leq 2\nu(G)+2(n-2\nu(G))=2n-2\nu(G)$. ∎

######  Corollary 20.

If $G$ is a graph with order $n\geq 4$ and girth $g(G)\geq 6$ that has a
perfect matching, then ${\rm gp}(\mu(G))=n$.

######  Corollary 21.

If $T$ is an abundant tree with order $n\geq 3$ and matching number $\nu(T)$,
then ${\rm gp}(\mu(T))\leq 2n-2\nu(T)$ and $(V_{1},V_{2})$ and $(V_{2},V_{3})$
are empty.

######  Lemma 22.

Let $T$ be any tree with order $n\geq 3$ and $\ell=w$, i.e. each NT vertex of
$T$ is adjacent to exactly one leaf. Then ${\rm gp}(\mu(T))=n$.

###### Proof.

We first verify the result for paths using induction. The result is true for
the path $P_{4}$ by Corollary 20, as $P_{4}$ has a perfect matching. Write the
vertex set of $P_{5}$ as $\\{v_{0},v_{1},v_{2},v_{3},v_{4}\\}$, where
$v_{i}\sim v_{i+1}$ for $i=0,1,2,3$. Suppose that ${\rm gp}(\mu(P_{5}))\geq 6$
with corresponding Mycielski partition $(V_{1},V_{2},V_{3},V_{4})$; then first
using Theorem 19 on the matching $v_{0}\sim v_{1},v_{2}\sim v_{3}$ and then
the matching $v_{1}\sim v_{2},v_{3}\sim v_{4}$, we see that $v_{0},v_{4}\in
V_{1}$. By Corollary 21 we have $v_{1},v_{3}\in V_{4}$, so that $v_{2}\in
V_{1}$; however $T$ is now a path of length four containing three vertices of
$V_{1}$, contradicting Condition 3 of Definition 5. Consider now a path
$P_{n}$ with order $n\geq 6$ and assume that the result is true for all paths
with order $n^{\prime}$ in the range $4\leq n^{\prime}<n$. Let $S$ be a gp-set
of $\mu(P_{n})$ not containing $u^{*}$ and let $x$ be a leaf of $P_{n}$ and
$y$ its neighbour. By Theorem 19 at most two of the vertices
$\\{x,y,x^{\prime},y^{\prime}\\}$ lie in $S$. The subtree
$P_{n}\setminus\\{x,y\\}$ has ${\rm gp}(\mu(P_{n}\setminus\\{x,y\\}))\leq n-2$
by induction; as $\mu(P_{n}\setminus\\{x,y\\}))$ is an isometric subgraph of
$P_{n}$ we have ${\rm gp}(\mu(P_{n}))\leq n$, establishing the result for
paths.

We may now assume that $T$ has order $n\geq 4$ and contains a vertex $u$ with
degree $d(u)\geq 3$ and that the result is true for all trees with order in
the range $3\leq n^{\prime}<n$. Let $x$ be an eccentric vertex of $u$; as $u$
is adjacent to at most one leaf, $x$ is a leaf at distance $\geq 2$ from $u$.
Let $P$ be the $x,u$-path in $T$ and $Q$ be the longest subpath of $P$ with
initial vertex $x$ such that for every vertex $v\in V(Q)$ we have $d(v)=2$.
Let $Q$ have order $n_{2}$. As $\ell(T)=w(T)$ the path $Q$ has length at least
one, i.e. $d(y)=2$. Deleting $Q$ from $T$ leaves a tree $T_{1}$ with order
$n_{1}\geq 4$ and $\ell(T_{1})=w(T_{1})$; by induction ${\rm
gp}(\mu(T_{1}))=n_{1}$. If $n_{2}\not=3$ the previous result implies that
${\rm gp}(\mu(Q))=n_{2}$ and so ${\rm gp}(\mu(T))\leq{\rm gp}(\mu(T_{1}))+{\rm
gp}(\mu(Q))=n_{1}+n_{2}=n$.

Thus we can assume that $n_{2}=3$. Let the $x,u$-path in $T$ be
$x,u_{1},u_{2},u_{3},\dots,u$. As $Q$ has length two, we must have
$d(u_{3})\geq 3$. Hence when we consider the distance partition of $T$
relative to $u$, the vertex $u_{3}$ has a descendent $w$ at distance
$d(u,x)-2$ from $u$ apart from $u_{2}$. Let the subtree induced by $w$ and its
descendants be denoted by $Q_{2}$. By the foregoing argument $Q_{2}$ is either
isomorphic to $K_{1}$ (i.e. $w$ is a leaf) or to $P_{3}$. Deleting
$P^{\prime}$ will work in our induction unless there are four vertices of
$\\{x,u_{1},u_{2},x^{\prime},u_{1}^{\prime},u_{2}^{\prime}\\}$ contained in
$S$, in which case by Corollary 21 we must have $x,u_{2}\in V_{1}$. If $Q\cong
K_{1}$ then our induction argument works unless $w\in V_{1}$ and, as with $Q$,
if $Q_{2}\cong P_{3}$ then we can again assume that $w\in V_{1}$. However,
this implies that $x,u_{1},u_{2},u_{3},w$ is a path of length four in $T$
containing three vertices of $V_{1}$, which is forbidden by Condition 3 of
Definition 5. This contradiction establishes the result. ∎

######  Corollary 23.

Let $T$ be a tree with order $n\geq 3$, $\ell$ leaves and $w$ NT vertices.
Then ${\rm gp}(\mu(T))\leq n+\ell-w$.

###### Proof.

For each NT vertex of $T$ deleted all but one leaf to form a tree $T_{1}$ with
order $n-\ell+w$. By Lemma 22 we have ${\rm gp}(\mu(T_{1}))=n-\ell+w$. The
deleted $\ell-w$ leaves make a contribution of at most $2(\ell-w)$ to ${\rm
gp}(\mu(T))$. It follows that ${\rm
gp}(\mu(T))\leq(n-\ell+w)+2(\ell-w)=n+\ell-w$. ∎

Combined with the lower bound from Lemma 18 this yields an exact expression
when all NT vertices of $T$ are at distance at least three from each other.

######  Corollary 24.

Let $T$ be a tree with order $n\geq 3$, $\ell$ leaves, $w$ NT vertices and
$D_{T}\geq 5$. Then ${\rm gp}(\mu(T))=n+\ell-w$.

## Acknowledgements

The third author acknowledges funding from an LMS Early Career Fellowship
(Project ECF-2021-27) and thanks the Open University for an extension of
funding in 2020.

## References

  * [1] Abid, A.M. & Rao, T.R., _Dominator coloring of Mycielskian graphs._ Australas. J. Comb. 73 (2019), 274-279.
  * [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] Balakrishnan, R. & Raj, S.F., _Connectivity of the Mycielskian of a graph._ Discrete Math. 308 (12) (2008), 2607-2610.
  * [4] Balakrishnan, R., Kavaskar, T. & So, W., _The energy of the Mycielskian of a regular graph._ Australas. J. Comb. 52 (2012), 163-172.
  * [5] Bondy, J.A. & Murty, U.S.R., _Graph theory with applications_ London: Macmillan, Vol. 290 (1976).
  * [6] Chandran S.V., U. & Parthasarathy, G.J., _The geodesic irredundant sets in graphs._ Int. J. Math. Comb. 4 (2016).
  * [7] Dliou, K., Boujaoui, H.E. & Kchikech, M., _The $L(2,1)$-Labeling of the Mycielski and the iterated Mycielski of graphs._ arXiv preprint arXiv:2103.00341 (2021).
  * [8] Dudeney, H.E. _Amusements in Mmathematics._ Vol. 473. Courier Corporation (1958).
  * [9] Fan, G.H., _Circular chromatic number and Mycielskian graphs._ Combinatorica 24 (1) (2004), 127-135.
  * [10] Froese, V., Kanj, I., Nichterlein, A. & Niedermeier, R., _Finding points in general position._ Int. J. Comput. Geom. Appl. 27 (04) (2017), 277-296.
  * [11] Granados, A., Pestana, D., Portilla, A. & Rodríguez, J.M., _Gromov hyperbolicity in Mycielskian graphs._ Symmetry 9 (8) 131 (2017).
  * [12] Manuel, P. & Klavžar, S., _A general position problem in graph theory._ Bull. Aust. Math. Soc. 98 (2) (2018), 177-187.
  * [13] Mycielski, J., _Sur le coloriage des graphes._ Colloq. Math volume 3 (1955), 9.
  * [14] Neethu, P.K., Chandran S.V., U., Changat, M. & Klavžar, S., _On the general position number of complementary prisms._ preprint arXiv:2001.02189 (2020).
  * [15] Payne, M.S. & Wood, D.R., _On the general position subset selection problem._ SIAM J. Discrete Math. 27 (4) (2013), 1727-1733.
  * [16] Savitha, K.S. & Vijayakumar, A. _Some network topological notions of the Mycielskian of a graph._ AKCE Int. J. Graphs Comb. 13 (1) (2016), 31-37.
  * [17] Thomas, E.J. & Chandran S.V., U., _Characterization of classes of graphs with large general position number._ AKCE Int. J. Graphs Comb. (2020).
  * [18] Thomas, E.J., Chandran S.V., U. & Tuite, J., _On monophonic position sets in graphs._ preprint (2020).
  * [19] Varghese, J. & Lakshmanan, S.A. _Italian domination on Mycielskian and Sierpinski graphs._ Discrete Math. Algorithms Appl. (2020), 2150037.


# ChatGLM-Math: Improving Math Problem-Solving in Large Language Models with a
Self-Critique Pipeline

Yifan Xu12†∗, Xiao Liu12∗, Xinghan Liu12†, Zhenyu Hou12, Yueyan Li1†, Xiaohan
Zhang1,
Zihan Wang12, Aohan Zeng12,Zhengxiao Du12, Wenyi Zhao1, Jie Tang2, Yuxiao
Dong2

1Zhipu.AI 2Tsinghua University

###### Abstract

Large language models (LLMs) have shown excellent mastering of human language,
but still struggle in real-world applications that require mathematical
problem-solving. While many strategies and datasets to enhance LLMs’
mathematics are developed, it remains a challenge to simultaneously maintain
and improve both language and mathematical capabilities in deployed LLM
systems. In this work, we tailor the Self-Critique pipeline, which addresses
the challenge in the feedback learning stage of LLM alignment. We first train
a general Math-Critique model from the LLM itself to provide feedback signals.
Then, we sequentially employ rejective fine-tuning and direct preference
optimization over the LLM’s own generations for data collection. Based on
ChatGLM3-32B, we conduct a series of experiments on both academic and our
newly created challenging dataset, MathUserEval. Results show that our
pipeline significantly enhances the LLM’s mathematical problem-solving while
still improving its language ability, outperforming LLMs that could be two
times larger. Related techniques have been deployed to
ChatGLM111https://chatglm.cn, an online serving LLM. Related evaluation
dataset and scripts are released at https://github.com/THUDM/ChatGLM-Math.

11footnotetext: Yifan and Xiao contributed equally. Emails: xu-
yf23<EMAIL_ADDRESS>Work done while
Xinghan and Yueyan interned at Zhipu AI.

Model |  Avg. of GSM8k & MATH |  AlignBench Language
---|---|---
DeepSeek-67B-Chat [deepseekai2024deepseek] | 58.3 | 7.11
DeepSeek-67B-Chat-DPO [deepseekai2024deepseek] | 57.7 (-1.2%) | 7.60 (+6.8%)
InternLM2-Chat-20B [2023internlm] | 57.2 | 7.68
Math-InternLM2-20B [2023internlm] | 60.2 (+5.1%) | 6.53 (-14.8%)
ChatGLM3-32B-SFT-2312 | 52.4 | 7.37
\+ RFT&DPO | 61.6 (+17.5%) | 7.80 (+5.85%)

Table 1: Our self-critique pipeline enables simultaneous improvement of
language and mathematical abilities. Previous alignment methods enhance
language but could potentially impair mathematical abilities
[deepseekai2024deepseek], whereas math-specialized models could harm language
capabilities [2023internlm].

Figure 1: Results of Hungarian Exam and Average Scores of GSM8k and MATH.

##  1 Introduction

Large Language Models (LLMs) [brown2020language; chowdhery2022palm;
kaplan2020scaling; scao2022bloom; touvron2023llama; zeng2022glm; Claude] have
garnered widespread attention for their remarkable proficiency in various
linguistic tasks such as text summarization[NIPS2015_afdec700; volske-
etal-2017-tl; xsum-emnlp; li-etal-2022-csl], question answering
[hendrycks2020measuring; kwiatkowski2019natural; bras_Gao_Choi_2020], and
role-playing conversations [tu2024charactereval; zhou2023characterglm;
shao2023characterllm]. Furthermore, their potential in addressing complex
problems requiring mathematical reasoning [metamath; wang2023mathshepherd;
wizardmath] has expanded their applicability across real-world missions
[liu2023agentbench; bai2023longbench].

Despite these advances, optimizing LLMs to excel simultaneously in language
understanding and mathematical problem-solving presents a notable challenge.
The prevalent reinforcement learning from human feedback (RLHF) approach
primarily enhances text generation based on reward models reflecting human
preferences [touvron2023llama; ouyang2022training; touvron2023llama2].
Although this method boosts the quality of generated text, it often overlooks
the accuracy and logical coherence essential for solving mathematical
problems, leading to a discrepancy in performance known as the "alignment
tax"[askell2021general] when applied to mathematical reasoning (refer to Table
1). Conversely, attempts to bolster LLMs’ mathematical capabilities typically
entail supervised fine-tuning (SFT) that inadvertently diminishes their
linguistic versatility, posing a dilemma for practical applications of LLM
systems [2023internlm; metamath; wizardmath; yue2023mammoth].

Pipeline: Self-Critique. This paper introduces a novel approach aimed at
enhancing both linguistic and mathematical skills of LLMs without compromising
one for the other. Our strategy deviates from traditional RLHF by
incorporating a Math-Critique model derived from the LLM itself, which
evaluates its mathematical outputs. This self-critique mechanism enables the
model to learn from AI-generated feedback specifically tailored to
mathematical content [bai2022constitutional; lee2023rlaif]. Our methodology
comprises two primary phases:

  * •

Stage 1: Rejective Fine-tuning (RFT) [yuan2023scaling-mathrft] employs a
rejection sampling technique, wherein responses failing to meet Math-Critique
standards are discarded, while the rest undergo further fine-tuning. This
stage aims to enhance the model’s accuracy and consistency in mathematical
responses while ensuring diversity among the selected answers.

  * •

Stage 2: Direct Preference Optimization (DPO) [rafailov2023direct] extends the
improvement process by directly learning from pairs of correct and incorrect
answers, further refined through Math-Critique, focusing on the most
challenging questions from the previous stage.

Benchmark: MathUserEval. To accurately assess LLMs’ capabilities in solving
real-world mathematical problems, we develop the MathUserEval dataset. It
features a diverse range of questions, extending beyond academic exercises to
include practical application scenarios, thereby better reflecting user needs
compared to traditional academic math datasets [zhao2020ape210k; wang-
etal-2017-deep-math23; cobbe2021training]. We leverage both GPT-4-turbo and
our Math-Critique model for comprehensive scoring.

In summary, our contributions include:

  * •

The introduction of the Self-Critique pipeline, a novel framework that
elevates both the mathematical and linguistic capabilities of LLMs through
self-generated feedback, thereby eliminating the need for external supervisory
models and manual annotations. This approach has been validated on a
ChatGLM3-32B model, achieving unparalleled performance on the MathUserEval,
Ape210k [zhao2020ape210k], MATH [hendrycks2020measuring], and the linguistic
tasks of AlignBench [liu2023alignbench].

  * •

The creation of the MathUserEval benchmark, tailored to assess LLMs on
complex, open-ended mathematical queries relevant to real-world applications,
setting a new standard in evaluating practical mathematical reasoning
capabilities.

  * •

A detailed analysis of the key factors contributing to the enhancement of
mathematical proficiency through the Self-Critique pipeline, offering insights
into future directions for autonomous model improvement.