text:
\begin{document}

\title{Strong geodetic problem on complete multipartite graphs}

\author{
	Vesna Ir\v si\v c $^{a,b}$
	\and
	Matja\v z Konvalinka $^{a,b}$
}

\date{\today}

\maketitle

\begin{center}
	$^a$ Faculty of Mathematics and Physics, University of Ljubljana, Slovenia\\
	\medskip

	$^b$ Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
\end{center}

\begin{abstract}
The strong geodetic problem is to find the smallest number of vertices such that by fixing one shortest path between each pair, all vertices of the graph are covered. In this paper we study the strong geodetic problem on complete bipartite graphs; in particular, we discuss its asymptotic behavior. Some results for complete multipartite graphs are also derived. Finally, we prove that the strong geodetic problem restricted to (general) bipartite graphs is NP-complete.
\end{abstract}

\noindent {\bf Key words:} geodetic problem; strong geodetic problem; (complete) bipartite graphs; (complete) multipartite graphs

\medskip\noindent
{\bf AMS Subj.\ Class:} 05C12, 05C70; 68Q17

\section{Introduction}
\label{sec:intro}

The strong geodetic problem was introduced in~\cite{MaKl16a} as follows. Let $G=(V,E)$ be a graph. For a set $S\subseteq V$, and for each pair of vertices $\{x,y\}\subseteq S$, $x\ne y$, define $\widetilde{g}(x,y)$ as a {\em selected fixed} shortest path between $x$ and $y$. We set
$$\widetilde{I}(S)=\{\widetilde{g}(x, y) : x, y\in S\}\,,$$ and $V(\widetilde{I}(S))=\bigcup_{\widetilde{P} \in \widetilde{I}(S)} V(\widetilde{P})$. If $V(\widetilde{I}(S)) = V$ for some $\widetilde{I}(S)$, then the set $S$ is called a {\em strong geodetic set}. This means that the selected fixed geodesics between vertices from $S$ cover all vertices of the graph $G$. If $G$ has just one vertex, then its vertex is considered the unique strong geodetic set. The {\em strong geodetic problem} is to find a minimum strong geodetic set of $G$. The size of a minimum strong geodetic set is the {\em strong geodetic number} of $G$ and is denoted by $\sg(G)$. A strong geodetic set of size $\sg(G)$ is also called an {\em optimal strong geodetic set}.

In the first paper~\cite{MaKl16a}, it was proved that the problem is NP-complete. The invariant has also been determined for complete Apollonian networks~\cite{MaKl16a}, thin grids and cylinders~\cite{Klavzar+2017}, and balanced complete bipartite graphs~\cite{bipartite}. Some properties of the strong geodetic number of Cartesian product of graphs have been studied in~\cite{products}. Recently, a concept of strong geodetic cores has been introduced and applied to the Cartesian product graphs~\cite{cores}. An edge version of the problem was defined and studied in~\cite{MaKl16b}.

The strong geodetic problem is just one of the problems which aim to cover all vertices of a graph with shortest paths. Another such problem is the \emph{geodetic problem}, in which we determine the smallest number of vertices such that the geodesics between them cover all vertices of the graph~\cite{bresar-2011b, chartrand-2000, hansen-2007, HLT93}. Note that we may use more geodesics between the same pair of vertices. Thus this problem seems less complex than the strong geodetic problem. It is known to be NP-complete on general graphs~\cite{atici}, on chordal and bipartite weakly chordal graphs~\cite{dourado}, on co-bipartite graphs~\cite{ekim-2014}, and on graphs with maximal degree $3$~\cite{bueno}. However, it is polynomial on co-graphs and split graphs~\cite{dourado}, on proper interval graphs~\cite{ekim-2012}, on block-cactus graphs and monopolar chordal graphs~\cite{ekim-2014}. Moreover, the geodetic number of complete bipartite (and multipartite) graphs is straightforward to determine, i.e.\ $\sg(K_{n,m}) = \min\{n,m,4\}$~\cite{HLT93}.

Recall from~\cite{bipartite} that the strong geodetic problem on a complete bipartite graph can be presented as a (non-linear) optimization problem as follows. Let $(X, Y)$ be the bipartition of $K_{n_1, n_2}$ and $S = S_1 \cup S_2$, $S_1 \subseteq X$, $S_2 \subseteq Y$, its strong geodetic set.  Let $|S_i| = s_i$ for $i \in \{1,2\}$. Thus, $\sg(K_{n_1, n_2}) \leq s_1 + s_2$. With geodesics between vertices from $S_1$ we wish to cover vertices in $Y - S_2$. Vice versa, with geodesics between vertices from $S_2$ we are covering vertices in $X - S_1$. The optimization problem for $\sg(K_{n_1, n_2})$ reads as follows:
\begin{align}
\label{optimizationProblem}
\begin{split}
\min \quad & s_1 + s_2 \\
\text{subject to: } & 0 \leq s_1 \leq n_1\\
&  0 \leq s_2 \leq n_2\\
&  \binom{s_2}{2} \geq n_1 - s_1\\
&  \binom{s_1}{2} \geq n_2 - s_2\\
& s_1, s_2 \in \Z.
\end{split}
\end{align}

This holds due to the fact that every geodesic in a complete bipartite graph is either of length $0$, $1$ (an edge), or $2$ (a path with both endvertices in the same part of the bipartition). If a strong geodetic set $S$ has $k$ vertices in one part of the bipartition, then geodesics between those vertices can cover at most $\binom{k}{2}$ vertices in the other part.

The exact value is known for balanced complete bipartite graphs: if $n \geq 6$, then
$$\sg(K_{n,n}) = \begin{cases}
2 \left \lceil \displaystyle \frac{-1 + \sqrt{8 n + 1}}{2} \right \rceil, & 8n - 7 \text{ is not a perfect square},\vspace{0.2cm}\\
2 \left \lceil \displaystyle \frac{-1 + \sqrt{8 n + 1}}{2} \right \rceil - 1, & 8n - 7 \text{ is a perfect square}.
\end{cases}$$

See \cite[Theorem 2.1]{bipartite}.

In the following section, we generalize the above result to all complete bipartite graphs. In particular, we determine the asymptotic behavior of $\sg(K_{n,m})$.

As we also consider complete multipartite graphs, it is useful to recall the notation $\langle 1^{m_1}, \ldots, k^{m_k} \rangle$ which describes a partition with $m_i$ parts of size $i$, $1 \leq i \leq k$.

To conclude the introduction, we state the following interesting and surprisingly important fact.

\begin{proposition}
	\label{prop:two}
	For every complete multipartite graph there exist an optimal strong geodetic set such that its intersection with all but two parts of the multipartition is either empty or the whole part.
\end{proposition}

\proof
Let $G = K_{n_1, \ldots, n_r}$ be a complete multipartite graph with the multipartition $X_1, \ldots, X_r$, $|X_i| = n_i$ for all $i \in [r]$. Let $S = S_1 \cup \cdots \cup S_r$ be an optimal strong geodetic set, $S_i \subseteq X_i$ and $|S_i| = s_i$ for $i \in [r]$.

Suppose that $s_i \in \{1, \ldots, n_i - 1\}$ for $i \in \{1,2,3\}$. Without loss of generality, $s_1 = \min\{ s_1, s_2, s_3 \}$. Let $x \in S_1$, $y \in X_2 - S_2$, and $z \in X_3 - S_3$.

Define
\begin{align*}
	T_2 & = (S_1 - \{x\}) \cup (S_2 \cup \{y\}) \cup S_3 \cup \cdots \cup S_r, \\
	T_3 & = (S_1 - \{x\}) \cup S_2 \cup (S_3 \cup \{z\}) \cup S_4 \cup \cdots \cup S_r.
\end{align*}
Notice that $|S| = |T_2| = |T_3| = \sg(G)$. We now show that either $T_2$ or $T_3$ is a strong geodetic set of $G$.

Let $B_i$, $i \in \{2,3\}$, be the vertices in $X_i$ that are covered by the geodesics between vertices in $S_1$, and let $C$ be the vertices in $X_4 \cup \cdots \cup X_r$ that are covered by the geodesics between vertices in $S_1$. Geodesics between vertices in $S_1 - \{x\}$ cover $s_1 - 1$ vertices fewer than geodesics between vertices in $S_1$.

If the remaining geodesics can be rearranged so that $B_i$ is completely covered, then $T_i$ is a strong geodetic set, as the remaining uncovered vertices lie outside of $X_i$, so they can be covered by $s_i \geq s_1$ geodesics between $S_i$ and $y$ or $z$, $i \in \{2,3\}$.

If $|B_i \cup C| \geq s_1 - 1$, these
 geodesics can be rearranged so that $B_{5-i}$ is completely covered. If $|B_i| \leq 1$, we can also consider $B_i$ as completely covered (the possibly uncovered vertex can be only $y$ or $z$).

The only remaining case is if $|B_i \cup C| < s_1 - 1$, and $|B_i| \geq 2$ for $i \in \{2,3\}$. Since $|B_2 \cup B_3 \cup C| = \binom{s_1}{2}$, the first condition implies $s_1 < 4$, which implies $|B_2 \cup B_3| \leq \binom{s_1}{2}\leq 3$, so this cannot occur at all.

This means that every strong geodetic set with three or more parts of size unequal to $0$ or $n_i$ can be transformed into a strong geodetic set of the same size, where one of these parts becomes smaller and one larger. After repeating this procedure on other such triples, at most two parts can have size different from $0$ or $n_i$.
\qed

The rest of the paper is organized as follows. In the next section, some further results about the strong geodetic number of complete bipartite graphs are obtained. In Section~\ref{sec:complete_multipartite} we discuss the strong geodetic problem on complete multipartite graphs. Finally, in Section~\ref{sec:NP} the complexity of the strong geodetic problem on multipartite and complete multipartite graphs is discussed.

\section{On complete bipartite graphs}
\label{sec:complete_bipartite}

In this section, we give a complete description of the strong geodetic number of a complete bipartite graph. The result is unusual, however, as it does not directly say how to compute $\sg(K_{n,m})$; instead, it classifies triples $(n,m,k)$ for which $\sg(K_{n,m}) = k$.

Define $$f(\alpha, \beta) = \alpha - 1 + \binom{\max\{\beta-1, 2\}}{2} \, .$$

\begin{theorem}
	\label{thm:sg=k}
	For positive integers $n$, $m$ and $k$, $\sg(K_{n,m}) = k$ if and only if
	$$n < k \; \& \; m = f(k, n) \quad \text{or} \quad m < k \; \& \; n = f(k, m) \quad \text{or}$$
	$$f(k, i-1) \leq m \leq f(k, i) \; \& \; f(k, k-i-1) \leq n \leq f(k, k-i) \; \text{for some }i, 0 \leq i \leq k.$$
	The only exceptions are $\sg(K_{1,1}) = 2$ and $\sg(K_{2,2}) = 3$.
\end{theorem}

\begin{example}
The strong geodetic numbers of small complete bipartite graphs can be found in Table~\ref{tbl:values2}.

	\begin{table}[!!h]
		\centering
		\begin{tabular}{|c||*{15}{c|}}\hline
			\backslashbox{$m$}{$n$}
			&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15 \\\hline\hline
			1 & 2 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\\hline
 2 & 2 & 3 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\\hline
 3 & 3 & 3 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\\hline
 4 & 4 & 4 & 4 & 4 & 4 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\\hline
 5 & 5 & 5 & 5 & 4 & 5 & 5 & 5 & 5 & 5 & 5 & 6 & 7 & 8 & 9 & 10 \\\hline
 6 & 6 & 6 & 6 & 4 & 5 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 \\\hline
 7 & 7 & 7 & 7 & 5 & 5 & 6 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 \\\hline
 8 & 8 & 8 & 8 & 6 & 5 & 6 & 7 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 \\\hline
 9 & 9 & 9 & 9 & 7 & 5 & 6 & 7 & 8 & 8 & 8 & 9 & 9 & 9 & 9 & 9 \\\hline
 10 & 10 & 10 & 10 & 8 & 5 & 6 & 7 & 8 & 8 & 8 & 9 & 9 & 9 & 9 & 10 \\\hline
 11 & 11 & 11 & 11 & 9 & 6 & 6 & 7 & 8 & 9 & 9 & 9 & 9 & 9 & 9 & 10 \\\hline
 12 & 12 & 12 & 12 & 10 & 7 & 6 & 7 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 \\\hline
 13 & 13 & 13 & 13 & 11 & 8 & 6 & 7 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 \\\hline
 14 & 14 & 14 & 14 & 12 & 9 & 6 & 7 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 \\\hline
 15 & 15 & 15 & 15 & 13 & 10 & 6 & 7 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 \\\hline
		\end{tabular}
		\caption{The strong geodetic numbers $\sg(K_{n,m})$ for some small complete bipartite graphs.}
		\label{tbl:values2}
	\end{table}

Figure \ref{fig:k12} shows the positions of all 201 pairs $(n,m)$ for which $\sg(K_{n,m}) = 12$. We can notice the ``parabolas'' corresponding to $m = f(k, n)$ and $n = f(k, m)$, as well as the ``intersecting rectangles'' corresponding to $f(k, i-1) \leq m \leq f(k, i)$, $f(k, k-i-1) \leq n \leq f(k, k-i)$.

\begin{figure}[!!h]
\begin{center}
	\scalebox{0.15}{\begin{ytableau}
	{} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   *(black) & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & *(black) & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & *(black) & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & *(black) & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & *(black) & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & *(black) & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 *(black) & *(black) & *(black) & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) &
   *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) &
   *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) &
   *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) &
   *(black) \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) &
   *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} \\
 {} & {} & {} & *(black) & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & *(black) & *(black) & *(black) & *(black) & *(black)
   & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & *(black) & *(black) & *(black) & *(black) & *(black)
   & *(black) & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {}
   & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & *(black) & *(black) & *(black) & *(black) & *(black)
   & *(black) & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {}
   & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} \\
 {} & {} & {} & {} & *(black) & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) &
   *(black) & *(black) & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & *(black) & *(black) & *(black) & *(black) & *(black) & {} & {} & {} & {}
   & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & *(black) & *(black) & *(black) & *(black) & *(black) & {} & {} & {} & {}
   & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & *(black) & *(black) & *(black) & *(black) & *(black) & {} & {} & {} & {}
   & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} \\
 {} & {} & {} & {} & {} & *(black) & {} & {} & {} & {} & {} & {} & {} &
   *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & *(black) & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   *(black) & *(black) & *(black) & *(black) & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   *(black) & *(black) & *(black) & *(black) & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   *(black) & *(black) & *(black) & *(black) & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   *(black) & *(black) & *(black) & *(black) & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} \\
 {} & {} & {} & {} & {} & {} & *(black) & {} & {} & {} & {} & *(black) &
   *(black) & *(black) & *(black) & *(black) & *(black) & {} & {} & {} & {} & {} & {} & {}
   & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & *(black)
   & *(black) & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {}
   & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & *(black)
   & *(black) & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {}
   & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & *(black)
   & *(black) & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {}
   & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & *(black)
   & *(black) & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {}
   & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & *(black)
   & *(black) & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {}
   & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & *(black) & {} & {} & {} & *(black) &
   *(black) & *(black) & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} & {} & *(black) & {}
   & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} & *(black) & {}
   & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & *(black) & {}
   & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & *(black) & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} &
   {} \\
 \end{ytableau}}
\end{center}
\caption{All pairs $(n,m)$ for which $\sg(K_{n,m}) = 12$.}  \label{fig:k12}
\end{figure}
\end{example}

\proof[Proof of Theorem~\ref{thm:sg=k}]
It is not difficult to see that $\sg(K_{n,m}) = 2$ if and only if $(n,m) \in \{ (1,1), (1,2), (2,1) \}$, and that $\sg(K_{2,2}) = 3$. So assume that $k \geq 3$ and $\max\{n,m\} \geq 3$.

The statement follows from the following (note that the sum $s_1 + s_2$ equals $k$ for every $(s_1, s_2)$ that appears below):
\begin{enumerate}
\setlength{\itemsep}{0pt}
	\item If $n \leq 3$ and $m = f(k, n) = k$,  then $(0,k)$ is an optimal solution.
	\item If $3 \leq n < k$ and $m = f(k, n)$,  then $(n, k-n)$ is an optimal solution.
	\item If $m \leq 3$ and $n = f(k, m) = k$,  then $(k,0)$ is an optimal solution.
	\item If $3 \leq m < k$ and $n = f(k, m)$,  then $(k-m, m)$ is an optimal solution.
	\item If $f(k, i-1) < m \leq f(k,i)$ and $f(k, k-i-1) < n \leq f(k, k-i)$ for $4 \leq i \leq k-4$, then $(i, k-i)$ is an optimal solution.
	\item If $f(k, i-1) < m \leq f(k,i)$ and $n = f(k, k-i-1)$ for $i \leq k-3$, then $(i, k-i)$ is an optimal solution.
	\item If $f(k, i-1) < m \leq f(k,i)$ and $n = f(k, k-i-1)$ for $i \leq k-4$, then $(i+1, k-i-1)$ is an optimal solution.
	\item If $f(k, i-1) < m \leq f(k,i)$ and $n = f(k, k-i-1)$ for $i \geq k-4$, then $(k,0)$ is an optimal solution.
	\item If $m =f(k, i-1)$ and $f(k, k-i-1) < n \leq f(k,k-i)$ for $i \geq 3$, then $(i, k-i)$ is an optimal solution.
	\item If $m =f(k, i-1)$ and $f(k, k-i-1) < n \leq f(k,k-i)$ for $i \geq 4$, then $(i-1,k-i+1)$ is an optimal solution.
	\item If $m =f(k, i-1)$ and $f(k, k-i-1) < n \leq f(k,k-i)$ for $i \leq 4$, then $(0,k)$ is an optimal solution.
	\item If $m = f(k,i-1)$ and $n = f(k, k-i-1)$ for $i \leq 4$, then $(0,k)$ is an optimal solution.
	\item If $m = f(k,i-1)$ and $n = f(k, k-i-1)$ for $2 \leq i \leq k-4$, then $(i+1, k-i-1)$ is an optimal solution.
	\item If $m = f(k,i-1)$ and $n = f(k, k-i-1)$ for $3 \leq i \leq k-3$, then $(i, k-i)$ is an optimal solution.
	\item If $m = f(k,i-1)$ and $n = f(k, k-i-1)$ for $4 \leq i \leq k-2$, then $(i-1, k-i+1)$ is an optimal solution.
	\item If $m = f(k,i-1)$ and $n = f(k, k-i-1)$ for $i \geq k-4$, then $(k,0)$ is an optimal solution.
\end{enumerate}

It is easy to see that the above solutions give rise to the strong geodetic sets of size $k$. For example, in the first case, the part of the bipartition of size $m$ is a strong geodetic set with parameters $(0,k)$. What remains to be proved is $\sg(K_{n,m}) \geq k$ for each case. This can be shown by a simple case analysis. As the reasoning is similar in all cases, we demonstrate only two of them. Let $X$ be the part of the bipartition of size $n$ and $Y$ the part of size $m$. Also, let $S = S_1 \cup S_2$, where $S_1 \subseteq X$, $S_2 \subseteq Y$, be some strong geodetic set.

\begin{enumerate}
	\item[2.] In this case we have $k > n \geq 3$ and $m = k-1 + \binom{n-1}{2} = k - n + \binom{n}{2}$. If $S_1 = X$, then geodesics between these vertices cover at most $\binom{n}{2}$ vertices in $Y$, so at least $k-n$ vertices in $Y$ must also lie in a strong geodetic set. Hence, $|S| \geq n - (k-n) = k$.

	If $S_1 \neq X$, geodesics between these vertices cover at most $\binom{n-1}{2}$ vertices in $Y$, so at least $k-1$ vertices from $Y$ must lie in a strong geodetic set. Hence, $|S| \geq |S_1| + (k-1)$. If $S_1 \neq \emptyset$ or $|S_2| \geq k$, we have $|S| \geq k$. Otherwise, $S = S_2$ and contains exactly $k-1$ vertices. But then the remaining vertices in $Y$ are not covered.

	\item[5.] We can write
	$$n = k-1 + \binom{k-i-2}{2} + l,\ l \in \{1, \ldots, k-i-2\}\, ,$$
	$$m = k-1 + \binom{i-2}{2} + j,\ j \in \{1, \ldots, i-2\}\, .$$
	Suppose $|S| \leq k-1$.
	If $|S_1| \leq i-2$, these vertices cover at most $\binom{i-2}{2}$  vertices in $X$, thus at least $k$ vertices remain uncovered and $|S| \geq k$. Hence, $|S_1| \geq i-1$. Similarly, $|S_2| \geq k-i-1$.

	If $|S_1| = i-1$, then $\binom{i-1}{2}$ vertices in $Y$ are covered. As $k + j - i+1$ are left uncovered, it holds that $|S_2| \geq k-i+2$ and thus $|S| \geq k+1$.

	If $|S_2| = k-i-1$, then $\binom{k-i-1}{2}$ vertices in $X$ are covered. As $l+i+1$ are left uncovered, it holds that $|S_1| \geq i+2$ and thus $|S| \geq k+1$.

	Hence $|S_1| \geq i$ and $|S_2| \geq k-i$ and thus $|S| \geq k$.
\end{enumerate}

Note that all different optimal solutions are described above, hence some of the conditions could be merged.
\qed

The first condition from Theorem~\ref{thm:sg=k} can be simplified as follows.

\begin{corollary}
	\label{cor:bipartite}
	If $n \geq 3$ and $m > \binom{n}{2}$, then $\sg(K_{n,m}) = m + 1 - \binom{n-1}{2}$. If $n \leq 3$ and $m > n$, then $\sg(K_{n,m}) = m$.
\end{corollary}

When $m \leq \binom n 2$, Theorem~\ref{thm:sg=k} is harder to apply. Note, however, that the theorem suggests that $m$ is approximately equal to $k-1+\binom{i-1}2$, and $n$ is approximately equal to $k-1+\binom{k-i-1}2$. Furthermore, note that we can rewrite the system of equations (with known $m,n$ and variables $k,i$) $m = k-1+\binom{i-1}2$, $n = k-1+\binom{k-i-1}2$ as a polynomial equation of degree $4$ for $k$ (say by subtracting the two equations, solving for $i$, and plugging the result into one of the equations), and solve it explicitly. It seems that one of the four solutions is always very close to $\sg(K_{m,n})$. Denote the minimal distance between $\sg(K_{m,n})$ and a solution $k$ of $m = k-1+\binom{i-1}2$, $n = k-1+\binom{k-i-1}2$ by $e(m,n)$. Then our data indicates the following:

\begin{table}[!!h]
	\centering
	\begin{tabular}{|c||*{15}{c|}}\hline
		$n$ & 10 & 100 & 1000 & 10000 & 100000 \\ \hline
		$\max\{e(m,n) \colon n \leq m \leq \binom n 2\}$ & $1.094$ & $1.774$ & $1.941$ & $1.983$ &  $1.995$ \\ \hline
	\end{tabular}
\end{table}

\medskip

We conjecture the following.

\begin{conjecture}
 If $n \leq m \leq \binom n 2$, then $e(m,n) < 2$.
\end{conjecture}

If the conjecture is true, $\sg(K_{m,n})$ is among the (at most $16$) positive integers that are at distance $< 2$ from one of the four solutions of the system $m = k-1+\binom{i-1}2$, $n = k-1+\binom{k-i-1}2$. For each of these (at most) $16$ candidates, there are at most three (consecutive) $i$'s for which $f(k,i-1) \leq m \leq f(k,i)$, found easily by solving the quadratic equation $m = k - 1 + \binom{i-1}2$. For each such $i$, check if $f(k,k-i-1) \leq n \leq f(k,k-i)$. This allows for computation of $\sg(K_{m,n})$ with a constant number of operations.

\medskip

In the rest of this section we discuss the asymptotic behavior  of the strong geodetic problem on complete bipartite graphs.

\begin{theorem}
	\label{thm:asymptotic}
	Assume that $m \geq n \geq 2$, $m = \alpha n^\beta + \gamma n^{\beta - 1} + O(n^{\beta - 2})$. Then
	\[\sg(K_{n,m}) =  \begin{cases}
	  \alpha n^\beta + O(n^{\beta-1}), & m = \alpha n^\beta + O(n^{\beta-1})\mbox{ for } \beta > 2 \\
	  (\alpha-\frac 1 2) n^2 + O(n), & m = \alpha n^2 + O(n)\mbox{ for } \alpha > 1/2 \\
	  (\gamma + \frac 3 2) n + O(1), & m =n^2/2 + \gamma n + O(1) \mbox{ for } \gamma > -1/2 \\
	  n + O(1), & m =n^2/2 + \gamma n + O(1) \mbox{ for } \gamma \leq -1/2 \\
	  \sqrt{2\alpha} \cdot n + O(1), & m = \alpha n^2 + O(n)\mbox{ for } 0 < \alpha < 1/2 \\
	  \sqrt{2\alpha} \cdot n^{\beta/2} + O(1), & m =  \alpha n^\beta + O(n^{\beta-1})\mbox{ for } 1 < \beta < 2 \\
	  \sqrt{2}(1+\sqrt\alpha) n^{1/2} + O(1), & m = \alpha n + O(1)\mbox{ for } \alpha \geq 1
	\end{cases}\]
\end{theorem}
\begin{proof}[Sketch of proof]
	The first three cases follow from the last corollary. Indeed, in each of these cases, $m > \binom{n}2$ for $n$ large enough, so $\sg(K_{m,n}) = m + 1 - \binom{n-1}2$; which gives the stated result. For example, when $m = n^2/2 + \gamma n + O(1)$ for $\gamma > -1/2$, we get $\sg(K_{m,n}) = n^2/2 + \gamma n + O(1) + 1 - \frac{n^2-3n+2}{2} = (\gamma+3/2)n + O(1)$.\\
  Now assume that $m = n^2/2 + \gamma n + O(1)$, $\gamma \leq -1/2$. Assume first that there exists a non-negative integer $c$ so that $-\gamma - 5/2 < c + \lceil (1+\sqrt{8c+9})/2 \rceil < -\gamma - 3/2$. Denote $\lceil (1+\sqrt{8c+9})/2 \rceil$ by $d$, and define $k = k(n) = n - c$ and $i = i(n) = k - d - 1$. Let us check that for $n$ large enough,
  $$f(k, i-1) \leq m \leq f(k, i), \qquad f(k, k-i-1) \leq n \leq f(k, k-i).$$
  Indeed, we have
  \begin{multline*}
  f(k,i) = k - 1 + \binom{i-1}2 = n - c - 1 + \binom{n - c - d - 2}{2} \\
  = n - c - 1 + \frac{(n - c - d - 2)(n - c - d - 3)}{2} \\
  = n^2/2 + n (1 - (c + d + 5/2)) + O(1) > m,
  \end{multline*}
  \begin{multline*}
  f(k,i-1) = k - 1 + \binom{i-2}2 = n - c - 1 + \binom{n - c - d - 3}{2} \\
  = n - c - 1 + \frac{(n - c - d - 3)(n - c - d - 4)}{2} \\
  = n^2/2 + n (1 - (c + d + 7/2)) + O(1) < m.
  \end{multline*}
  On the other hand, we claim that $d$ is the smallest non-negative integer so that $\binom{d}2 \geq c + 1$. Indeed, if $\binom x 2 \geq c + 1$ for $x$, then $x^2 - x - 2c - 2 \geq 0$ and therefore $x \geq (1 + \sqrt{1+4(2c+2)})/2$. If $x$ is an integer, then $x \geq d$. It follows that $\binom{d-1}2 < c + 1 \leq \binom{d}2$. Then
  $$f(k,k - i - 1) = k - 1 + \binom{k - i - 2}2 = n - c - 1 + \binom{d - 1}{2} < n$$
  and
  $$f(k,k - i) = k - 1 + \binom{k - i - 1}2 = n - c - 1 + \binom{d}{2} \geq n.$$
  This proves that $\sg(m,n) = k$.\\
  If such $c$ does not exist, there are two options. One is that the sequence $(c +  \lceil (1+\sqrt{8c+9})/2 \rceil)_{c=0}^\infty$, which contains all natural numbers except $\binom j 2$, $j \geq 0$, skips the interval $[-\gamma - 5/2,-\gamma-3/2]$. Take $c$ so that
  $$c + \lceil (1+\sqrt{8c+9})/2 \rceil < -\gamma - 5/2 < -\gamma - 3/2 < c + 1 +\lceil (1+\sqrt{8c+17})/2 \rceil.$$
  It turns out that in that case, $8c+9$ is the square of an odd integer, say $8c + 9 = (2d-3)^2$ (i.e.~$c = (d^2-3j)/2$ and $(1+\sqrt{8c+9})/2 = d - 1$). Now take $k = k(n) = n - c$ and $i = k - d - 1$. Then $f(k,i-1) \leq m \leq f(k,i)$ and $f(k,k-i-1) \leq n \leq f(k,k-i)$ for $n$ large enough, so $\sg(K_{n,m}) = k$.\\
  Another case is that $\gamma$ is half a negative integer. A similar analysis holds, with some weak inequalities replacing strong inequalities, and dealing separately with cases $m \geq n^2/2 + \gamma n$ and $m < n^2/2 + \gamma n$. We leave this as an exercise for the reader.\\
  We sketch the proof for the last three cases. If $m \sim \alpha n^2$ for $0 < \alpha < 1/2$, take $k \sim \sqrt{2\alpha} \, n$ and $k - i \sim \sqrt{2(1-\sqrt{2\alpha})} \sqrt n$ (in particular, $i \sim \sqrt{2\alpha} \, n$). Then
  $$f(k,i) \sim k + \binom{i} 2 \sim \sqrt{2\alpha} \, n + \frac{i^2}{2} \sim \sqrt{2\alpha} \, n + \alpha n^2 \sim \alpha n^2$$
  and
  $$f(k,k-i) \sim k + \binom{k-i} 2 \sim \sqrt{2\alpha} \, n + (1-\sqrt{2\alpha}) n \sim n.$$
  We can adapt this to show that $\sg(K_{n,m}) \sim \sqrt{2\alpha} \,  n$.\\
  If $m \sim \alpha n^\beta$ for $\alpha > 0$ and $1 < \beta < 2$, we can repeat the previous calculation with $k \sim \sqrt{2\alpha} n^{\beta/2}$ and $k - i \sim \sqrt{2n}$, and if $m \sim \alpha n$, with $k \sim \sqrt 2(1+\sqrt \alpha) \sqrt n$ and $i \sim \sqrt{2 \alpha n}$.
\end{proof}

\section{On complete multipartite graphs}
\label{sec:complete_multipartite}

The optimization problem~\eqref{optimizationProblem} can be generalized to complete multipartite graphs. However, solving such a program seems rather difficult. Hence, we present an approximate program which gives a nice lower bound for the strong geodetic number of a complete multipartite graph. If $i$ vertices from one part are in a strong geodetic set, geodesics between them cover at most $\binom{i}{2}$ other vertices. In the following, we do not take into account the condition that they can only cover vertices in other parts, and that the number of selected vertices must be an integer. Let $G$ be a complete multipartite graph corresponding to the partition $\pi = \langle 1^{m_1}, \ldots, k^{m_k} \rangle$ and let $a_{ij}$ denote the number of parts of size $j$ with exactly $i$ vertices in the strong geodetic set. Thus we must have $\sum_{i = 0}^j a_{ij} = m_j$ and $\sum_{j=1}^k \sum_{i=0}^j \binom{i}{2} a_{ij} \geq \sum_{j = 1}^k \sum_{i = 0}^j (j-i) a_{ij}$. The second condition simplifies to $\sum_{j=1}^k \sum_{i=1}^j \binom{i+1}{2} a_{ij} \geq \sum_{j = 1}^k \sum_{i = 0}^j j a_{ij} = \sum_{j = 1}^k j m_j = n$. As $a_{0j}$'s do not appear in it anymore, we also simplify the first condition to $\sum_{i = 1}^j a_{ij} \leq m_j$ and get

\begin{align}
\label{optimizationProblemMulti}
\begin{split}
\min \quad & \sum_{j=1}^k \sum_{i=1}^j i a_{ij} \\
\text{subject to: } & \sum_{i = 1}^j a_{ij} \leq m_j\\
&  \sum_{j=1}^k \sum_{i=1}^j \binom{i+1}{2} a_{ij} \geq n\\
&  0 \leq a_{ij} \leq m_j
\end{split}
\end{align}

As the sequence $\binom{k}{2} - k$ is increasing for $k \geq 3$, it is better to select more vertices in a bigger part. Hence, the optimal solution is

\begin{align*}
a_{k,k} & =  m_k \\
a_{k-1,k-1} & =  m_{k-1} \\
 & \vdots  \\
a_{l+1,l+1} & =  m_{l+1} \\
a_{l,l} & =  \frac{l m_l + \cdots + 1 m_1 - \binom{k}{2} m_k - \cdots - \binom{l+1}{2} m_{l+1}}{\binom{l+1}{2}}\,,
\end{align*}
where $l$ is the smallest positive integer such that $\binom{k+1}{2} m_k + \cdots + \binom{l+2}{2} m_{l+1} \leq k m_k + \cdots + 1 m_1 = |V(K_{\langle 1^{m_1}, \ldots, k^{m_k} \rangle})|$, which is equivalent to $l m_l + \cdots + 1 m_1 \geq \binom{k}{2} m_k + \cdots + \binom{l+1}{2} m_{l+1}$, and
$$\sg(K_{\langle 1^{m_1}, \ldots, k^{m_k} \rangle}) \geq \left \lceil k m_k + \cdots + (l+1) m_{l+1} + \frac{l m_l + \cdots + m_1 - \binom{k}{2} m_k - \cdots - \binom{l+1}{2} m_{l+1}}{\frac{l+1}{2}} \right \rceil.$$

The result is particularly interesting in the case when $\pi = \langle k^m \rangle$, i.e.\ when we observe a multipartite graph with $m$ parts of size $k$, as we get $l = k$ and $$\sg(K_{\langle k^m \rangle}) \geq \left \lceil \frac{2 k m}{k + 1} \right \rceil \, .$$

On the other hand, considering a strong geodetic set consisting only of the whole parts of the bipartition yields an upper bound. At least $l \in \Z$, where $l (k + \binom{k}{2}) \geq m k$, parts must be in a strong geodetic set. Hence,
$$\sg(K_{\langle k^m \rangle}) \leq \left \lceil \frac{2 m}{k + 1} \right \rceil \cdot k \, .$$

This implies the following result.

\begin{proposition}
	\label{prop:km}
	If $k, n \in \mathbb{N}$ and $(k+1)|2m$, then $\sg(K_{\langle k^m \rangle}) = \frac{2 m k}{k + 1}$.
\end{proposition}

\section{Complexity results for multipartite graphs}
\label{sec:NP}

The strong geodetic problem can be naturally formed as a decision problem.

\vspace{2mm}
\textsc{Strong geodetic set}\\
Input: a graph $G$, an integer $k$\\
Question: does a graph $G$ have a strong geodetic set of size at most $k$?
\vspace{2mm}

The strong geodetic problem on general graphs is known to be NP-complete~\cite{MaKl16a}. In the following we prove that it is also NP-complete on multipartite graphs.

The reduction uses the dominating set problem. Recall that a set $D \subseteq V(G)$ is a dominating set in the graph $G$ if every vertex in $V(G) - D$ has a neighbor in $D$.

\vspace{2mm}
\textsc{Dominating set}\\
Input: a graph $G$, an integer $k$\\
Question: does a graph $G$ have a dominating set of size at most $k$?
\vspace{2mm}

The dominating set problem is known to be NP-complete on bipartite graphs~\cite{Liedloff}, hence it is also NP-complete on multipartite graphs. The idea of the following proof is similar to the proof that the ordinary geodetic problem restricted to chordal bipartite graphs is NP-complete~\cite{dourado}.

\begin{theorem}
	\label{thm:NPC}
	\textsc{Strong geodetic set} restricted to bipartite graphs is NP-complete.
\end{theorem}

\proof
To prove NP-completeness, we describe a polynomial reduction of \textsc{Dominating set} on bipartite graphs to \textsc{Strong geodetic set} on bipartite graphs. Let $(G,k)$ be an input for \textsc{Dominating set}, and $(X, Y)$ a bipartition of the graph $G$. Define a graph $G'$, $$V(G') = V(G) \cup \{ u_1, u_2 \} \cup \{ x' \; ; \; x \in X \} \cup \{ y' \; ; \; y \in Y \},$$
with the edges $E(G)$, $u_1 \sim u_2$, and $x \sim u_2 \sim x'$ for all $x \in X$, $y \sim u_1 \sim y'$ for all $y \in Y$. Define the sets $X' = X \cup \{ u_1 \} \cup \{ x' \; ; \; x \in X \}$, $Y' = Y \cup \{ u_2 \} \cup \{ y' \; ; \; y \in Y \}$,
and observe that $(X', Y')$ is a bipartition of the graph $G'$. Define the parameter $k' = k + |V(G)|$.

Suppose $D$ is a dominating set of the graph $G$ of size at most $k$.  Define $$D' = D \cup \{ x' \; ; \; x \in X \} \cup \{ y' \; ; \; y \in Y \}.$$ Notice that $|D'| \leq k'$. For each $x \in X \cap D$, fix geodesics
$x \sim y \sim u_1 \sim y', y \in N_G(x)$.
Similarly, for each $y \in Y \cap D$, fix $y \sim x \sim u_2 \sim x', x \in N_G(y)$.
As $D$ is a dominating set, these geodesics cover all vertices in $V(G)$. Additionally, fix geodesics $x \sim u_2 \sim x'$ for some $x \in X$, and $y \sim u_1 \sim y'$ for some $y \in Y$, to cover the vertices $u_1, u_2$. Hence, $D'$ is a strong geodetic set of the graph $G'$.

Conversely, suppose $D'$ is a strong geodetic set of $G'$ of size at most $k'$. Vertices $\{ x' \; ; \; x \in X \} \cup \{ y' \; ; \; y \in Y \}$ are all simplicial, hence they all belong to $D'$. Geodesics between them cannot cover any vertices in $V(G)$, thus $V(G) \cap D' \neq \emptyset$. Let $D = D' \cap V(G)$. Clearly, $|D| \leq k$. Consider $x \in V(G) - D$. Thus $x$ is an inner point of some $y,z$-geodesic. At most one of $y, z$ does not belong to $D$. The structure of the graph ensures that at least one of $y, z$ is a neighbor of $x$. Hence, $D$ is a dominating set of the graph $G$.
\qed

\begin{corollary}
	\label{cor:NPC}
	\textsc{Strong geodetic set} restricted to multipartite graphs is NP-complete.
\end{corollary}

In the following we consider the complexity of \textsc{Strong geodetic set} on \emph{complete} multipartite graphs. Proposition~\ref{prop:two} gives rise to the following algorithm.

Let $G$ be a graph and $(X_1, \ldots, X_r)$ its multipartition. Denote $n_i = |X_i|$, $i \in [r]$. For all $\{i, j\} \subseteq \binom{[r]}{2}$, for all subsets $R$ of $[r] - \{i,j\}$, for all $s_i \in \{0,\ldots,n_i\}$, for all $s_j \in \{0,\ldots,n_j\}$, set $S_i \subseteq X_i$ of size $s_i$, and $S_j \subseteq X_j$ of size $s_j$. Check if $S_i \cup S_j \cup \bigcup_{k \in R} X_k$ is a strong geodetic set for $G$. The answer is the size of the smallest strong geodetic set.

The time complexity of this algorithm is $O(n^2 r^2 2^r)$. This confirms the already known result that \textsc{Strong geodetic set} restricted to complete bipartite graphs is in $P$, which is an easy consequence of Theorem~\ref{thm:sg=k}. Moreover, it is now clear that the problem is solvable in quadratic time. The same holds for complete $r$-partite graphs (when $r$ is fixed). But for a general complete multipartite graph (when the size of the multipartition is part of the input), the algorithm tells us nothing about complexity.

But we also observe an analogy between the \textsc{Strong geodetic set} problem on complete multipartite graphs and the \textsc{Knapsack problem}, which is known to be NP-complete~\cite{NP}. Recall that in this problem, we are given a set of items with their weights and values, and we need to determine which items to put in a backpack, so that a total weight is smaller that a given bound and a total value is as large as possible. The approximate reduction from the \textsc{Strong geodetic set} on complete multipartite graphs to the \textsc{Knapsack problem} is the following. Let $(X_1, \ldots, X_r)$ be the parts of the complete multipartite graph. The items $x_1, \ldots, x_r$ represent those parts, a value if $x_i$ is $\binom{|X_i|}{2}$ and the weight is $|X_i|$. Thus selecting the items such that their total value is as large as possible and the total weight as small as possible, is almost the same as finding the smallest strong geodetic set of the complete multipartite graph (as Proposition~\ref{prop:two} states that at most two parts in the strong geodetic set are selected only partially). We were not able to find a reduction from the \textsc{Knapsack problem} to the \textsc{Strong geodetic set} on complete multipartite graphs. But due to the connection with the \textsc{Knapsack problem}, it seems that the problem is not polynomial. Hence we pose

\begin{conjecture}
	\label{conjecture}
	\textsc{Strong geodetic set} restricted to complete multipartite graphs is NP-complete.
\end{conjecture}

However, as already mentioned, determining the strong geodetic number of complete $r$-partite graphs for fixed $r$ is polynomial. Using a computer program (implemented in Mathematica) we derive the results shown in Table~\ref{tbl:values}.

\begin{table}[htb]
	\centering
	\begin{tabular}{ c || c || c | c || c | c | c || c | c | c | c | c }
		\hline
		$\pi$ & $\langle 1 \rangle$ & $\langle 2 \rangle$ & $\langle 1^2 \rangle$ & $\langle 3 \rangle$ & $\langle 1,2 \rangle$ & $\langle 1^3 \rangle$ & $\langle 4 \rangle$ & $\langle 1,3 \rangle$ & $\langle 2^2 \rangle$ & $\langle 1^2, 2 \rangle$ & $\langle 1^4 \rangle$ \\ \hline \hline
		$\sg(K_{\pi})$ & 1 & 2 & 2 & 3 & 2 & 3 & 4 & 3 & 3 & 3 & 4 \\
		\hline
	\end{tabular}

	\medskip

	\begin{tabular}{ c || c | c | c | c | c | c | c }
		\hline
		$\pi$ & $\langle 5 \rangle$ & $\langle 1,4 \rangle$ & $\langle 2,3 \rangle$ & $\langle 1^2, 3 \rangle$ & $\langle 1, 2^2 \rangle$ & $\langle 1^3, 2 \rangle$ & $\langle 1^5 \rangle$  \\ \hline \hline
		$\sg(K_{\pi})$ & 5 & 4 & 3 & 3 & 4 & 4 & 5  \\
		\hline
	\end{tabular}

	\medskip

	\begin{tabular}{ c || c | c | c | c | c | c | c | c | c | c | c }
		\hline
		$\pi$ & $\langle 6 \rangle$ & $\langle 1,5 \rangle$ & $\langle 2,4 \rangle$ & $\langle 1^2,4 \rangle$ & $\langle 3^2 \rangle$ & $\langle 1,2,3 \rangle$ & $\langle 1^3,3 \rangle$ & $\langle 2^3 \rangle$ & $\langle 1^2,2^2 \rangle$ & $\langle 1^4, 2 \rangle$ & $\langle 1^6 \rangle$ \\ \hline \hline
		$\sg(K_{\pi})$ & 6 & 5 & 4 & 4 & 3 & 3 & 3 & 4 & 4 & 5 & 6 \\
		\hline
	\end{tabular}

	\medskip

	\begin{tabular}{ c || c | c | c | c | c | c | c | c }
		\hline
		$\pi$ & $\langle 7 \rangle$ & $\langle 1,6 \rangle$ & $\langle 2,5 \rangle$ & $\langle 1^2,5 \rangle$ & $\langle 3,4 \rangle$ & $\langle 1,2,4 \rangle$ & $\langle 1^3,4 \rangle$ & $\langle 1,3^2 \rangle$ \\ \hline \hline
		$\sg(K_{\pi})$ & 7 & 6 & 5 & 5 & 4 & 4 & 4 & 4 \\
		\hline
	\end{tabular}

	\medskip

	\begin{tabular}{ c || c | c | c | c | c | c | c }
		\hline
		$\pi$ & $\langle 2^2,3 \rangle$ & $\langle 1^2,2,3 \rangle$ & $\langle 1^4,3 \rangle$ & $\langle 1,2^3 \rangle$ & $\langle 1^3,2^2 \rangle$ & $\langle 1^5,2 \rangle$ & $\langle 1^7 \rangle$ \\ \hline \hline
		$\sg(K_{\pi})$ & 4 & 4 & 4 & 5 & 5 & 6 & 7 \\
		\hline
	\end{tabular}

	\caption{The strong geodetic numbers for some small complete multipartite graphs.}
	\label{tbl:values}
\end{table}

\section*{Acknowledgments}
\label{sec:Acknowledgments}

The authors would like to thank Sandi Klav\v zar and Valentin Gledel for a number of helpful conversations and suggestions.


text:
(* Title:      Subalgebras of Kleene Relation Algebras
   Author:     Walter Guttmann
   Maintainer: Walter Guttmann <walter.guttmann at canterbury.ac.nz>
*)

section \<open>Subalgebras of Kleene Relation Algebras\<close>

text \<open>
In this theory we show that the regular elements of a Stone-Kleene relation algebra form a Kleene relation subalgebra.
\<close>

theory Kleene_Relation_Subalgebras

imports Stone_Relation_Algebras.Relation_Subalgebras Kleene_Relation_Algebras

begin

instantiation regular :: (stone_kleene_relation_algebra) kleene_relation_algebra
begin

lift_definition star_regular :: "'a regular \<Rightarrow> 'a regular" is star
  using regular_closed_p regular_closed_star by blast

instance
  apply intro_classes
  apply (metis (mono_tags, lifting) star_regular.rep_eq less_eq_regular.rep_eq left_kleene_algebra_class.star_left_unfold one_regular.rep_eq simp_regular sup_regular.rep_eq times_regular.rep_eq)
  apply (metis (mono_tags, lifting) less_eq_regular.rep_eq left_kleene_algebra_class.star_left_induct simp_regular star_regular.rep_eq sup_regular.rep_eq times_regular.rep_eq)
  apply (metis (mono_tags, lifting) less_eq_regular.rep_eq strong_left_kleene_algebra_class.star_right_induct simp_regular star_regular.rep_eq sup_regular.rep_eq times_regular.rep_eq)
  by simp

end

end

subset_name: curated


TITLE: Possible values of $\lim_{x \rightarrow \infty} \left(\frac{p(x)}{q(x)}\right)^x$
QUESTION [3 upvotes]: I was asked by some freshmen the follwing two questions regarding the limit:

Using the fact that
$$\lim_{x \rightarrow \infty} \left(1 + \frac{1}{x}\right)^x = e$$
evaluate
$$\lim_{x \rightarrow \infty} \left(1 + \frac{3}{x^2}\right)^x$$
$$\lim_{x \rightarrow \infty} \left(\frac{x^2-2x-3}{x^2-3x-28}\right)^x$$

I got the answers $1$ and $e$ respectively. Hope nothing wrong.
In the second question, my attempt is like this:
$$\frac{x^2-2x-3}{x^2-3x-28} = \frac{(x-3)(x+1)}{(x-7)(x+4)}$$
$$\lim_{x \rightarrow \infty} \left(\frac{x-3}{x-7}\right)^x = e^{4}$$
$$\lim_{x \rightarrow \infty} \left(\frac{x+1}{x+4}\right)^x = e^{-3}$$
$$\lim_{x \rightarrow \infty} \left(\frac{x^2-2x-3}{x^2-3x-28}\right)^x = e^4e^{-3} = e$$
We can also do the other way round:
$$\lim_{x \rightarrow \infty} \left(\frac{x-3}{x+4}\right)^x = e^{-7}$$
$$\lim_{x \rightarrow \infty} \left(\frac{x+1}{x-7}\right)^x = e^{8}$$
Indeed, the power of $e$ in the final answer is the difference of the sums of roots of $x^2-2x-3$ in the numerator and $x^2-3x-28$ in the denominator.

From this question, I suspect that
$$\lim_{x \rightarrow \infty} \left(\frac{x^n + \alpha_{n-1} x^{n-1} + \ldots + \alpha_0}{x^n + \beta_{n-1} x^{n-1} + \ldots + \beta_0}\right)^x = e^{\alpha_{n-1} - \beta_{n-1}}$$
is true, but I have no idea how to prove it, if the polynomials are not able to be factorized.
The freshmen had not learnt the rule yet. It would be good if there is a proof without using the rule to let them know an easy way to check their answers and why this way holds.

REPLY [2 votes]: Let $c=a_{n-1}-b_{n-1}$. Assume $c\ne 0$.
Let $p(x)=(a_{n-1}-b_{n-1})^{-1}\left((a_{n-1}-b_{n-1}) x^{n-1} + \dots + a_0-b_0\right)$.
Let $q(x)=x^n + b_{n-1} x^{n-1} + \dots + b_0$.
Let $f(x)=\left(1+c\frac{p(x)}{q(x)}\right)^\frac{q(x)}{p(x)}$.
Let $g(x)=\frac{xp(x)-q(x)}{q(x)}$.
$$\left(\frac{x^n + a_{n-1} x^{n-1} + \dots + a_0}{x^n + b_{n-1} x^{n-1} + \dots + b_0}\right)^x = \left(1+\frac{(a_{n-1}-b_{n-1}) x^{n-1} + \dots + a_0-b_0}{x^n + b_{n-1} x^{n-1} + \dots + b_0}\right)^x = \left(1+c\frac{p(x)}{q(x)}\right)^x=\left(\left(1+c\frac{p(x)}{q(x)}\right)^\frac{q(x)}{p(x)}\right)^{1+\frac{xp(x)-q(x)}{q(x)}}=f(x)f(x)^{g(x)}$$
$f(x)\to e^c$ as $x\to\infty$, since $\frac{q(x)}{p(x)}\to\infty$.
For large $x$, $f(x)\in e^c\times [\frac{1}{2},2]$.
For large $x$, $g(x)\in M\times[-\frac{1}{x},\frac{1}{x}]$, for some $M$.
So, for large $x$, $f(x)^{g(x)}\in [2^{-M\frac{1}{x}},2^{M\frac{1}{x}}]$, both of which $\to 1$.
So $f(x)^{g(x)}\to 1$ as $x\to\infty$ by squeeze theorem.
Hence $\left(\frac{x^n + a_{n-1} x^{n-1} + \dots + a_0}{x^n + b_{n-1} x^{n-1} + \dots + b_0}\right)^x\to e^c$ as $x\to\infty$.


TITLE: Nuclear physics on gravitational background
QUESTION [1 upvotes]: Is there any treatment on nuclear physics in strong gravitational fields? (I tried to search over the Internet, but found references only on QFT on gravitational background)

REPLY [0 votes]: I would say, no, because they are descriptions that are relevant at very different scales (but there might be...). There are very few and remote settings where both gravity and particle physics play role. So let alone the nuclear regime, which pertains to energies that are somewhat lower than in particle physics.
As an example imagine you are trying to describe the motion of planets around the sun while simultaneously accounting for the mass shift because of ants moving on the earth.
So the question I can return to you is actually what kind of scenario are you imagining where gravity and nuclear forces are simultaneously relevant?


text:
\begin{document}
\subjclass[2010]{35J62, 35B05, 35A24, 35B09, 34B18.}

\keywords{Lorentz-Minkowski mean curvature operator, Shooting method,
Existence and multiplicity, Oscillating solutions, Neumann boundary conditions.}

\title[Positive solutions for the Minkowski-curvature equation]{Positive radial solutions for the Minkowski-curvature equation  with Neumann boundary conditions}

\author[A. Boscaggin]{Alberto Boscaggin}
\address{Alberto Boscaggin\newline\indent
Dipartimento di Matematica ``Giuseppe Peano''
\newline\indent
Universit\`a di Torino
\newline\indent
via Carlo Alberto 10, 10123 Torino, Italia}
\email{alberto.boscaggin@unito.it}

\author[F. Colasuonno]{Francesca Colasuonno}
\address{Francesca Colasuonno\newline\indent
Dipartimento di Matematica ``Giuseppe Peano''
\newline\indent
Universit\`a di Torino
\newline\indent
via Carlo Alberto 10, 10123 Torino, Italia}
\email{francesca.colasuonno@unito.it}

\author[B. Noris]{Benedetta Noris}
\address{Benedetta Noris
\newline \indent Laboratoire Ami\'enois de Math\'ematique Fondamentale et Appliqu\'ee\newline\indent
Universit\'e de Picardie Jules Verne\newline\indent
33 rue Saint- Leu, 80039 AMIENS, France}
\email{benedetta.noris@u-picardie.fr}

\date{\today}

\begin{abstract}
We analyze existence, multiplicity and oscillatory behavior of positive radial solutions to a class of quasilinear equations governed by the Lorentz-Minkowski mean curvature operator. The equation is set in a ball or an annulus of $\mathbb R^N$, is subject to homogeneous Neumann boundary conditions, and involves a nonlinear term on which we do not impose any growth condition at infinity. The main tool that we use is the shooting method for ODEs.
\end{abstract}

\maketitle
\begin{quotation}
{\sl Dedicated to Professor Patrizia Pucci, on the occasion of her 65th birthday, with great esteem.}
\end{quotation}

\section{Introduction}
In this paper we deal with the existence and multiplicity of solutions to the nonlinear boundary value problem
\begin{equation}\label{eq:main}
\left\{
\begin{array}{ll}
\vspace{0.1cm}
\displaystyle{-\mathop{\rm div}\left(\frac{\nabla u}{\sqrt{1-|\nabla u|^2}}\right) = f(u)} & \mbox{ in } \Omega \\
\vspace{0.1cm}
u > 0 & \mbox{ in } \Omega \\
\partial_\nu u = 0 & \mbox{ on } \partial\Omega, \\
\end{array}
\right.
\end{equation}
where $\nu$ is the outer unit normal of $\partial \Omega$ and $\Omega\subset\mathbb R^N$ ($N\geq1$) is a radial domain which can be either an annulus
$$
\Omega=\mathcal A(R_1,R_2):=\{ x \in \mathbb{R}^N \, : \, R_1 < \vert x \vert < R_2 \},\quad 0<R_1<R_2<+\infty,
$$
or a ball
$$
\Omega=\mathcal B(R_2):=\{ x \in \mathbb{R}^N \, : \vert x \vert < R_2 \},\quad 0<R_2<+\infty.
$$
Throughout the paper, in order to treat simultaneously the cases of the annulus and of the ball, we use the convention $R_1=0$ when $\Omega=\mathcal B(R_2)$.
We are interested in radial, $C^2(\overline{\Omega})$ solutions of \eqref{eq:main}, thus writing, with the usual abuse of notation, $u(x) = u(r)$ for $r = \vert x \vert$.

The nonlinear differential operator appearing in \eqref{eq:main} is usually meant as a mean curvature operator in the Lorentz-Minkowski space
and it is of interest in Differential Geometry and General Relativity \cite{BaSi-8283,Ecker,Ge-83}; it also appears in the nonlinear theory of Electromagnetism, where it is usually referred to as Born-Infeld operator \cite{BoCoFo-pp,BdAP-16,BoIa-pp}. In recent years, it has become very popular among specialists in Nonlinear Analysis, and various existence/multiplicity results for the associated boundary value problems are available, both in the ODE and in the PDE case, possibly in a non-radial setting (see, among others, \cite{Az-14,Az-16,BeJeMa-09,BeJeTo-13,BeJeTo-13a,BeMa-07,BoFe-pp,BoGa-ccm,CoCoObOm-12,CoelhoCorsatoRivetti,CoObOmRi-13,DW,Ma-13} and the references therein).

In this paper, we focus on the Neumann boundary value problem \eqref{eq:main}. Notice that, differently from the Dirichlet problem, solutions cannot exist if $f$ has constant sign; therefore, we are led to assume that $f$ has a zero $s_0 > 0$ (and, thus, $u \equiv s_0$ is a constant solution to \eqref{eq:main}).
As a prototype nonlinearity, we can think at the following difference of pure powers
\begin{equation}\label{eq:prototype}
f(s)=s^{q-1}-s^{r-1} \quad \mbox{with } 2\leq r<q<+\infty,
\end{equation}
which indeed satisfies $f(s_0) = 0$ for $s_0 = 1$.

In such a situation, it has been shown in some recent papers \cite{BonheureGrossiNorisTerracini2015, bonheure2016multiple,BNW,ABF2,
ABF,ma2016bonheure} that non-constant positive Neumann solutions to the semilinear equation
$$
-\Delta u = f(u)
$$
can be provided and characterized in terms of the intersection with the constant solution $u \equiv s_0$. More precisely, in \cite{ABF2,ABF}
it is proved that, if $f'(s_0)$ is greater than the $k$-th eigenvalue of the radial Neumann problem for $-\Delta u = \lambda u$, then
a solution with $u(R_1) < s_0$, having exactly $k$ intersections with $s_0$ always exists (incidentally, let us recall that this provides a positive answer to the conjecture raised in \cite{BNW}). Moreover, a solution with $u(R_1) > s_0$ and having exactly $k$ intersections with $s_0$ also exists, if we further assume that $f$ satisfies suitable sub-criticality growth conditions at infinity (that is, in the case of the ball, $q < 2^*$ for the prototype nonlinearity \eqref{eq:prototype}).
We note in passing that in \cite{ABF2,ABF,ColasuonnoNoris,CNproc} a similar analysis is performed for quasilinear problems governed by the $p$-Laplacian operator, cf. also \cite{PS1} for ground state solutions.  Furthermore, the case of exponential nonlinearities is treated in \cite{BCN,PS2}.

The aim of the present paper is to show that the above multiplicity pattern can still be provided for the strongly nonlinear problem \eqref{eq:main}: even more, due to the singular character of the Minkowski-curvature operator, the existence of solutions with $u(R_1) > s_0$ does not require any sub-criticality condition. Indeed, we work with a minimal set of assumptions for $f$; precisely, we just assume
\begin{itemize}
\item[$(f_\textrm{reg})$] $f \in \mathcal{C}^1([0,+\infty))$;
\item[$(f_\textrm{eq})$] $f(0) = f(s_0) = 0$, $f(s) < 0$ for $0 < s < s_0$ and $f(s) > 0$ for $s > s_0$.
\end{itemize}

In order to state our main result, we need to introduce the radial eigenvalue problem for the Laplacian with homogeneous Neumann boundary conditions in $\Omega$, that is
\begin{equation}\label{eq:eigenv_radial}
-(r^{N-1} u')'=\lambda r^{N-1} u \quad\text{in } (R_1,R_2) \qquad u'(R_1)=u'(R_2)=0.
\end{equation}
It is well known that all the eigenvalues are simple and arranged in an increasing sequence
\[
0=\lambda_1^{\mathrm{rad}}<\lambda_2^{\mathrm{rad}}<\ldots<\lambda_k^{\mathrm{rad}}<\ldots\to+\infty
\]
(for additional information concerning this problem see Appendix \ref{sec:5} ahead).
The main result of the paper is the following.

\begin{theorem}\label{thm:main}
Let $\Omega$ be either the annulus $\mathcal A(R_1,R_2)$ or the ball $\mathcal B(R_2)$ and let $f$ satisfy $(f_\textrm{reg})$, $(f_\textrm{eq})$ and
\begin{itemize}
\item[$(f_{s_0})$] for some integer $k \geq 1$ it holds $f'(s_0) > \lambda_{k+1}^{\textnormal{rad}}$.
\end{itemize}
Then there exist at least $2k$ distinct non-constant radial solutions $u_1,\ldots,u_{2k}$ to \eqref{eq:main}.
Moreover, we have
\begin{itemize}
\item[(i)] $u_j(R_1)<s_0$ for every $j=1,\ldots,k$;
\item[(ii)] $u_j(R_1)>s_0$ for every $j=k+1,\ldots,2k$;
\item[(ii)] $u_j(r)-s_0$ and $u_{j+k}(r)-s_0$ have exactly $j$ zeros for $r\in(R_1,R_2)$, for every $j=1,\ldots,k$.
\end{itemize}
\end{theorem}

For the proof of Theorem \ref{thm:main}, similarly as in the papers \cite{ABF2,ABF,MontefuscoPucci} we use a shooting approach for the equivalent ODE problem
\begin{equation}\label{eq:main_radial}
\begin{cases}
\left(r^{N-1} \frac{u'}{\sqrt{1-(u')^2}}\right)'+r^{N-1} f(u)=0 \qquad r\in (R_1,R_2)\\
u > 0 \\
u'(R_1)=u'(R_2)=0.
\end{cases}
\end{equation}
Precisely, we first write the equation as the equivalent first order system
\begin{equation}\label{sys:intro}
u' = \frac{v}{r^{N-1}\sqrt{1+ (v/r^{N-1})^2}}, \qquad v' = - r^{N-1} f(u),
\end{equation}
and we then look for values $d \in (0,+\infty) \setminus \{s_0\}$ such that the solution
$(u_d,v_d)$ with initial condition $(u_d(R_1),v_d(R_1)) = (d,0)$ satisfies $v_d(R_2) = 0$. Due to the assumption $(f_\textrm{eq})$, solutions $(u_d,v_d)$ wind around the equilibrium point $(s_0,0)$ in the clockwise sense and, actually, the number of half-turns around such a point is nothing but the number of intersections of $u_d$ with the constant solution $u \equiv s_0$ (see Figure \ref{fig:polar_coord}).
By estimating, via assumption $(f_{s_0})$, the number of half-turns around $(s_0,0)$ when $d \to s_0$ and the number of half-turns when $d \to 0^+$ and $d \to +\infty$, the existence of solutions making a precise number of half-turns follows from a continuity argument, cf. Fig. \ref{fig:num_giri}.
\begin{figure}[h]
\includegraphics[scale=0.8]{C1maggiore0.pdf}
\caption{Number of half-turns performed by the solutions of the Cauchy problem $(u(R_1),v(R_1))=(d,0)$ associated with \eqref{sys:intro} varying with the initial condition $u(R_1)=d$. The existence of a bound from above $d^*$ for the initial data $d$ in correspondence to which the solutions of the Cauchy problem perform at least one half-turn in the phase plane is a consequence of the fact that $|u'|\le 1$, see \eqref{sys:intro}.}\label{fig:num_giri}
\end{figure}
It is interesting to observe that the singular character of the Minkowski operator reflects into the fact that the right-hand side in the equation for $u'$ (see \eqref{sys:intro}) is globally bounded, this being ultimately the reason why no-subcriticality conditions are needed in this setting.
On the contrary, as already mentioned, when the equation is governed by the Laplacian (cf. \cite{bonheure2016multiple}) or the $p$-Laplacian operator (cf. \cite{ABF2,CNproc}), the existence of solutions having $u(R_1)>s_0$ could be proved only if the nonlinearity $f$ is Sobolev-subcritical. Indeed, this additional assumption allows to prove a priori estimates on the solutions, which are crucial in the proof of a bound $d^*$ from above of initial data $d$ and eventually in the proof of the existence of solutions with $u(R_1)>s_0$. The necessity of such a growth condition is also confirmed by numerical evidence in \cite[Fig. 16]{bonheure2016multiple}.

In the case of the prototype nonlinearity \eqref{eq:prototype}, Theorem~\ref{thm:main} reduces to the following result.

\begin{corollary}\label{cor:prot}
Let $\Omega$ be either the annulus $\mathcal A(R_1,R_2)$ or the ball $\mathcal B(R_2)$ and let $f(s)=s^{q-1}-s^{r-1}$ with $r\geq2$ and $q-r>\lambda_{k+1}^{\mathrm{rad}}$ for some integer $k\ge 1$.
Then there exist at least $2k$ distinct non-constant radial solutions $u_1,\ldots,u_{2k}$ to \eqref{eq:main}.
Moreover, we have
\begin{itemize}
\item[(i)] $u_j(R_1)<1$ for every $j=1,\ldots,k$;
\item[(ii)] $u_j(R_1)>1$ for every $j=k+1,\ldots,2k$;
\item[(ii)] $u_j(r)-1$ and $u_{j+k}(r)-1$ have exactly $j$ zeros for $r\in(R_1,R_2)$, for every $j=1,\ldots,k$.
\end{itemize}
\end{corollary}

To illustrate better our results stated in Theorem \ref{thm:main} and Corollary \ref{cor:prot}, we present below some numerical simulations performed with the software AUTO-07P \cite{AUTO}. In the simulations we consider the following special case of \eqref{eq:main_radial}:
\begin{equation}\label{eq:rad_prot}
\begin{cases}
\left(r^{N-1} \frac{u'}{\sqrt{1-(u')^2}}\right)'+r^{N-1} (-u^2+u^{q-1})=0 \qquad r\in (0,1)\\
u > 0 \\
u'(0)=u'(1)=0,
\end{cases}
\end{equation}
with $q>3$ and $N=1,2$. In Figures \ref{fig:dim1} (a) and \ref{fig:dim2} (a) below, we represent $u(0)$ as a function of $q$. The black horizontal line corresponds to the constant solution $u\equiv s_0=1$. We can see that, as soon as the exponent $q$ overcomes a value of the form $3+\lambda_{k+1}^{\mathrm{rad}}$ ($k\ge1$), a new branch of solutions appears and each of these branches bifurcates from the constant solution. Furthermore, in Figures \ref{fig:dim1} (b) and \ref{fig:dim2} (b) we plot a selection of nonconstant solutions, in order to show their oscillatory behavior. It can be seen that solutions belonging to different branches present different oscillatory behaviors, so that the appearance of a new branch of solutions indicates the existence of a new solution with a different oscillatory behavior. This is coherent with the multiplicity result stated in Corollary \ref{cor:prot}.
We can finally observe from the simulations (a), that while in dimension $N=1$ the values $3+\lambda_{k+1}^{\mathrm{rad}}$ seem to be optimal in $q$ for the existence of a new solution having a different oscillatory behavior, in dimension $N=2$ the bifurcation points are of different type (called {\it transcritical}) and so, for instance, a nonconstant (decreasing) solution can be expected to exist also in correspondence to values of $q$ that are very close to, but {\it smaller} than $3+\lambda_2^{\mathrm{rad}}$. An analogous situation has been detected and analytically proved via bifurcation theory, for the semilinear problem in \cite{bonheure2016multiple}. It would be interesting to perform a bifurcation analysis also in the quasilinear case and to prove analytically the numerical evidence that the branches of nonconstant solutions actually bifurcate from the branch of constant solutions $u\equiv s_0$.
\begin{figure}[h!]
\includegraphics[width=\textwidth]{dim1.pdf}
\caption{(a) Partial bifurcation diagram in dimension $N=1$, with $R_1=0$, $R_2=1$, and $s_0=1$. (b) Graphs of eight solutions belonging to the four branches represented in (a). The colour of each solution is the same as the branch it belongs to. For each branch we have selected two solutions, one with $u(0)>1$ and the other with $u(0)<1$. The solutions displayed correspond to different values of $q$.}\label{fig:dim1}
\end{figure}
\begin{figure}[h!]
\includegraphics[width=\textwidth]{dim2.pdf}
\caption{(a) Partial bifurcation diagram in a unit disk (i.e., $R_1=0$, $R_2=1$, and $N=2$), with $s_0=1$. (b) Solutions corresponding to $q=70$.}\label{fig:dim2}
\end{figure}

The plan of the paper is the following. In Section \ref{sec:2} we prove some preliminary results for the (possibly singular) Cauchy problem $(u(R_1),v(R_1)) = (d,0)$ associated with \eqref{sys:intro}. In Section \ref{sec:3} we estimate, using a trick based on a system of scaled polar coordinates, the number of half-turns around the equilibrium point $(s_0,0)$ of solutions $(u_d,v_d)$ with $d \to s_0$. Finally, in Section \ref{sec:3} we give the proof of Theorem~\ref{thm:main}.
The paper ends with Appendix \ref{sec:5}, where we recall some known results for the radial Neumann eigenvalue problem for $-\Delta u = \lambda u$.

\section{The Cauchy problem}\label{sec:2}
In all the paper we will assume that $\Omega$ is either the annulus $\mathcal A(R_1,R_2)$ or the ball $\mathcal B(R_2)$ and that $f$ satisfies $(f_\textrm{reg})$ and $(f_\textrm{eq})$.

Let us introduce the trivial extension of $f$
\begin{equation}\label{eq:f_hat}
\hat f(s):=\begin{cases}
	f(s) \quad&\text{if } s \geq 0\\
	0 &\text{if } s < 0,
\end{cases}
\end{equation}
which is continuous thanks to $(f_\textrm{eq})$.
We consider the radial problem
\begin{equation}\label{eq:radial}
\begin{cases}
(r^{N-1} \varphi(u'))'+r^{N-1}\hat f(u)=0 \qquad r\in (R_1,R_2)\\
u'(R_1)=u'(R_2)=0.
\end{cases}
\end{equation}
Here, with the usual abuse of notation, $u(r)=u(|x|)$, the prime symbol $'$ denotes the derivative with respect to $r$, and
\begin{equation}\label{eq:phi_def}
\varphi(s):=\frac{s}{\sqrt{1-s^2}}.
\end{equation}
For future use, note that $\varphi$ is invertible with inverse
\[
\varphi^{-1}(t)=\frac{t}{\sqrt{1+t^2}}
\]
and that
\begin{equation}\label{eq:inverse-phi}
|\varphi^{-1}(t)|<1 \qquad\text{for all } t\in\R.
\end{equation}
We shall see (cf. Lemma \ref{lem:hat_f} at the end of this section) that $u$ is a nonconstant radial solution of \eqref{eq:main} if and only if $u$ is a nonconstant solution of \eqref{eq:radial}.

Before doing that, we prove uniqueness, global continuability and regularity for the associated Cauchy problem; hence we consider, for every $d\geq 0$,
\begin{equation}\label{eq:shooting}
\begin{cases}
u'=\varphi^{-1}\left(\frac{v}{r^{N-1}}\right) \qquad & r\in (R_1,R_2)\\
v'=-r^{N-1} \hat f(u) \qquad & r\in (R_1,R_2) \\
u(R_1)=d \\
v(R_1)=0.
\end{cases}
\end{equation}
We note that, despite the presence of the term $v/r^{N-1}$ (which is singular if $N \geq 2$ and $R_1 = 0$), using \eqref{eq:inverse-phi} it follows that the right hand side of the above system, that is $F:(R_1,R_2)\times\R^2\to \R^2$ defined as
\[
F(r,(u,v)) :=
\left(\varphi^{-1}\left(\frac{v}{r^{N-1}}\right), -r^{N-1} \hat f(u)\right),
\]
is an $L^\infty$-Carath\'eodory function, namely
\begin{itemize}
\item[(i)] $F(\cdot,(u,v))$ is measurable for every $(u,v)\in \R^2$;
\item[(ii)] $F(r,\cdot)$ is continuous for almost every $r\in (R_1,R_2)$;
\item[(iii)] for every $K>0$ there exists $C_K>0$ such that $|F(r,(u,v))|\leq C_K$ for almost every $r \in (R_1,R_2)$ and for every $(u,v)\in\R^2$ with $|(u,v)|\leq K$.
\end{itemize}
Hence, by the Peano existence theorem for ODEs with $L^\infty$-Carath\'eodory right hand side (see for example \cite[Section 1.5]{Hale}), the existence of a local $W^{1,\infty}$ solution of \eqref{eq:shooting} is guaranteed. Below, we prove uniqueness, higher regularity and global continuability for such a solution, henceforth denoted by $(u_d,v_d)$, as well as a continuous dependence result.

\begin{lemma}\label{lem:uniqueness_Cauchy}
For every $d\geq 0$, the local $W^{1,\infty}$ solution $(u_d,v_d)$ of \eqref{eq:shooting} is unique and can be defined on the whole $[R_1,R_2]$; moreover, $u_d$ is of class $C^2([R_1,R_2])$, with $u_d'(R_1) = 0$.

In addition, if $(d_n)\subset [0,+\infty)$ is such that $d_n\to d\in [0,+\infty)$ as $n\to+\infty$, then
\begin{equation}\label{eq:dip_cont}
(u_{d_n}(r),v_{d_n}(r))\to (u_d(r),v_d(r))\quad \mbox{uniformly for }r\in [R_1,R_2],
\end{equation}
\begin{equation}\label{eq:dip_cont_u'}
u'_{d_n}(r)\to u'_d(r) \quad \mbox{uniformly for }r\in [R_1,R_2].
\end{equation}

\end{lemma}
\begin{proof} We first observe that any solution $(u_d,v_d)$ can be defined in $[R_1,R_2]$. Indeed, since $|u'_d|<1$ by \eqref{eq:inverse-phi} and \eqref{eq:shooting}, we obtain
$$
|u_d(r)|\le d+\int_{R_1}^r |u_d'(s)|ds \le d+R_2-R_1
$$
and consequently
$$
|v_d(r)|\le  \int_{R_1}^r s^{N-1}|\hat f(u_d(s))|ds \le \frac{(R_2-R_1)^N}{N} \max_{|s|\le d+R_2-R_1}|\hat f(s)|
$$
for every $\textcolor{blue}{R_1\le}r\le R_2$ in the maximal interval of definition of the solution $(u_d,v_d)$.
Hence, $(u_d,v_d)$ cannot blow-up in a finite interval, proving that it can be globally extended in $[R_1,R_2]$.

In the rest of the proof we suppose $R_1=0$, since the result is standard in case $R_1>0$.
In order to prove uniqueness, let $(u_d,v_d)$ and $(\bar u_d,\bar v_d)$ be two distinct solutions of \eqref{eq:shooting} and define $(U,V):=(\bar u_d-u_d,\bar v_d-v_d)$. Then $(U,V)$ is a solution of the following problem
\begin{equation}\label{pb:U'V'}
\begin{cases}
&U'=\varphi^{-1}\left(\frac{\bar v_d}{r^{N-1}}\right)-\varphi^{-1}\left(\frac{v_d}{r^{N-1}}\right)\\
&V'=-r^{N-1}(\hat f(\bar u_d)-\hat f(u_d))\\
&U(0)=V(0)=0.
\end{cases}
\end{equation}
Using the local-Lipschitz continuity of $\varphi^{-1}$ and $\hat f$ we find
\begin{equation*}
|U'(r)|\le K \frac{|V(r)|}{r^{N-1}} \quad\mbox{and}\quad |V'(r)|\le K r^{N-1}|U(r)|
\end{equation*}
for a.e. $r\in [0,R_2]$, where $K > 0$ is a suitable constant.
Then,
$$
\begin{aligned}
|U(r)|&\le \int_{0}^r |U'(s)| ds\le K\int_0^r  \frac{|V(s)|}{s^{N-1}}ds\le
K\int_{0}^r \frac{1}{s^{N-1}}\left(\int_0^s |V'(t)|dt\right) ds \\
&\le
K^2 \int_{0}^r \frac{1}{s^{N-1}}\left(\int_0^s t^{N-1}|U(t)|dt\right) ds
\le K^2 \int_{0}^r \left(\int_0^s|U(t)|dt\right) ds\\
& \le K^2 R_2 \int_{0}^r |U(t)|dt
\end{aligned}
$$
for every $r\in [0,R_2]$.
Hence, by Gronwall's Lemma,
$$
U(r)=0\quad	\mbox{for every }r\in [0,R_2]
$$
and consequently, using \eqref{pb:U'V'}, also $V(r)=0$ for every $[0,R_2]$.

We now prove that $u_d$ is of class $C^1([0,R_2])$, with $u_d'(0) = 0$. By the second equation in \eqref{eq:shooting}, we obtain
$$
\left\vert \frac{v_d(r)}{r^{N-1}}\right \vert = \left\vert \int_{0}^r \left( \frac{s}{r}\right)^{N-1} \hat f(u_d(s))\,ds\right \vert
\leq \int_{0}^r \vert \hat f(u_d(s)) \vert\,ds.
$$
Therefore,
$$
\frac{v_d(r)}{r^{N-1}} \to 0, \quad \mbox{ as } r \to 0^+,
$$
and consequently, by the continuity of $\varphi^{-1}$, we conclude that $u_d'$ can be continuously extended up to $r = 0$ with $u_d'(0) = 0$.

In order to show that $u_d$ is of class $C^2([0,R_2])$, following \cite[Remark 3.3]{CoelhoCorsatoRivetti} let us prove that
\begin{equation}\label{eq:u_d_C2}
\lim_{r\to0^+} \frac{\varphi(u'_d(r))}{r}=-\frac{\hat f(d)}{N}.
\end{equation}
To this aim, fix $\varepsilon>0$. By the continuity of $\varphi$ and of $u_d$, there exists $\delta>0$ such that $|\hat f(d)-\hat f(u_d(s \textcolor{blue}{r}))|<\varepsilon$ for every $s\textcolor{blue}{r}\in[0,\delta)$. Taking $r\in (0,\delta)$, we have
\begin{multline*}
\left| \frac{\hat f(d)}{N} +\frac{\varphi(u_d'(r))}{r}\,\right|=
\left| \frac{\hat f(d)}{N} -\frac{1}{r^N}\int_{0}^r s^{N-1} \hat f(u_d(s))\,ds\,\right| \\
=\left| \frac{1}{r^N} \int_0^r s^{N-1} \left( \hat f(d)-\hat f(u_d(s)) \right) \,ds \,\right|
\leq \frac{\varepsilon}{N},
\end{multline*}
so that \eqref{eq:u_d_C2} holds. As a consequence, $\varphi(u'_d)$ is of class $C^1([0,R_2])$, which implies, being $\varphi^{-1}$ regular, that $u_d$ is of class $C^2([0,R_2])$.

Concerning the continuous dependence, the proof of \eqref{eq:dip_cont} is a standard argument based on the Ascoli-Arzel\`a Theorem.
We now prove \eqref{eq:dip_cont_u'}. Let $d_n\to d$, then, by the second equation in \eqref{eq:shooting}, we get for every $r\in [R_1,R_2]$
\begin{multline}
\left\vert \frac{v_{d_n}(r)-v_d(r)}{r^{N-1}}\right \vert = \left\vert \int_{0}^r \left( \frac{s}{r}\right)^{N-1} [\hat f(u_{d_n}(s))-\hat f(u_d(s))]\,ds\right \vert\\
\leq \int_{0}^r \vert \hat f(u_{d_n}(s))-\hat f(u_d(s)) \vert\,ds \to 0 \quad\mbox{as } n\to\infty,
\end{multline}
where in the last step we used \eqref{eq:dip_cont} and the continuity of $\hat f$.
Finally, by the first equation in \eqref{eq:shooting} and the continuity of $\varphi^{-1}$, \eqref{eq:dip_cont_u'} follows.
\end{proof}

\begin{remark}
Let us notice that, in the case $R_1 = 0$, the above lemma implies that $v_d(r)/r^{N-1}$ can be continuously extended \textcolor{blue}{to 0} up to $r = 0$ and that
(cf. \eqref{eq:dip_cont_u'})
\begin{equation}\label{eq:dip_cont_vr}
\frac{v_{d_n}(r)}{r^{N-1}}\to \frac{v_d(r)}{r^{N-1}} \quad \mbox{uniformly for }r\in [0,R_2].
\end{equation}
\end{remark}
We conclude the section with a maximum-type principle.

\begin{lemma}\label{lem:hat_f} The function
$u$ is a radial solution of \eqref{eq:main} if and only if $u$ solves \eqref{eq:radial} and $u\not\equiv -C$ with $C\geq0$.
\end{lemma}
\begin{proof}
Proceeding exactly as in \cite[Lemma 2.1]{ABF}, one can prove that if $u$ solves \eqref{eq:radial} and $u\not\equiv -C$ with $C\geq0$ then $u\geq0$.
It only remains to show that $u(r)>0$ for $r\in [R_1,R_2]$. To this aim, suppose by contradiction that there exists $\bar r \in [R_1,R_2]$ such that $u(\bar r)=0$, then also $u'(\bar r)=0$. If $\bar r>0$, the standard Cauchy-Lipschitz theory implies that $u\equiv0$, which is a contradiction. Otherwise $\bar r=0$, and we proved in Lemma \ref{lem:uniqueness_Cauchy} that also in this case $u\equiv0$.
\end{proof}

\section{Scaled polar coordinates}\label{sec:3}
Thanks to the uniqueness result proved in Lemma \ref{lem:uniqueness_Cauchy}, we can study system \eqref{eq:shooting} by passing to scaled polar coordinates around the point $(s_0,0)$. For $\alpha>0$ and $r\in [R_1,R_2]$, let
\begin{equation}\label{eq:polar}
\begin{cases}
u(r)-s_0=\rho(r)\cos\theta(r) \\
v(r)=-\alpha \rho(r)\sin\theta(r).
\end{cases}
\end{equation}
For $d\geq 0$ and $d\neq s_0$, if $(u_d,v_d)$ satisfies \eqref{eq:shooting}, the corresponding $(\theta_d,\rho_d)$ is such that, for $r\in (R_1,R_2)$,
\begin{equation}\label{eq:theta'}
\begin{aligned}
\theta_d'&=\frac{1}{\alpha\rho_d^2} \left[\varphi^{-1}\left(\frac{v_d}{r^{N-1}}\right)v_d + r^{N-1}\hat f(u_d)(u_d-s_0) \right] \\
&=\frac{\alpha \sin^2\theta_d}{r^{N-1}[1+(v_d/r^{N-1})^2]^{1/2}}
+r^{N-1} \hat f(u_d) \frac{u_d-s_0}{\alpha\rho_d^2}
\end{aligned}
\end{equation}
with initial conditions
\[
\theta_d(R_1)=\begin{cases}
\pi \quad \text{if } 0<d<s_0\\
0 \quad \text{if } d>s_0.
\end{cases}
\quad\text{and}\quad
\rho_d(R_1)=|d-s_0|.
\]

We remark that, by \eqref{eq:theta'}, $\theta_d(r)$ is strictly increasing for every $r\in [R_1,R_2]$, so that the solution $(u_d,v_d)$ is turning clockwise around $(s_0,0)$ in the phase plane $(u,v)$.

\begin{figure}[h]
\includegraphics{picture1.pdf}
\caption{A solution $(u_d,v_d)$, with $0<d<s_0$, in the phase plane $(u,v)$. The solution is also given in polar coordinates $(\theta_d,\rho_d)$ with $\alpha=1$. It can be noted from the picture that $u_d(\bar r)=s_0$ if and only if $\cos\theta_d(\bar r)=0$ and that $v_d(r)=0$ for some $r\in [R_1,R_2]$ if and only if $\sin\theta_d(r)=0$.}\label{fig:polar_coord}
\end{figure}

We would like to estimate the quantity $\theta_d(R_2) - \theta_d(R_1)$ for $d$ in a neighborhood of $s_0$. We remark that, despite the fact that the angle $\theta_d$ depends on the constant $\alpha$, the quantity
\[
\left\lfloor\frac{\theta_d(R_2) - \theta_d(R_1)}{\pi}\right\rfloor,
\]
that is the number of half turns of the solution around $(s_0,0)$, does not depend on $\alpha$. Here $\lfloor\cdot\rfloor$ denotes the floor function. Indeed, this quantity is the number of zeros of $v(r)$ for $r\in (R_1,R_2]$, which clearly does not depend on $\alpha$, cf. also Fig. \ref{fig:polar_coord}.

\begin{lemma}\label{lem:d_close1}
Suppose that, for some integer $k\geq1$,
\[
f'(s_0)>\lambda_{k+1}^{\textnormal{rad}}.
\]
There exists $\bar\delta>0$ such that $\theta_d(R_2) - \theta_d(R_1)>k\pi$ for $d\in [s_0-\bar\delta,s_0+\bar\delta]$ and $d \neq s_0$.
\end{lemma}
\begin{proof}
Suppose that $f'(s_0)>\lambda_{k+1}^{\mathrm{rad}}$.
Let $\bar\lambda$ be such that
\begin{equation}\label{eq:bar_lambda_def}
\lambda_{k+1}^{\mathrm{rad}}<\bar \lambda<f'(s_0),
\end{equation}
and consequently choose $\varepsilon>0$ such that
\begin{equation*}
\bar\lambda \sqrt{1+\varepsilon^2} <f'(s_0)-\varepsilon.
\end{equation*}
Then, using assumptions $(f_\textrm{reg})$ and $(f_\textrm{eq})$, there exists $\delta>0$ such that, for every $s$ satisfying $|s-s_0|\leq \delta$, it holds
\begin{equation}\label{eq:ineq1}
\hat f(s)(s-s_0)\geq (f'(s_0)-\varepsilon)(s-s_0)^2 \geq
\bar\lambda \sqrt{1+\varepsilon^2} (s-s_0)^2.
\end{equation}
Thanks to \eqref{eq:dip_cont} and \eqref{eq:dip_cont_vr}, there exists $\bar\delta>0$ such that, for every $d$ satisfying $0<|d-s_0|\leq\bar\delta$, it holds
\begin{equation}\label{eq:ineq2}
|u_d(r)-s_0|\leq \delta \qquad\text{and}\qquad
\frac{|v_d(r)|}{r^{N-1}}\leq\varepsilon,
\end{equation}
for every $r\in [R_1,R_2]$, being $u_{s_0}\equiv s_0$ in $[R_1,R_2]$. Now we choose in \eqref{eq:polar} and consequently in \eqref{eq:theta'}
\[
\alpha=\sqrt{1+\varepsilon^2}.
\]
By replacing \eqref{eq:ineq1} and \eqref{eq:ineq2} into \eqref{eq:theta'}, and using \eqref{eq:polar}, we obtain that, for every $d$ satisfying $0<|d-s_0|\leq \bar\delta$ and $r\in [R_1,R_2]$,
\begin{equation}
\theta_d'(r)\geq \frac{\sin^2\theta_d(r)}{r^{N-1}}+\bar\lambda r^{N-1} \cos^2\theta_d(r).
\end{equation}
Recalling equation \eqref{eq:theta_mu} with $\mu=\bar\lambda$, using the Comparison Theorem for ODEs and \eqref{eq:initial_linear}, we obtain, for all $d$ satisfying $0<|d-s_0|\leq\bar\delta$,
$$
\theta_d(r) - \theta_d(R_1)\geq \vartheta_{\bar\lambda}(r)\quad\mbox{for all }r\in[R_1,R_2].
$$
In particular, by relation \eqref{eq:bar_lambda_def} and Theorems \ref{th:RW} and \ref{th:eigen}, we have
\[
\theta_d(R_2) - \theta_d(R_1)>  \vartheta_{\lambda_{k+1}^{\mathrm{rad}}}(R_2) = k\pi.  \qedhere
\]
\end{proof}

\section{Proof of the main result}\label{sec:4}

\begin{proof}[Proof of Theorem \ref{thm:main}]
Suppose first $d\in [0,s_0)$ and let $(u_d,v_d)$ be the solution of \eqref{eq:shooting}. We consider the associated angular variable $\theta_d$ given by \eqref{eq:polar} with $\alpha=1$. Notice that $\theta_d(R_1)=\pi$. By assumption $(f_{s_0})$ and Lemma \ref{lem:d_close1}, we have
\begin{equation}\label{eq:at_s_0}
\theta_d(R_2) >( k+1)\pi \quad \text{for }d\in [s_0-\bar\delta,s_0).
\end{equation}
Furthermore
\begin{equation}\label{eq:at_0}
\theta_0(r)\equiv\pi \quad \text{for every } r\in [R_1,R_2].
\end{equation}
By \eqref{eq:dip_cont}, the map $d\mapsto \theta_d(R_2)$ is continuous on $[0,s_0)$. Thus \eqref{eq:at_s_0} and \eqref{eq:at_0} imply that, for all $j=1,\ldots,k$, there exists $d_j \in (0,s_0)$ such that
\begin{equation}\label{eq:d_j}
\theta_{d_j}(R_2)=(j+1)\pi.
\end{equation}
By \eqref{eq:polar}, this corresponds to $u'_{d_j}(R_2)=0$, so that $u_j:=u_{d_j}$ for $j=1,\ldots,k$ are the solutions mentioned in point (i).
In order to study the oscillatory behavior of $u_j$ for $j=1,\ldots,k$, we notice that, by \eqref{eq:theta'} and \eqref{eq:d_j}, $\theta_{d_j}(\cdot)$ is strictly increasing from $\pi$ to $(j+1)\pi$. Hence there exist exactly $j$ radii $r_1,\ldots,r_{j}\in (R_1,R_2)$ such that $\theta_{d_j}(r_1)=\frac{3}{2}\pi_p$, $\theta_{d_j}(r_2)=\frac{5}{2}\pi_p,\ldots,\theta_{d_j}(r_{j})=\left(j+\frac{1}{2}\right)\pi_p$. Again by \eqref{eq:polar}, we have $u_j(r)=s_0$ if and only if $r\in \{r_1,\ldots,r_j\}$.

If $d>s_0$, then $\theta_d(R_1)=0$. Again by assumption $(f_{s_0})$ and Lemma \ref{lem:d_close1}, we have
\[
\theta_d(R_2) >k\pi \quad \text{for }d\in (s_0,s_0+\bar\delta].
\]
On the other hand, we claim that, letting $d^\ast :=s_0+R_2-R_1$, it holds
\[
\theta_{d^\ast}(R_2)<\pi.
\]
Indeed by \eqref{eq:inverse-phi} we have, for every $r\in [R_1,R_2]$,
\begin{multline*}
\rho_{d^\ast}(r)\cos\theta_{d^\ast}(r)=u_{d^\ast}(r)-s_0
\geq -\int_{R_1}^r |u'_{d^\ast}(s)| \,ds +d^\ast-s_0 \\
> -(R_2-R_1)+d^\ast-s_0=0,
\end{multline*}
implying that $\theta_{d^\ast}(r)<\pi/2$ for every $r\in [R_1,R_2]$.

As in the previous case, we infer the existence of $k$ values $d_{j+k}$ for $j=1,\ldots,k$ such that $\theta_{d_{j+k}}(R_2)=j\pi$. We thus obtain the solutions $u_{j+k}:=u_{d_{j+k}}$ for every $j=1,\ldots,k$ whose existence is stated in (ii). Similarly as before, there exist $r_1,\ldots,r_{j}\in (R_1,R_2)$ such that $\theta_{d_{j+k}}(r_1)=\frac{1}{2}\pi$, $\theta_{d_{j+k}}(r_2)=\frac{3}{2}\pi,\ldots,\theta_{d_{j+k}}(r_{j})=\left(j-\frac{1}{2}\right)\pi$, proving the oscillatory behavior stated at (iii).
\end{proof}

\appendix

\section{Radial eigenvalue problem for the Neumann Laplacian}\label{sec:5}

In this appendix we recall some known results concerning the radial eigenvalue problem for the Laplacian with homogeneous Neumann boundary conditions \eqref{eq:eigenv_radial}.
Even though this equation contains the possibly singular weight $r^{1-N}$, it is well known that the eigenfunctions satisfy the classical Sturm theory. We refer for example to \cite{RW99}, where indeed a more general problem is treated.

\begin{theorem}{\cite[Theorem 1]{RW99}}\label{th:eigen}
The eigenvalue problem \eqref{eq:eigenv_radial} has a countable number of simple eigenvalues $0=\lambda_1^{\mathrm{rad}}<\lambda_2^{\mathrm{rad}}<\lambda_3^{\mathrm{rad}}<\dots$, $\lim_{k\to+\infty}\lambda_k^{\mathrm{rad}}=+\infty$, and no other eigenvalues. The eigenfunction that corresponds to the $k$-th eigenvalue $\lambda_k^{\mathrm{rad}}$ has $k-1$ simple zeros in $(R_1,R_2)$.
\end{theorem}

Via the change of variables
\[
\begin{cases}
u(r)=\varrho_\lambda(r)\cos\vartheta_\lambda(r) \\
r^{N-1}u'(r)=-\varrho_\lambda(r)\sin\vartheta_\lambda(r),
\end{cases}
\]
if $u$ is an eigenfunction associated to $\lambda$ as in \eqref{eq:eigenv_radial}, the corresponding $(\vartheta_\lambda,\varrho_\lambda)$ is such that
\begin{equation}\label{eq:theta'-omogenea-associata}
\vartheta_\lambda'=\frac{\sin^2\vartheta_\lambda}{r^{N-1}}+\lambda r^{N-1}\cos^2\vartheta_\lambda, \qquad r\in [R_1,R_2].
\end{equation}
By convention, we choose an eigenfunction $u$ satisfying $u(R_1)>0$, so that we can assume
\begin{equation}\label{eq:initial_linear}
\vartheta_\lambda(R_1)=0.
\end{equation}

Notice that, by \eqref{eq:theta'-omogenea-associata}, the function $r \mapsto \vartheta_\lambda(r)$ is strictly increasing. As a consequence, if $\lambda=\lambda^{\mathrm{rad}}_{k+1}$ for $k\ge0$, the fact that the eigenfunction which corresponds to the $(k+1)$-th eigenvalue has $k$ simple zeros in $(R_1,R_2)$ reads as
\begin{equation}\label{initialcondition-ep}
\vartheta_{\lambda^{\mathrm{rad}}_{k+1}}(R_2) =k\pi.
\end{equation}

We will also need to consider the Cauchy problem associated to the equation \eqref{eq:theta'-omogenea-associata} when $\lambda$ is not an eigenvalue. Also in this case it is known that, despite the fact that the equation may be singular, there exists a unique solution satisfying the initial condition $\vartheta_\mu(R_1)=0$.
\begin{theorem}{\cite[Theorem 4]{RW99}}\label{th:RW}
For every $\mu>0$, let $\vartheta_\mu$ solve
\begin{equation}\label{eq:theta_mu}
\vartheta_\mu'=\frac{\sin^2\vartheta_\mu}{r^{N-1}}+\mu r^{N-1}\cos^2\vartheta_\mu, \qquad r\in [R_1,R_2],
\end{equation}
with initial condition $\vartheta_\mu(R_1)=0$.
The function $\vartheta_\mu(R_2)$ is strictly increasing in $\mu$.
\end{theorem}

\section*{Acknowledgments}
\noindent A. Boscaggin and B. Noris acknowledge the support of the project ERC Advanced Grant 2013 n. 339958: ``Complex Patterns for Strongly Interacting Dynamical Systems --COMPAT''.

config: arxiv


TITLE: Computing $\lim_{n \to \infty} \sup_{x \in (0,1)}\left| \frac{1}{nx} \right|$
QUESTION [0 upvotes]: I believe that the above is equal to $\infty$ but I don't have any formal reason why.

REPLY [0 votes]: Note that for all $n\in\mathbb{N}^*,$ $\sup\limits_{x\in(0,1)}\frac{1}{nx}=+\infty$ (for all $A>1,$ if you take $x=\frac{1}{A\cdot n}\in(0,1)$ you get $\frac{1}{nx}=\frac{A\cdot n}{n}=A$). Then,
$$\lim\limits_{n\to+\infty}\sup\limits_{x\in(0,1)}\frac{1}{nx}=\lim\limits_{n\to+\infty}+\infty=+\infty.$$


TITLE: $X\sim N(0,1)$, find the generating function of $Y=X^2$
QUESTION [0 upvotes]: If $X\sim N(0,1)$, I need find the generating function of $Y=X^2$. The exercise says me that I should not solve the integral (which is I presume $\int e^{tx^2}f(x)dx$). It also says:
$$E(e^{tY}) = E(e^{tX^2})$$
and that any probability distribution function $f(x)$ has $\int_{-\infty}^{\infty}f(x)\ dx = 1$
How should I solve it? I know I must find $M_{X^2}(t) = E(e^{tX^2})$. I can't, however, solve the integral. Which methods are left? I don't know any.

REPLY [2 votes]: $Y=X^2$
$$E(e^{tY})=E(e^{tX^2})=\int_{-\infty}^{\infty}e^{tx^2}\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}dx\\=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}e^{-\dfrac{x^2(1-2t)}{2}}dx$$
I think you can do next steps.
Note that $$\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}}e^{-\dfrac{x^2}{2\sigma^2}}dx=\sigma$$
So you have to find $\sigma$ here, that's all.
Btw $Y$ follows Chi-Square distribution with 1 degree of freedom