\section{Introduction}

In this paper, we study the multiplicity of the Laplacian eigenvalues of trees. In particular, we are interested in upper bounds for these multiplicities, and trees with multiplicities that are close to these upper bounds.

Let $G$ be a graph with Laplacian eigenvalues $0=\mu_1\leq \cdots \leq \mu_n$. Fiedler \cite{fiedler} showed that $m_G(\mu_1)=1$ if and only if $G$ is connected, where $m_G(\mu)$ denotes the multiplicity of Laplacian eigenvalue $\mu$. Grone, Merris, and Sunder \cite[Prop.~2.2]{kamel} proved that $m_G(\mu_n)=1$ if $G$ is a connected bipartite graph (in particular, if it is a tree). On the other hand, for the complete graph $K_n$, the multiplicity of $\mu_n$ is large and indeed is $n-1$. How large can the multiplicities be when we restrict to trees? It is shown by Grone et al.~\cite[Thm.~2.1]{kamel} that if an integer $\mu \geq 2$ is a Laplacian eigenvalue of a tree $T$ of order $n$, then $m_T(\mu)=1$ and $\mu \mid n$. Interestingly, it is different for the Laplacian eigenvalue $1$, because $m_G(1)\geq p(G)-q(G)$ for all graphs $G$, where $p(G)$ and $q(G)$ are the number of pendant vertices and quasipendant vertices, respectively, see \cite[p.~263]{far}. For example, it follows that if $G$ is a star ($p(G)=n-1,q(G)=1$), then $m_G(1)=n-2$. Guo, Feng, and Zhang \cite{feng} showed that if $T$ is a tree of order $n$, then $m_T(1) \in S=\{0,\, 1,\, \ldots,\,n-5, n-4,\, n-2\}$ and for every integer $n$ and every $k\in S$ there exists a tree $T$ of order $n$ with $m_T(1)=k$. Also Barik, Lal, and Pati \cite{barik} studied the multiplicity of Laplacian eigenvalue $1$ in trees. In this paper we consider the multiplicities of the other (non-integral) Laplacian eigenvalues.

Our paper is further organized as follows. In Section \ref{secNotation}, we introduce some notation and  definitions. We then collect some relevant results from the literature in Section \ref{secSurvey}. In Section \ref{secExamples}, we introduce the family of trees that we will call spiders, as they will play a key role in the main part of the paper, Section \ref{secMAIN}. In this main part we will give an upper bound $\frac{n-3}{2}$ on the multiplicities of a Laplacian eigenvalue of a tree of order $n$, in particular for the algebraic connectivity, and characterize the trees that are close to this upper bound.
One main result (Theorem \ref{km2}) --- and starting point of several refinements --- is that for a tree $T$ of order $n\geq 6$, the multiplicity of a Laplacian eigenvalue $\mu \neq 1$ is at most $\frac{n-3}{2}$, and we characterize the trees that attain this bound. We will also characterize the trees that have a multiplicity that is close to the upper bound (in Theorems \ref{n/2-2} and \ref{n-1/2-2}), and show that there are finitely many trees besides a specific family of spiders for which the algebraic connectivity has a multiplicity within a fixed range from the upper bound (in Theorem \ref{thm:n/2-k}).

\section{Preliminaries}
\subsection{Notation}\label{secNotation}

Let $G = (V(G),E(G))$ be a graph, where $V (G) = \{v_1, \ldots , v_n\}$ is the vertex set and $E(G)$ is the edge set. Throughout this paper all graphs are simple, that is, without loops and multiple edges. Let $d_G(v_i)$ be the degree of $v_i$. We denote the non-increasing vertex degree sequence of $G$ by $(d_1, \ldots , d_n)$. The maximum and minimum degree of $G$ are denoted by $\Delta(G)=d_1$ and $\delta(G)=d_n$, respectively.

The {\em adjacency matrix} of $G$, denoted by $A(G)$, is an $n\times n$ matrix whose $(i, j)$-entry is $1$ if $v_i$ and $v_j$ are adjacent and $0$ otherwise. We call $L(G) = D(G) - A(G)$ the {\it Laplacian matrix} of $G$, where $D(G)$ is the $n \times n$ diagonal matrix with $d_{ii}=d(v_i)$. The eigenvalues of $L(G)$ are called the {\it (Laplacian) eigenvalues}\footnote{Whenever we write about eigenvalues of a graph, we mean Laplacian eigenvalues (unless explicitly stated otherwise).} of $G$, and we denote these in increasing order by $0=\mu_1(G) \leq \cdots \leq \mu_n(G)$. The multiset of eigenvalues of $L(G)$ is called the (Laplacian) spectrum of $G$. Fiedler \cite{fiedler} called $\mu_2$ the {\it algebraic connectivity} of $G$. The multiplicity of a Laplacian eigenvalue $\mu$ in a graph $G$ is denoted by $m_G(\mu)$; the number of Laplacian eigenvalues of $G$ in an interval $I$ is denoted by $m_GI$. We say that two (or more) Laplacian eigenvalues are conjugates (of each other) if they are roots of the same irreducible factor of the characteristic polynomial of the Laplacian (over the rationals). Conjugate eigenvalues have the same multiplicity.

A {\em star} (graph) is a complete bipartite graph $K_{1,n}$, for some positive integer $n$. We let $P_n$ be the path of order $n$. The {\em diameter} of $G$ is  denoted by $\diam(G)$. A vertex of degree one is called a {\em pendant vertex} and a vertex that is adjacent to at least one pendant vertex is called a {\em quasipendant vertex}. The number of pendant and quasipendant vertices of a graph $G$ are denoted by $p(G)$ and $q(G)$, respectively.

In all of the above notation, we remove the additional $G$ or $T$ if there is no ambiguity; for example $m(\mu)$ instead of $m_T(\mu)$, or $V$ instead of $V(G)$.

\subsection{A collection of elementary results}\label{secSurvey}

In this section we collect and extend some relevant basic lemmas from the literature.
We start with some general ones. For other basic results, we refer to the books by Brouwer and Haemers \cite{BH}, Cvetkovi\'{c}, Doob, and Sachs \cite{CDS}, and Cvetkovi\'{c}, Rowlinson, and Simi\'{c} \cite{cvet}.

\begin{lem}\label{cve}
{\em \cite[Prop.~7.5.6]{cvet}.} If $G$ is a connected graph with $r$ distinct Laplacian eigenvalues, then $\diam(G)\leq r-1$.
\end{lem}

 \begin{lem}\label{haem}
{\em \cite[Thm.~1]{haemer}}. Let $G$ be a graph of order $n$, with vertex degrees $d_1\geq \cdots \geq d_n$ and Laplacian eigenvalues $\mu_1 \leq \cdots \leq \mu_n$. If $G$ is not $K_m \cup (n-m)K_1$, then $\mu_{n-m+1}\geq d_m - m+2$ for $1\leq m \leq n$. In particular, if $G$ has at least one edge, then $\mu_n\geq d_1+1$ and if $G$ has at least two edges, then $\mu_{n-1} \geq d_2$.
\end{lem}

We recall that a sequence $\mu_1 \geq \cdots \geq \mu_m$ interlaces another sequence $\lambda_1 \geq \cdots \geq \lambda_n$ with $m < n$ whenever $\lambda_i \geq \mu_i \geq \lambda_{n-m+i}$, for $i = 1, \ldots , m$. It is well known \cite[Thm.~1]{hwa} that the eigenvalues of a principal submatrix of a Hermitian matrix $M$ interlace the eigenvalues of $M$. For the Laplacian eigenvalues, we moreover have the following two specific results.

\begin{lem}\label{kame3}
{\em \cite[Thm.~4.1]{kamel}.} Let $\tilde{G}$ be a graph of order $n$ and let $G$ be a (spanning) subgraph of $\tilde{G}$ obtained by removing just one of its edges. Then the $n-1$ largest Laplacian eigenvalues of $G$ interlace the Laplacian eigenvalues of $\tilde{G}$.
\end{lem}

A consequence of this is the following.

\begin{lem}\label{kame22}
{\em \cite[Cor.~4.2]{kamel}.} Let $v$ be a pendant vertex of $\tilde{G}$ and let $G=\tilde{G}\setminus v$. Then the Laplacian eigenvalues of $G$ interlace the Laplacian eigenvalues of $\tilde{G}$.
\end{lem}

The following results concern multiplicities.

\begin{lem}\label{kame}
\cite[p.~263]{far}. Let $G$ be a graph with $p$ pendant vertices and $q$ quasipendant vertices. Then $m_G(1)\geq p-q$.
\end{lem}
This result follows from the observation that for every pair $(v_i,v_j)$ of pendant vertices that is adjacent to the same quasipendant vertex, the difference $e_i-e_j$ of the corresponding characteristic vectors is an  eigenvector of $L(G)$ for eigenvalue $1$. This gives $p-q$ linearly independent eigenvectors

Finally, we have some specific results for trees.

\begin{lem}\label{Tm2p}
{\em \cite[Thm.~2.3]{kamel}.} Let $T$ be a tree with $p$ pendant vertices. If $\mu$ is a Laplacian eigenvalue of $T$, then $m_T(\mu) \leq p-1$.
\end{lem}

The following is a clear generalization to non-integral eigenvalues of a result by Grone, Merris, and Sunder \cite[Thm.~2.15]{kamel}. It uses the Matrix-Tree theorem, which states that any cofactor of the Laplacian matrix of $G$ equals the number of spanning trees of $G$. In case of trees, this is equivalent to the fact that the product of all non-zero Laplacian eigenvalues equals the number of vertices; we shall use this also later.

\begin{lem}\label{van}
Let $\mu$ be a Laplacian eigenvalue of a tree $T$ with $m_T(\mu)>1$. Then the product of $\mu$ and its conjugate eigenvalues equals $1$. In particular, if $\mu$ is an integer, then $\mu=1$.
\end{lem}

\begin{proof}
Let $v$ be a pendant vertex. Then the Laplacian matrix of $T$ has the form
$$L(T)=\begin{bmatrix}
B& *\\
*& 1
\end{bmatrix},$$
where $B$ is the principal submatrix corresponding to $T\setminus v$. Since $m_T(\mu)>1$, there is an eigenvector $x$ of $L(T)$ for $\mu$ such that its last component is $0$.  If $x'$ is the vector obtained from $x$ by deleting the last component, then it is not hard to see that $Bx'=\mu x'$. So $\mu$ is an eigenvalue of $B$ as well (and so are its conjugates). By the Matrix-Tree Theorem however, we have that $\det(B)=1$, and the result follows.
\end{proof}

To conclude this section, we mention a bound for the multiplicity of the algebraic connectivity of a tree. It follows easily from a result of Grone and Merris \cite{merris}.
\begin{prop}\label{delta}
Let $T$ be a tree with   $\Delta \geq 2$. Then $m_T(\mu_2)\leq \Delta -1$.
\end{prop}

\begin{proof}
Let $m=m_T(\mu_2)$, and suppose that $m\geq \Delta$. Because the multiplicity is at least $2$, there is an eigenvector that has value $0$ corresponding to  one of the vertices, and so $T$ is a so-called type I tree (see \cite{merris}). By \cite[Thm.~2]{merris}, the so-called characteristic vertex of $T$ has degree at least $m+1$, but this is at least $\Delta+1$, which is a contradiction.
\end{proof}

\section{Spiders and their spectra}\label{secExamples}

In this section we define two families of trees that are most relevant to our results. We start with the main one, i.e., the family of trees that have large multiplicities for some non-integral Laplacian eigenvalues.

The spider $T(s,k)$, with $1\leq k \leq s$, is defined as in Figure \ref{12star}. It is obtained from the star $K_{1,s}$ by extending $k$ of its rays (legs) by an extra edge, and has $n=s+k+1$ vertices. We say that the spider has $k$ legs.

\begin{figure}[h]
\centering
\includegraphics[width=60mm]{12star22.pdf}
\caption{The spider $T(s,k)$}\label{12star}
\end{figure}

\begin{prop}\label{spectrum1}
The Laplacian spectrum of $T(k,k)$ is
$$\{0^{[1]},\, \theta^{[k-1]},\, \lambda_1^{[1]},\, \overline{\theta}^{[k-1]},\, \lambda_2^{[1]}\},$$
where $(\theta, \overline{\theta})=(\frac{3-\sqrt{5}}{2},\frac{3+\sqrt{5}}{2})$ and $\lambda_1$, $\lambda_2$ are the roots of  $x^2-(k+3)x+2k+1$.
\end{prop}

\begin{proof}
In Figure \ref{12star}, an eigenvector for eigenvalue $\theta=\frac{3-\sqrt{5}}{2}$ is shown\footnote{Whenever we use $\theta$ and $\overline{\theta}$ in this paper, we mean the specific values $\frac{3-\sqrt{5}}{2}$ and $\frac{3+\sqrt{5}}{2}$.}. It is clear that there are $k-1$ linearly independent such eigenvectors corresponding to the eigenvalue $\theta$. Similarly, we find $k-1$ linearly independent eigenvectors corresponding to eigenvalue $\overline{\theta}=\frac{3+\sqrt{5}}{2}$.
Because $\mu_1=0$, there are only two other eigenvalues $\lambda_1 \leq \lambda_2$. Because the product of all non-zero eigenvalues equals $n=2k+1$, it follows that $\lambda_1 \lambda_2 =2k+1$. Noting the trace of $L$ (which equals twice the number of edges) it follows that $\lambda_1 + \lambda_2 =k+3$, and the result follows.
\end{proof}

Note that if we let $\lambda_2 >\lambda_1$, then $\lambda_1>1$ and $\lambda_2>\overline{\theta}$, so for $k \geq 2$ the algebraic connectivity $\mu_2$ equals $\frac{3-\sqrt{5}}{2}$ and $\mu_{n-1}=\frac{3+\sqrt{5}}{2}$. Proposition \ref{spectrum1} thus shows that the upper bound of Proposition \ref{delta} is sharp.

\begin{prop}\label{spectrum2}
The Laplacian spectrum of $T(s,k)$ with $k<s$ is
$$\{ 0^{[1]},\, \theta^{[k-1]},\, \lambda_1^{[1]},\, 1^{[s-k-1]},\, \lambda_2^{[1]},\, \overline{\theta}^{[k-1]},\, \lambda_3^{[1]}\},$$
where $(\theta, \overline{\theta})=(\frac{3-\sqrt{5}}{2},\frac{3+\sqrt{5}}{2})$ and $\lambda_1$, $\lambda_2$, $\lambda_3$ are the roots of $x^3-(s+4)x^2+(3s+4)x-(s+k+1)$.
\end{prop}

\begin{proof} As before, we have eigenvalues $\theta$ and $\overline{\theta}$ with multiplicities at least $k-1$, and eigenvalue $0$. In addition, we have eigenvalue $1$ with multiplicity at least $s-k-1$ by Lemma \ref{kame}. Thus, three eigenvalues $\lambda_1, \lambda_2,\lambda_3$ are left. Again, from the product of all non-zero eigenvalues being equal to $n$, it follows that   $\lambda_1 \lambda_2 \lambda_3 = n= s+k+1$. Moreover, $\lambda_1+\lambda_2 +\lambda_3= 2n-2-(s-k-1)-3(k-1)=s+4$. A quadratic equation easily follows from the trace of $L^2$:
$$ \sum_{i=1}^n \mu_i^2= \sum_{i=1}^n d_i^2 + 2m$$
for every graph $G$ of order $n$ with $m$ edges, and degrees $d_i$. For $T(s,k)$, we obtain that
$\lambda_1^2+\lambda_2^2 +\lambda_3^2= s^2+2s+8$, and from this we conclude that $\lambda_1 \lambda_2 + \lambda_1 \lambda_3 +\lambda_2 \lambda_3 = \frac{1}{2}(s+4)^2-\frac{1}{2}(s^2+2s+8) = 3s+4$. From all of this, the spectrum follows.
\end{proof}

Note that for a fixed integer $s$, one can use induction to show that $\nobreak \mu_2(T(s,s-i))\geq \theta$ and $\mu_{n-1}(T(s,s-i))\leq \overline{\theta}$, for $i=0, \ldots , s-1$, starting from Proposition \ref{spectrum1} and by inductively applying Lemma \ref{kame22}. On the other hand, for fixed $k\geq 2$, it also follows by induction that $\mu_{n-1}(T(k+i,k))\geq \overline{\theta}$ for all $i$. Consequently, we have the following.

\begin{lem}\label{lemmatsk35} Let $T=T(s,k)$, with $s \geq k \geq 2$. Then $\mu_2(T)= \theta=\frac{3-\sqrt{5}}{2}$ and $\mu_{n-1}(T)= \overline{\theta}=\frac{3+\sqrt{5}}{2}$.
\end{lem}

It also follows from the above that $\mu_2(T(s,1))>\theta$ for $s\geq 1$.
Below we will show that the spider graphs $T=T(s,k)$, with $s \geq k \geq 2$ are extremal regarding the eigenvalues $\theta$ and $\overline{\theta}$.

Observe first however that if $k=s-1$ then $m_T(1)=0$ and $\lambda_2=2$. So in this case, $\lambda_1$ and $\lambda_3$ are the roots of $x^2-(s+2)x+s$ and the spectrum of $T(s,s-1)$ is
$$\{0^{[1]},\, \theta^{[s-2]},\, \lambda_1^{[1]},\, 2^{[1]},\, \overline{\theta}^{[s-2]},\, \lambda_3^{[1]}\}.$$

\begin{figure}[h]
\centering
\includegraphics[width=60mm]{Hs,r,t.pdf}
\caption{$H(s,r,t)$}\label{Htree}
\end{figure}
A second family of trees that we will use is shown in Figure \ref{Htree}. Such a tree $H(s, r, t)$  is obtained by attaching $s$ pendant vertices to one end point of the path on $r$ vertices, and $t$ pendant vertices to its other end point, for some positive integers $s,r,t$. We note that for $r=1$, we obtain a star (a tree with diameter $2$). The Laplacian spectrum of this graph is $\{0^{[1]},\, 1^{[n-2]},\, n^{[1]}\}$. Also, every tree of order $n$ with diameter $3$ is a graph $H(s,2,t)$ for some integers $s, t$ such that $s+t=n-2$. The spectrum of this graph can easily be obtained in a similar way as in Proposition \ref{spectrum2}.

\begin{lem}\label{dou}
\cite[Prop.~1]{Grone}. Let $T=H(s,2,t)$ be of order $n=s+t+2$. Then the characteristic polynomial of $L(T)$ is
$x(x-1)^{n-4}[x^3-(n+2)x^2+(2n+st+1)x-n]$.
\end{lem}

In order to prove some of the results in the next section, we need the following two half-known characterizations of trees with extremal Laplacian eigenvalues $\frac{3 \pm \sqrt{5} }{2}$. The first is a result by Li, Guo, and Shiu \cite{li}. For completeness, we provide a shorter proof of this result.

\begin{figure}[h]
\centering
\includegraphics[width=30mm]{obt.pdf}
\caption{The fork $F$}\label{obt}
\end{figure}

\begin{prop}\label{kho}
{\em \cite[Thm.~3.4]{li}.}
Let $G$ be a connected graph of order $n$. Then $\mu_{n-1}(G)=\frac{3+\sqrt{5}}{2}$ if and only if $G\cong T(s,k)$ for some positive integers $s,k$ with $k\geq 2$.
\end{prop}

\begin{proof}
One side is clear by Lemma \ref{lemmatsk35}. To show the other side, suppose that $\mu_{n-1}(G)=\frac{3+\sqrt{5}}{2}=\overline{\theta}$. If $\Delta(G)=2$, then $G$ is a path or a cycle. Since $\mu_{5}(P_6)=3>\overline{\theta}$, it follows from interlacing (Lemmas \ref{kame3} and \ref{kame22}) that the order of $G$ is less than $6$, and then it can be checked that $G\cong P_5 = T(2,2)$. Next, assume that $u$ is a vertex of $G$ with degree $\Delta(G)\geq 3$. If there exists a vertex $v$ at distance $2$ from $u$ with degree at least $2$, then the graph $G$ can be obtained from the fork $F$ in Figure \ref{obt} by adding some pendant vertices and some edges. But $\mu_5(F) =3>\overline{\theta}$ and so again by interlacing, we have that $\mu_{n-1}(G)\geq \mu_5(F) > \overline{\theta}$, which is a contradiction. Thus, every vertex of degree at least $2$ is adjacent to $u$. By Lemma \ref{haem}, we have $d_2(G)\leq \mu_{n-1}$, hence $d_2(G) \leq 2$. So $G\cong T(s,k)$ for some integers $s,k$. By Proposition \ref{spectrum2}, it is necessary to have $k\geq 2$.
\end{proof}

We note that the proof actually shows that if $\mu_{n-1}(G) \leq \frac{3+\sqrt{5}}{2}$, then $G$ is a star or a spider. For more details and the full classification of graphs with $\mu_{n-1}(G) \leq 3$, we refer to Li, Guo, and Shiu \cite{li}. The following similar result is a strengthening of a result by Zhang \cite[Thm.~2.12]{zhang}.

\begin{prop}\label{kho2}
Let $T$ be a tree of order $n$. If $\mu_2(T) \geq \frac{3-\sqrt{5}}{2}$, then $T$ is a star, a spider, $H(2,2,2)$, or $H(3,2,2)$, and equality holds if and only if $T\cong T(s,k)$ for some positive integers $s,k$, with $k\geq 2$.
\end{prop}

\begin{proof}
Suppose that $\mu_2(T) \geq \frac{3-\sqrt{5}}{2}=\theta$. By interlacing (Lemma \ref{kame22}), the tree $T$ cannot have $P_6$ as a subgraph since $\mu_2(P_6)<\theta$, so $\diam(T)\leq 4$. If $T$ is not a star, then it must have diameter $3$ or $4$. If $\diam(T)=3$, then $T$ is $H(s,2,t)$ for some positive integers $s,t$. Using Lemma \ref{dou}, we find however that $\mu_2(H(3,2,3)) < \theta $ and $\mu_2(H(4,2,2)) < \theta$, so it follows again by interlacing that in this case $T$ can only be one of the trees $H(2,2,2)$, $H(3,2,2)$, and $T(s,1)$, for some positive integer $s$. Indeed, $\mu_2(H(2,2,2)) > \theta $, $\mu_2(H(3,2,2)) > \theta$, and $\mu_2(T(s,1))> \theta$.

Finally, suppose that $\diam(T)=4$. For the fork $F$ (see Figure \ref{obt}), we have $\mu_2(F)<\theta$. So $T$ cannot have $F$ as a subgraph, and thus $T$ is a spider. The case of equality now follows from Lemma \ref{lemmatsk35} and the fact that a star, $H(2,2,2)$, $H(3,2,2)$, and $T(s,1)$ all have $\mu_2>\theta$.
\end{proof}

\section{Trees with a large multiplicity}\label{secMAIN}

We are now ready for our main results, that is, to bound the multiplicities of non-integer Laplacian eigenvalues of trees, and to characterize the trees with large Laplacian eigenvalue multiplicities.

\begin{thm}\label{km2}
Let $T$ be a tree of order $n\geq 6$ with a Laplacian eigenvalue $\mu$. If $\mu\neq 1$, then $m_T(\mu)\leq \frac{n-3}{2}$, and equality holds if and only if $T\cong T(\frac{n-1}{2},\frac{n-1}{2})$ and $\mu =\frac{3 \pm \sqrt{5}}{2}$. In particular, if equality holds, then $\mu$ is the algebraic connectivity of $T$ or its conjugate.
\end{thm}

\begin{proof}
Suppose that $m_T(\mu) > \frac{n-3}{2}$ and $\mu \neq 1$. Then $m_T(\mu)>1$. So  by Lemma \ref{van}, the eigenvalue $\mu$ is not an integer, so it has at least one conjugate eigenvalue $\overline{\mu}$ with $m_T(\overline{\mu})=m_T(\mu)$. So $m_T(\mu)\leq \frac{n-1}{2}$. If $n$ is odd, then $m_T(\mu) =\frac{n-1}{2}$, so $T$ has exactly $3$ distinct eigenvalues. This implies that the diameter of $T$ is at most $2$ (by Lemma \ref{cve}), so $T$ is a star, with spectrum $\{ 0^{[1]},\, 1^{[n-2]},\, n^{[1]}\}$, which is a contradiction.

So $n$ is even and $m_T(\mu)=\frac{n-2}{2}$. Hence $T$ has spectrum
$$ \{ 0^{[1]},\, \mu^{[\frac{n-2}{2}]},\, \overline{\mu}^{[\frac{n-2}{2}]},\, \lambda^{[1]}\}$$
for some eigenvalue $\lambda$. Now, by Lemma \ref{cve}, $T$ has diameter at most $3$, and it is not a star. So $T$ has $p=n-2$ pendant vertices and $q=2$ quasipendant vertices. Thus, $m_T(1)\geq p-q=n-4 \geq 2$, by Lemma \ref{kame}, which is a contradiction, so $m_T(\mu) \leq \frac{n-3}{2}$.

Now, suppose that $m_T(\mu)= \frac{n-3}{2}$. Again, by Lemma \ref{van}, the eigenvalue $\mu$ is not an integer.
If $n=7$, then possibly $\mu$ can have two conjugate eigenvalues. However, this would imply  that $T$ has four distinct eigenvalues, which would give a contradiction in the same way as in the above case of $n$ even. So $n \geq 7$ and $\mu$ has exactly one conjugate eigenvalue $\overline{\mu}$. By Lemma \ref{van}, we have $\mu\overline{\mu}=1$. So the spectrum of $T$ is
$$\{0^{[1]},\, \mu^{[\frac{n-3}{2}]},\, \overline{\mu}^{[\frac{n-3}{2}]},\, \lambda_1^{[1]},\, \lambda_2^{[1]}\},$$
for some eigenvalues $\lambda_1$ and $\lambda_2$. Since the product of all non-zero eigenvalues of a tree equals $n$, we find that $\lambda_1\lambda_2=n$. Because the only tree on $n$ vertices with an eigenvalue $n$ is the star (which easily follows by observing that the complement of such a tree should be disconnected), it follows that $m_T(1)=0$, and hence by Lemma \ref{kame}, we deduce that $p=q$. Moreover, by Lemma \ref{cve} the diameter of $T$ is at most $4$. Because $n$ is odd, it now easily follows that $T$ is isomorphic to $T(\frac{n-1}{2},\frac{n-1}{2})$. As observed in Proposition \ref{spectrum1}, this graph indeed has an eigenvalue (in fact, the two conjugates $\frac{3\pm \sqrt{5}}2)$ with multiplicity $\frac{n-3}{2}$.
\end{proof}

Note that if $T$ is a tree but not a star, then $\diam(T) \geq 3$. Because $\mu_2(P_4)<1$, it then follows by interlacing that $\mu_2(T)<1$, so we have the following.

\begin{cor}\label{m2n2}
If $T$ is a tree of order $n$ but not a star, then $m_T(\mu_2)\leq \frac{n-3}{2}$.
\end{cor}

The multiplicity of $\mu_2$ in a star $K_{1,n}$ equals $n-1$ and by Corollary \ref{m2n2}, $m_T(\mu_2)\leq \lfloor \frac{n-1}{2} \rfloor -1$ for every other tree $T$. So there is a huge gap between these multiplicities $n-1$ and $ \lfloor \frac{n-1}{2} \rfloor -1$.
Lemma \ref{lemmatsk35} and Proposition \ref{spectrum2} show that there are no other gaps. In fact, for any $i=1,\dots, \lfloor \frac{n-1}{2} \rfloor -1$, the tree $T=T(n-i-2,i+1)$ has $m_T(\mu_2)=i$.

In Theorem \ref{thm:n/2-k}, we will show that for every positive integer $j$, all except finitely many trees $T$ with $m_T(\mu_2)=\lfloor \frac{n}{2} \rfloor -j$ are spiders. But first, we determine the typical values of the Laplacian eigenvalues with large multiplicity.

\begin{lem}\label{lem:n/2-k}
Let $j$ be an integer with $j \geq 2$. If $T$ is a tree of order $n> 10j$ and $m_T(\mu)= \lfloor \frac{n}{2} \rfloor -j$ for a Laplacian eigenvalue $\mu \neq 1$, then $\mu =\frac{3 \pm \sqrt{5}}{2}$.
\end{lem}

\begin{proof}
Suppose that $n\geq 10j+1$ and $m_T(\mu)=\lfloor \frac{n}{2} \rfloor -j$. Because $\mu$ cannot be integer, there exists another (conjugate) eigenvalue $\overline{\mu}$ with $m_T(\overline{\mu})=\lfloor \frac{n}{2}\rfloor -j$. Since $n\geq 10j+1$ there can be no other (conjugate) eigenvalue with such a large multiplicity. Thus, $\mu$ and $\overline{\mu}$ are the roots of a quadratic factor of the Laplacian polynomial, so $\mu + \overline{\mu}$ equals a positive integer $t$, say. Because $\mu\overline{\mu}=1$ by Lemma \ref{van}, it follows that $t \geq 3$. Since $\mu_1+\cdots +\mu_n =2n-2$, we have that
$(\lfloor \frac{n}{2} \rfloor -j)t < 2n-2.$

First suppose  that $t\geq 5$. If $n$ is even, then it follows that $n<\frac{2jt-4}{t-4} \leq 10j-4$, which is a contradiction. Similarly, if $n$ is odd, then $n<\frac{(2j+1)t-4}{t-4} \leq 10j+1$; again a contradiction.
Next, suppose that $t=4$. Note that by Proposition \ref{delta} and Lemma \ref{haem}, we have $\Delta \geq \lfloor \frac{n}{2} \rfloor -j +1$ and $\mu_n \geq \Delta +1$, and hence  $\mu_n \geq \lfloor \frac{n}{2}\rfloor -j+2$. Note also that $\mu_n$ is a simple eigenvalue by \cite[Prop.~2.2]{kamel}, so it is not equal to $\mu$ or $\overline{\mu}$. If $n$ is even, then
$$ \sum_{\mu_i \notin \{ \mu, \overline{\mu} \}} \mu_i = 4j-2 >  \frac{n}{2} -j+2$$
and so $n<10j-8$, which is a contradiction.
Similarly, if $n$ is odd, then
$$ \sum_{\mu_i \notin \{ \mu, \overline{\mu} \}} \mu_i = 4j > \frac{n-1}{2} -j+2$$
and so $n<10j-3$; again a contradiction.

Thus, $t= 3$ and hence $\mu ,\overline{\mu} = \frac{3 \pm \sqrt{5}}{2}$.
\end{proof}

\begin{thm}\label{thm:n/2-k}
Let $j$ be an integer with $j\geq 2$ and let $T$ be a tree of order $n> 10j$. Then $m_T(\mu_2)= \lfloor \frac{n}{2} \rfloor -j$ if and only if $T \cong T(\lceil \frac{n}{2} \rceil +j-2, \lfloor \frac{n}{2} \rfloor -j+1)$.
\end{thm}

\begin{proof}
If $m_T(\mu_2)= \lfloor \frac{n}{2} \rfloor -j$, then $T$ is not a star, so $\mu_2 \neq 1$, and hence by Lemma \ref{lem:n/2-k}, we have $\mu_2= \frac{3-\sqrt{5}}{2}$. Now, by Proposition \ref{kho2}, it is clear that $T\cong T(s,k)$ for some suitable $s$ and $k$. These integers are now determined by the multiplicity of $\mu_2$ (see Propositions \ref{spectrum1} and \ref{spectrum2}), which finishes the proof.
\end{proof}

Observe the contrast between Theorems \ref{km2} and \ref{thm:n/2-k} in the sense that in the latter we restrict to eigenvalue $\mu_2$. Indeed, the following examples show that this restriction is necessary, at least for $j \geq 3$.

\begin{figure}[h]
\centering
\includegraphics[width=70mm]{teta.pdf}
\caption{The tree $T^{*}(s,2)$}\label{teta}
\end{figure}

Let $s \geq k \geq 2$ and let $T^{*}=T^{*}(s,k)$ be the tree obtained from $T(s,k)$ by adding one pendant vertex to one of the $k$ legs. See Figure \ref{teta} for the case $k=2$. It is clear from Proposition \ref{kho2} that $\mu_2(T^{*})< \theta$, and it follows from interlacing (Lemma \ref{kame22}) that $m_{T^{*}}(\theta)$ equals $k-2$ or $k-1$. We claim that this multiplicity equals $k-2$. In order to show this, we first consider the case $k=2$ and show that $\theta$ is not an eigenvalue of $T^{*}(s,2)$ for any $s \geq 2$.

Indeed, suppose that $\theta$ is an eigenvalue of $T^{*}(s,2)$ with eigenvector $x$. By normalizing the entry $x_1=1$ of the top right vertex in Figure \ref{teta}, and applying the equation $Lx=\theta x$, we recursively find the entries of $x$ as given in the figure (we omit the technical details; note also that it easily follows that $x_1$ cannot be zero). But then finally for the bottom two right vertices (where we obtained $x_{n-1}=x_n=-1$) we should have the equation $x_n-x_{n-1}=\theta x_{n}$, which gives a contradiction.

Next, consider the general case $T^{*}(s,k)$, and suppose that it has eigenvalue $\theta$ with multiplicity $k-1$, for $k\geq 3$. By interlacing it then follows that $T^{*}(s,k-1)$ has eigenvalue $\theta$ with multiplicity at least $k-2$, and by repeating this, we find that $T^{*}(s,2)$ has eigenvalue $\theta$ with multiplicity at least $1$, which is a contradiction, and hence confirms our claim.

For even $n$, we can now take $s=\frac n2+j-4$ for $j \geq 3$, to obtain $m_{T^{*}}(\theta)=\frac n2-j$. For odd $n$, we take  $s=\frac {n-1}2+j-3$ for $j \geq 3$, to obtain $m_{T^{*}}(\theta)=\frac {n-1}2-j$. Thus, for every $j \geq 3$ there are infinitely many trees with such multiplicities.

In the given examples, we cannot take $j=2$. Indeed, for this case we can prove something stronger than in Theorem \ref{thm:n/2-k}, and obtain a result that is similar to Theorem \ref{km2}. Here we will show that there are unique trees of order $n$ with multiplicities $\frac{n}{2}-2$ and $\frac{n-1}{2}-2$ for an eigenvalue $\mu\neq 1$.

\begin{thm}\label{n/2-2}
Let $T$ be a tree of order $n\geq 8$ and $\mu \neq 1$ be a Laplacian eigenvalue of $T$. Then $m_T(\mu)= \frac{n}{2} -2$ if and only if $T\cong T(\frac{n}{2}, \frac{n}{2} -1)$ and $\mu=\frac{3\pm \sqrt{5}}{2}$.
In particular, in this case $\mu$ is the algebraic connectivity of $T$ or its conjugate.
\end{thm}

\begin{proof} One side of the equivalence is clear from Proposition \ref{spectrum2}. To show the other side, we will first show by induction on $n$ (with $n$ even) the claim that if $m_T(\mu)= \frac{n}{2} -2$, then $\mu=\frac{3\pm \sqrt{5}}{2}$ and that  $\mu_2(T)=\theta=\frac{3- \sqrt{5}}{2}$. We checked that this is true for $n=8$ by enumerating all trees of this order with the Sage computer package.
For $n>8$, consider a tree $T$ with $m_T(\mu)= \frac{n}{2} -2$. Consider one of its extremal quasipendant vertices $v$ (in the sense that $v$ becomes pendant in the tree that is obtained from $T$ by removing all its pendant vertices). Now, remove the edge that connects $v$ to its (unique) non-pendant neighbor. The remaining graph is a disjoint union of a star (with center $v$) and a tree $T'$ on $t$ vertices, say. By interlacing (Lemma \ref{kame3}), it follows that $m_{T'}(\mu) \geq \frac n2-3$. But $m_{T'}(\mu) \leq \frac {t-3}2$ by Theorem \ref{km2}, so it follows that $t \geq n-3$. Because $n-t \geq 2$, we have two cases. If $t=n-3$, then $m_{T'}(\mu) = \frac {t-3}2$, and it follows from Theorem \ref{km2} that indeed $\mu=\frac{3\pm \sqrt{5}}{2}$ and $\mu_2(T')=\theta$, which implies by interlacing that $\mu_2(T)=\theta$. If $t=n-2$, then $m_{T'}(\mu) = \frac {t}2-2$, so by induction $\mu=\frac{3\pm \sqrt{5}}{2}$ and $\mu_2(T')=\theta$, but the latter (and interlacing) again implies that $\mu_2(T)=\theta$, which finishes the proof of our claim.

Just like in the proof of Theorem \ref{thm:n/2-k}, we can now apply Proposition \ref{kho2} to finish the proof.
\end{proof}

We omit the proof of the following similar result, as the proof is very similar, although we also have to use Theorem \ref{n/2-2} now.

\begin{thm}\label{n-1/2-2}
Let $T$ be a tree of order $n\geq 9$ and $\mu \neq 1$ be a Laplacian eigenvalue of $T$. Then $m_T(\mu)= \frac{n-1}{2} -2$ if and only if $T\cong T(\frac{n-1}{2}+1, \frac{n-1}{2} -1)$ and $\mu=\frac{3\pm \sqrt{5}}{2}$.
In particular, in this case $\mu$ is the algebraic connectivity of $T$ or its conjugate.
\end{thm}

We note that one could try to extend this result further, and indeed, the induction steps work over and over again, so induction would give a theorem about multiplicity $\lfloor \frac{n}{2} \rfloor -j$ for each $j \geq 2$, if only the bases of the induction steps would be true. Of course, this is where things go wrong. For example, we cannot prove a similar result for multiplicity $\frac{n}{2} -3$ and $n \geq 10$ because we have counterexamples such as $T^{*}(4,4)$ on $10$ vertices. Indeed, there are five such counterexamples, and we depict them in Figure \ref{5examples2}. Besides $T^{*}(4,4)$ (Fig.~\ref{5examples2}a), there are (exactly) two other trees of order $10$ that have eigenvalue $\theta$ with multiplicity $2$ and $\mu_2(T)<\theta$ (Fig.~\ref{5examples2}b and c). Moreover, there is one tree of order $10$ with eigenvalues $2 \pm \sqrt{3}$ with multiplicity $2$ (Fig.~\ref{5examples2}d), and one tree of order $10$ that has the roots of $x^3-5x^2+6x-1$ as eigenvalues with multiplicity $2$ (Fig.~\ref{5examples2}e). The variety of these examples shows that further classification of trees with an eigenvalue other than $1$ with multiplicity $\lfloor \frac{n}{2} \rfloor -j$ for $j \geq 3$ (on top of Lemma \ref{lem:n/2-k} and Theorem \ref{thm:n/2-k}) seems unfeasible.

\begin{figure}[h]
\centering
\includegraphics[width=110mm]{5examples2.pdf}
\caption{Five counterexamples of order $10$}\label{5examples2}
\end{figure}

\noindent  {\bf Acknowledgement}. The research of the first author was partly funded by Iran National Science Foundation (INSF) under the contract No. 96004167. Also, part of the work in this paper was done while the third author was visiting Tilburg University.


\section{Introduction}
\vspace{-0.20cm}
Given a simple undirected graph $G=(V,E)$, $\delta_G(v_i,v_j)$ denotes the length of a shortest path between the
vertices $v_i$ and $v_j$ in $G$. For an integer $d >0$, the $d$-distance neighborhood of a vertex $v_i \in V$ is denoted by
$N_G^d[v_i]$ and is defined as  $N_G^d[v_i] = \{v_j\in V \mid \delta_G(v_i,v_j) \leq d\}$.
A \emph{$d$-distance $m$-tuple $(\ell,r)$-dominating set} (($d, m, \ell, r$) set for short) of $G$ is a subset $V'\subseteq V$ such that (i) for every $v_i \in V$, $|N^d_G[v_i]\cap V'| \geq m$, and (ii) $|(\cup_{u \in U} N^d_G[u]) \cap V'| \geq \ell$ for every $r$ size subset $U$ of $V$, where $d, m, r$, and $\ell$ are positive integers.
If $m \geq \ell$, then the second condition in the definition of ($d, m, \ell, r$) set is redundant. In the case of
$m = \ell (=k$, say), the ($d, m, \ell, r$) set is known as $k$-tuple dominating set in the literature. Note that, if $m = \ell$ then the value of $r>1$ is irrelevant. Therefore, we assume $r=1$ in case of $m=\ell$. From now onwards,
we assume that $m \leq \ell$. If $d=1, m = 2, \ell = 3, r=2$ then $(d, m, \ell, r$) set is known as a liar's dominating
set in the literature. The objective of the $d$-distance $m$-tuple $(\ell, r)$-domination problem is to find a minimum size  $d$-distance $m$-tuple $(\ell, r)$ dominating set in a given graph $G$, and we call this problem as the \emph{minimum ($d, m, \ell, r$) dominating set}  problem. In Figure \ref{fig:def}, the set of vertices $\{e,f,i\}$ form a 3-distance 2-tuple $(3, 4)$-dominating set for the graph.

\begin{figure}[!h]\vspace*{-0.25cm}
\centering
\includegraphics[scale=0.6]{Ddlds_fig.pdf}
\caption{The set $\{e,f,i\}$ is the 3-distance 2-tuple $(3, 4)$-dominating set.}
\label{fig:def}\vspace*{-0.25cm}
\end{figure}

Our interest in the problem arises from its important application such as fault tolerance in wireless/sensor networks. One specific real-time application is as follows for $r=2$.
Suppose that in a graph $G=(V,E)$ each vertex is a possible location for an intruder such as a thief, a saboteur, a fire or some possible fault. Assume also that there is exactly $\min (\ell-m, \ceil{\ell/2}-1)$ intruders in the system represented by $G$. A protection device placed at a vertex $v$ is assumed to be able to (i) detect the intruder at any vertex in its $d$-distance neighborhood $N^d_G[v]$, and (ii) report the vertex $u \in N^d_G[v]$ at which the intruder is located.
We are interested in deploying protection devices at a minimum number of
vertices so that the intruder can be detected and identified correctly.
This can be solved by finding a minimum cardinality $m$-tuple dominating set, say $D$, of $G$ and deploying protection devices at all the vertices of $D$.
If any one protection device can fail to detect the intruder, then to correctly detect and identify the intruder one needs to place the protection devices at all the vertices of a minimum cardinality $2m$-tuple dominating set of $G$. Now it may so happen that all the protection devices detect the intruder location correctly but while reporting some of these protection devices can misreport or lie (either deliberately or through a transmission error) about the intruder location.
Assume that at most $\min (\ell-m, \ceil{\ell/2}-1)$ protection devices in the $d$-distance neighborhood of an intruder location can lie.
Under these circumstances, to protect the network we have to install the protection devices at all the vertices of a minimum  $d$-distance $m$-tuple $(\ell, r)$ dominating set.

\vspace{-0.30cm}
\section{Related work}
\vspace{-0.20cm}
The domination problem is one of the most studied problem in the literature for its wide range of applications. Finding a minimum dominating set (MDS) in general graphs is  known to be NP-hard \cite{garey2002}. Raz and Safra \cite{raz1997sub} proved that there does not exist any approximation algorithm better than $O(\log n)$-factor unless P=NP.  The concepts of dominations and its variations are widely studied and can be seen in \cite{haynes208,haynes209}.

One of  the  variations  of  domination is the $k$-tuple domination problem and was introduced by Harary and Haynes \cite{harary}. When $k=1$, it is the usual domination problem.  For $k=2$, it is called double domination \cite{harary}.
The same paper discusses exact values of  the  double domination numbers for  some  special graphs and various bounds  of  the  double  and  the $k$-tuple  domination numbers  in  terms  of  other  parameters.
The hardness results and bounds for the $k$-tuple domination number for various sub-classes of graphs can be found in \cite{liao2003k,rautenbach2007new}.

In 2009, Slater \cite{slater} first introduced 1-distance 2-tuple (3,2) domination problem known as the liar's dominating set (LDS) problem in the literature. The author proved that the problem is NP-hard for general graphs and proposed various bounds for trees, a subclass of trees, and graphs. The problem is also studied for different sub-classes of graphs and proved to be NP-hard  for  bipartite graphs  \cite{roden}, split graphs and chordal graphs \cite{panda2013liar}, doubly chordal graphs \cite{panda2015hardness},  whereas polynomially solvable in trees  \cite{panda2013liar}, block graphs \cite{panda2015hardness}, proper interval graphs \cite{paul2013}.
Panda et al. \cite{panda2015hardness} studied the approximability of the problem and gave an $O(\ln \Delta)$-factor approximation algorithm, where $\Delta$ is the degree of the given graph.
Alimadadi et al. \cite{alimadadi} provided the characterization of graphs and trees for which the LDS cardinality is $|V|$ and $|V|-1$, respectively.
\vspace{-0.40cm}

\subsection{Our contribution} \label{contribution}
We prove that the problem of deciding whether a graph $G$ has a 1-distance $m$-tuple ($\ell, r$)-dominating set for each fixed value of $m, \ell$, and $r$ of cardinality at most $k$ is NP-complete (see Subsection \ref{hardness1}).
Next, we prove that the problem of deciding whether a graph $G$ has a $d$-distance $m$-tuple  ($\ell, 2$)-dominating set for each fixed value of $d (> 1), m$, and $\ell$ of cardinality at most $k$ is NP-complete (see Subsection \ref{hardness2}).
We also prove that for any $\varepsilon>0$, the 1-distance $m$-tuple $(\ell, r)$-domination problem and the $d$-distance $m$-tuple $(\ell,2)$-domination problem cannot be approximated within a factor of $(\frac{1}{2}- \varepsilon)\ln |V|$ and $(\frac{1}{4}- \varepsilon)\ln |V|$, respectively, unless $P = NP$ (see Section \ref{inapproximability}).
\section{Hardness Results}
\subsection{Hardness of the 1-distance $m$-tuple $(\ell, r)$-domination problem}\label{hardness1}
In this section, we show that the decision version of the 1-distance $m$-tuple $(\ell, r)$-domination problem in graphs is NP-complete by reducing the {\it dominating set} (DS) problem to it, which is known to be NP-complete \cite{garey2002}.

The definition of the decision version of both the problems are as follows:
\begin{description}
\item [Decision version of 1-distance $m$-tuple $(\ell, r)$-domination problem:]
\item[Instance:] A simple undirected graph $G = (V,E)$ with at least $\ell$ vertices and three positive integers $m$, $r$, and $k (\leq |V|)$, where $m \leq \ell$.\vspace{-0.2cm}
\item[Question:] Does $G$ has a 1-distance $m$-tuple $(\ell, r)$-dominating set of size at most $k$?
\end{description}

\begin{description}
\item [Decision version of the DS problem:]

\item [Instance:] A simple undirected graph $G=(V,E)$  and a positive integer $k$.
\vspace{-0.2cm}
\item [Question:] Does there exist a dominating set $D$ of $G$ such that $|D| \leq k$?
\end{description}

\begin{theorem}\label{thm:main1}
 The decision version of the \textsf{1-distance $m$-tuple $(\ell, r)$-domination} problem is NP-complete.
\end{theorem}

\begin{proof}
 For any given set $L\subseteq V$ and a positive integer $k$, we can verify whether $L$ is a 1-distance $m$-tuple
$(\ell, r)$-dominating set of size at most $k$ or not in polynomial time by checking both the conditions of
1-distance $m$-tuple $(\ell, r)$-dominating set. Therefore, 1-distance $m$-tuple $(\ell, r)$-domination problem is in NP.

Now, we prove the hardness of the 1-distance $m$-tuple $(\ell, r)$-domination problem by reducing the decision version of the \textsc{DS} problem, which is known to be NP-complete \cite{garey2002}, to it.
Let $<G=(V,E),k>$ be an instance of the dominating set problem, where $G=(V,E)$ is an undirected graph with vertex set $V=\{v_1,v_2, \ldots ,v_n\}$ and $k$ is an integer.
We construct an instance $<G'=(V',E'),m,\ell, r>$ of the decision version of 1-distance $m$-tuple $(\ell, r)$-domination problem as follows:

\begin{minipage}{.5\textwidth}
\begin{center}
\begin{align*}
V'&=V^1\cup V^2\cup V^3, \text{where}\\
V^1&=\{v_1^1,v_2^1, \ldots ,v_n^1\},\\
V^2&=\{v_1^2,v_2^2, \ldots v_{\ell-1}^2\},\\
V^3&=\{v_1^3,v_2^3, \ldots, v_r^3\}\\%\intertext{and}
\end{align*}
\end{center}
\end{minipage}%
\begin{minipage}{.5\textwidth}
\begin{center}
\begin{align*}
 E'&=E^1\cup E^2\cup E^3\cup E^4, \text{where}\\
 E^1&=\{(v_i^1,v_j^1)\mid (v_i,v_j) \in E\},\\
 E^2&=\{(v_i^2,v_j^2)\mid 1\leq i<j\leq \ell-1\},\\
 E^3&=\{(v_i^1,v_j^2)\mid 1\leq i \leq n, 1\leq j\leq \ell-1\},\\
 E^4&=\{(v_i^2,v_j^3)\mid 1\leq i \leq \ell-1, 1 \leq j \leq r\}
\end{align*}
\end{center}
\end{minipage}%

Observe that, $G'=(V',E')$ can be constructed in polynomial time and $|V'|=n+\ell+r-1$, where $n=|V|$ and $\ell, r <n$.
An illustration for the construction of $G'$ from $G$ is shown in Figure \ref{hardnessfig1}(a).

\begin{figure}[!t]
\centering
\includegraphics[scale=0.75]{figure1.pdf}
\caption{(a) A graph $G'=(V',E')$ constructed for an instance of the 1-distance $m$-tuple $(\ell,r)$-domination problem, and (b) a graph $G'=(V',E')$ constructed for an instance of the $d$-distance $m$-tuple $(\ell,2)$- domination problem.}\label{hardnessfig1} \vspace{-0.40cm}
\end{figure}

{\bf Claim 1:} {\it $G$ has a dominating set of size at most $k$ if and only if $G'$ has a 1-distance $m$-tuple $(\ell, r)$-dominating set of size at most $k+\ell$}.

{\it \bf Proof:} Let $D$ be a dominating set of $G$ and $|D|\leq k$.
Let $L=\{v_i^1 \mid v_i\in D\}\cup V^2\cup \{v_1^3\}$.
Now, we show that $L$ is a 1-distance $m$-tuple $(\ell, r)$-dominating set in $G'$.

{\bf (i)} Observe that for each $v \in V'$, $|N^1_{G'}[v] \cap L| \geq m$ as $m \leq \ell$ (value of $r=1$ in case of $m = \ell$)
and each $v \in V'$ is dominated by $\ell-1$ vertices in $V^2$.

{\bf (ii)} Let $U = \{u_1, u_2, \ldots, u_r\} \subseteq V'$ be an arbitrary subset of size $r$.

{\bf Case 1:} Let $U \cap V^2 \neq \emptyset$ and $v_i^2 \in U \cap V^2$. From the construction of $G'$,
$N_G^1[v_i^2] \cap L \supseteq V^2 \cup \{v_1^3\}$, which implies $|N_G^1[v_i^2] \cap L| \geq \ell$. Therefore,
$|(\cup_{u \in U} N_G^1[u]) \cap L| \geq \ell$.

{\bf Case 2:}  Let $U \cap V^1 \neq \emptyset$ and $v_i^1 \in U \cap V^1$. From the constructions of $G'$ and $L$,
$N_G^1[v_i^1] \cap L \supseteq V^2 \cup \{v_j^1\}$, where $v_j \in D$ is a dominator of $v_i$ in $G$. Therefore, $|N_G^1[v_i^1] \cap L| \geq \ell$, which leads to $|(\cup_{u \in U} N_G^1[u]) \cap L| \geq \ell$.

{\bf Case 3:} Let $U = V^3$. Again, from the constructions of $G$ and $L$, $(\cup_{u \in U} N_G^1[u]) \cap L \supseteq V^2 \cup \{v_1^3\}$. Therefore,
in this case also $|(\cup_{u \in U} N_G^1[u]) \cap L| \geq \ell$.

Thus $L$ is a 1-distance $m$-tuple $(\ell,r)$-dominating set in $G'$ and  $|L| \leq k+\ell$.

Conversely, let $L$ be a 1-distance $m$-tuple $(\ell,r)$-dominating set for $G'$ of size at most $k+\ell$.
From the definition of the 1-distance $m$-tuple $(\ell,r)$-dominating set and as $|V^3| = r$,
$|(\cup_{v \in V^3} N^1_{G'}[v] ) \cap L|\geq \ell$.
Therefore, there must be at least $\ell$ vertices from $V^2 \cup V^3$ in $L$ (see Figure \ref{hardnessfig1}(a)).
Let $D=\{v_i\in V\mid v_i^1\in L \setminus (V^2 \cup V^3)\}$.
If $D$ is a dominating set of $G$, then we are done as $|D| \leq k$.
Suppose $D$ is not a dominating set in $G$.
Since $|V^2|$ is $\ell-1$, the 1-distance neighborhood of every subset of $V^1$ with cardinality greater than or equal to $r$ will have a non-empty intersection with $D$ (due to the second condition of 1-distance $m$-tuple $(\ell,r)$-domination). This implies, for any subset $U^1$ of $V$, $D \cap (\cup_{u \in U^1}N^1_G[u])=\emptyset$ if and only if $|U^1|\leq r-1$. Note that such a set $U^1 (\neq \emptyset)$ exists
based on our assumption that $D$ is not a dominating set of $G$. Let $|U^1|=s$. Now, we will show that $|(V^2 \cup V^3) \cap L| \geq \ell+s$.

Let $U^2 (\subseteq V^2)$ and $U^3 (\subseteq V^3)$ be the maximum size subsets such that $U^2 \cap L = \emptyset$ and
 $U^3 \cap L = \emptyset$, respectively. Let $s' = |U^2|$ and $s'' = |U^3|$. Let $U_{13} = U^1 \cup U^3$. Since
$(\cup_{u \in U_{13}}N^1_{G'}[u])\cap L = V^2\setminus U^2$, i.e., $|(\cup_{u \in U_{13}}N^1_{G'}[u])\cap L| = \ell-1-s' < \ell$,
$|U_{13}| = s+s'' < r$. Add $r-s-s''$ vertices from $V^3\setminus U^3$ to the vertex set $U_{13}$. Now, by the definition of $L$
the size of the set $|(\cup_{u \in U_{13}}N_{G'}^1[u])\cap L|$ must be at least $\ell$. Therefore, $r-s-s'' + \ell-1-s' \geq \ell$,
which implies $r-s'' \geq s+s'+1$.

Since $r-s'' \geq s+s'+1$, $|D|\leq k-s$. Let $D_1 = D \cup U^1$. So, every vertex in $V$ is dominated by at least one vertex in $D_1$ whose size is at most $k$. Therefore, we conclude, the decision version of 1-distance $m$-tuple $(\ell,r)$-domination problem is NP-complete.
\end{proof}

\subsection{Hardness of the $d$-distance $m$-tuple {$(\ell,2)$-domination} problem}\label{hardness2}
In this section, we show that the decision version of $d$-distance $m$-tuple $(\ell,2)$-domination problem is NP-complete.
 For fixed constant $d \geq 2$, the decision version of the problem is defined as follows.

\begin{description}
\item [Instance:] An undirected connected graph $G = (V,E)$ with $|V|\geq \ell$ and three positive integers $m$, $d$, and $k (\leq |V|)$, where $m \leq \ell$.
\vspace{-0.1in}
\item [Question:] Does $G$ has a $d$-distance $m$-tuple $(\ell,2)$-dominating set of size at most $k$?
\end{description}

We prove that decision version of $d$-distance $m$-tuple $(\ell,2)$-domination problem ($d \geq 2$) is NP-complete by reducing the decision
version of the 1-distance $m$-tuple $(\ell,2)$-domination problem to it in polynomial time. Note that 1-distance $m$-tuple
$(\ell,2)$-domination problem is NP-complete (see Section \ref{hardness1}). Recall, the decision version of 1-distance $m$-tuple $(\ell,2)$-domination problem:

\begin{description}
 \item [Instance:] An undirected connected graph $G = (V,E)$ with $|V|\geq \ell$ and two positive integer $m, k \leq |V|$, where $m \leq \ell$.
\vspace{-0.1in}
 \item [Question:] Does $G$ has a 1-distance $m$-tuple $(\ell,2)$-dominating set of size at most $k$?
\end{description}

\begin{theorem}\label{thm:decissiontheorem}
The decision version of the $d$-distance $m$-tuple $(\ell,2)$-domination problem is NP-complete.
\end{theorem}

\begin{proof}
The decision version of the $d$-distance $m$-tuple $(\ell,2)$-domination problem is in NP as for a given certificate (a subset of $V$) we can verify whether it is satisfying both the conditions of the $d$-distance $m$-tuple $(\ell,2)$-dominating set or not in polynomial time.

We now describe a polynomial time reduction from an arbitrary instance
of the decision version of 1-distance $m$-tuple $(\ell,2)$-domination problem to an instance of the
decision version of the $d$-distance $m$-tuple $(\ell,2)$-domination problem.

Let $G=(V=\{v_1,v_2, \ldots ,v_n\},E)$ be an arbitrary instance of the decision version of 1-distance $m$-tuple
$(\ell,2)$-domination problem. We construct an instance, a graph $G'=(V',E')$, of the decision version of the
$d$-distance $m$-tuple $(\ell,2)$-domination problem as follows:\vspace{-0.60cm}

\begin{align*}
V'&=\{v_i'\mid v_i \in V\} \cup (\bigcup_{v_i \in V}\{v_{i1}',v_{i2}',\ldots,v_{id-1}'\})   (see\ Figure\ \ref{hardnessfig1}(b)\ for\ an\ example)\\
E'&=\{(v_i',v_j') \mid (v_i,v_j)\in E\}\cup
(\bigcup_{v_i \in V}\{(v_i',v_{i1}'),(v_{i1}',v_{i2}'),\ldots,(v_{id-2}',v_{id-1}')\})
\end{align*}\vspace{-0.40cm}

\noindent
{\bf Claim 2:} {\it $G$ has a 1-distance $m$-tuple $(\ell,2)$-dominating set of cardinality at most $k$ if and only if
$G'$ has a $d$-distance $m$-tuple $(\ell,2)$-dominating set of cardinality at most $k$}.\\
{\bf Necessity:} Let $L$ be a 1-distance $m$-tuple $(\ell,2)$-dominating set of $G$ such that $|L|\leq k$.
Let $L'=\{v_i' \in V' \mid v_i \in L\}$. We can argue that $L'$ is a $d$-distance $m$-tuple $(\ell,2)$-dominating set in $G'$ and $|L'| \leq k$.
Since $|L'| = |L|$ and $|L|\leq k$, so $|L'| \leq k$. As each vertex $v \in V$ satisfies
1-distance $m$-tuple $(\ell,2)$-domination properties and each vertex in $G'$ is at most $d-1$ distance
away from a vertex in $L'$, $L'$ suffices to ensure $d$-distance $m$-tuple $(\ell,2)$-dominating set in graph $G'$ for $d \geq 2$.

{\bf Sufficiency:} Let $L'$ be a $d$-distance $m$-tuple $(\ell,2)$-dominating set in $G'$ such that $|L'|\leq k$. We shall show that,
by updating (i.e., removing or replacing) some of the vertices in $L'$, at most $k$ vertices from
$\{v_1',v_2',\ldots,v_n'\}$ can be chosen such that the set of corresponding vertices in $V$ is an
1-distance $m$-tuple $(\ell,2)$-dominating set in $G$. Let $L''=L'$. For each vertex $v_{ij}' \in V'$,
$(1 \leq j \leq d-1$ and $1 \leq i \leq n)$ we do the following: if $v_{ij}' \in L''$, then replace it with its
associated vertex $v_i'$ if $v_i'$ is not already in $L''$, otherwise, replace it with any vertex in
$N^1_{G'}[v_i'] \cap \{v_1',v_2',\ldots,v_n'\}$ which is not in $L''$. If all the vertices of
$N^1_{G'}[v_i'] \cap \{v_1',v_2',\ldots,v_n'\}$ are in $L''$
(i.e., $(N^1_{G'}[v_i']\cap \{v_1',v_2',\ldots,v_n'\}) \subseteq L'' )$, then remove $v_{ij}'$ from $L''$.
Therefore, $|L''| \leq k$. Let $L=\{v_i \in V \mid v_i' \in L''\}$. Now, we prove that $L$ is an
1-distance $m$-tuple $(\ell,2)$-dominating set in $G$ such that $|L|\leq k$.

Since $|L''|\leq k$, then $|L| \leq k$. We first prove the first condition (i.e., for every $v \in V$,
$|N^1_G[v]\cap L| \geq m$) of 1-distance $m$-tuple $(\ell,2)$-dominating set. Consider a vertex  $v_i' \in V'$, for some
$1 \leq i \leq n$, let $s$ be the number of vertices in $L' \cap \{v_{i1}',v_{i2}',\ldots,v_{id-1}'\}$.

{\bf Case 1. $s=0$.}
Since $L'$ is $d$-distance $m$-tuple $(\ell,2)$-dominating set, there must exist at least $m$ vertices, say $\{v_1'',v_2'', \ldots, v_m''\}$ in $\{v_1',v_2', \ldots,v_n'\}\cap L'$ such that $\{v_1'',v_2'', \ldots , v_m''\} \subseteq N^d_{G'}[v_{i,d-1}']$, otherwise, $L'$ is not a feasible solution as $v_{id-1}'$ does not have $m$ distance-$d$ $(m,\ell)$-dominators.
Therefore, $|N^1_{G'}[v_i'] \cap (\{v_1',v_2', \ldots,v_n'\} \cap L'')|\geq m$.\\
{\bf Case 2. $s \geq 1$.}
Let $v_{ij_1}',v_{ij_2}', \ldots, v_{ij_t}'\in L'$, for some $1\leq j_1,j_2, \ldots, j_t\leq d-1$.
By our construction of $L''$ each vertex in $\{v_{ij_1}',v_{ij_2}', \ldots, v_{ij_t}'\}$ is replaced by one of the vertices in $N^1_{G'}[v_i'] \cap \{v_1',v_2', \ldots,v_n'\}$.
Therefore, in this case also $|N^1_{G'}[v_i'] \cap (\{v_1',v_2', \ldots,v_n'\}\cap L'')| \geq m$. Thus, by our construction of $L$ from $L''$, $|N^1_G[v_i] \cap L|\geq m$ is true.

Now we prove the second condition of 1-distance $m$-tuple $(\ell,2)$-dominating set (i.e., for every pair of distinct vertices $u,v \in V$, $|(N^1_G[u]\cup N^1_G[v])\cap L| \geq \ell$).

Let $v_i$ and $v_j$ be two distinct vertices in $G$. Consider the vertices $v_{id-1}'$ and $v_{jd-1}'$ in $G'$.
As $L'$ is a $d$-distance $m$-tuple $(\ell,2)$-dominating set of $G'$, it satisfies the second property of $d$-distance $m$-tuple $(\ell,2)$-domination in $G'$.
Thus there exist at least $\ell$ dominators dominating $v_{id-1}'$ and $v_{jd-1}'$ in $L'$, i.e., $|(N^d_{G'}[v_{id-1}']\cup N^d_{G'}[v_{jd-1}'])\cap L'|\geq \ell$.
These dominators are either from $N^1_G[v_i'] \cup N^1_G[v_j']$ or from
$\{v_{i1}',v_{i2}',\ldots,v_{id-1}'\}$ and/or from $\{v_{j1}',v_{j2}' \ldots,v_{jd-1}'\}$.
As per our construction of $L''$ from $L'$, we are replacing each dominator in $\{v_{i1}',v_{i2}',\ldots,v_{id-1}'\} \cup \{v_{j1}',v_{j2}' \ldots,v_{jd-1}'\} $ (if any) by a vertex in $(N^1_{G'}[v_i'] \cup N^1_{G'}[v_j']) \cap \{v_1',v_2',\ldots,v_n'\}$.

Since $G$ is connected and $|V|\geq \ell$, so is $G'$. Therefore, $L''$ contains  at least $\ell$ vertices from $(N^1_{G'}[v_i'] \cup N^1_{G'}[v_j']) \cap \{v_1',v_2',\ldots,v_n'\}$, i.e., $|(N^1_{G'}[v_i'] \cup N^1_{G'}[v_j']) \cap \{v_1',v_2',\ldots,v_n'\} \cap L''| \geq \ell$.
Therefore, according to the construction of $L$ from $L''$, $|(N^1_G[v_i] \cup N^1_G[v_j]) \cap L| \geq \ell$.
Thus, $L$ is a 1-distance $m$-tuple $(\ell,2)$-dominating set of the graph $G$ having cardinality at most $k$.

 Therefore, the decision version of $d$-distance $m$-tuple $(\ell,2)$-domination problem is NP-complete.
\end{proof}
\vspace{-0.70cm}
\section{Inapproximability results}\label{inapproximability}

\subsection{Inapproximability of the 1-distance $m$-tuple $(\ell,r)$-domination problem} \label{inapproximability1}
In this section, we prove that the 1-distance $m$-tuple $(\ell,r)$-domination problem cannot be approximated
within a factor of $(\frac{1}{2}- \varepsilon) \ln(|V|)$ for any $\varepsilon >0$, unless P = NP.
We argue the claim by showing that if 1-distance $m$-tuple $(\ell,r)$-domination problem can be approximated within a factor of $(\frac{1}{2}- \varepsilon) \ln(|V|)$ for any $\varepsilon >0$ in a graph $G'$, then the domination problem can be approximated within a factor of $(1- \varepsilon) \ln(|V|)$ for any $\varepsilon >0$.

\begin{theorem} \cite{dinur} \label{thm:dinur}
For every $\varepsilon >0$, it is NP-hard to approximate set cover problem within a factor of $(1- \varepsilon) \ln n$, where $n$ is the size of the instance. The reduction runs in $n^{O(1/\varepsilon)}$ time.
\end{theorem}

\begin{theorem} \label{thm:inapprox}
Minimum domination problem cannot be approximated within a factor of $(1- \varepsilon) \ln(|V|)$ for any $\varepsilon >0$, unless P = NP.
\end{theorem}

\begin{proof}
The result follows from (i) the relation between set cover problem and dominating set problem, (ii) Theorem
\ref{thm:dinur}, and (iii) the inapproximability result in \cite{chleb}.
\end{proof}

\begin{theorem}\label{thm:own}
Minimum 1-distance $m$-tuple $(\ell,r)$-domination problem cannot be approximated within a factor of
$(\frac{1}{2}- \varepsilon) \ln(|V|)$ for any $\varepsilon >0$, unless P = NP.
\end{theorem}

\begin{proof}
Let $G$ be a simple graph.
Consider the construction of the graph $G'$ for any given graph $G$ as discussed in Section \ref{hardness1}.
As per our construction, we proved that each instance of domination problem can be
reducible to an instance of 1-distance $m$-tuple $(\ell,r)$-domination problem in polynomial-time . \\
Let $D^*$ and $L^*$ be the optimal DS and 1-distance $m$-tuple $(\ell,r)$-dominating set in $G$ and $G'$,
with cardinalities $\gamma_{ds}(G)$  and $\gamma_{m \ell r}(G')$, respectively. Now we can argue the following
claim: $\gamma_{m \ell r}(G')=\gamma_{ds}(G)+\ell$. The inequality $\gamma_{m \ell r}(G')\leq \gamma_{ds}(G)+\ell$
is trivial as per our construction in Section \ref{hardness1}. On the other hand,
$\gamma_{m \ell r}(G')\geq \gamma_{ds}(G)+\ell$ follows from the sufficiency proof of Claim 1 in Section \ref{hardness1}.
So given a dominating set $D$ of $G$, one can find a 1-distance $m$-tuple $(\ell,r)$-dominating set $L$ of $G'$ such that
$|L|=|D|+\ell$. Now, $\frac{|L|}{|L^*|}=\frac{|D|+\ell}{|D^*|+\ell} \geq \frac{1}{2} \frac{|D|}{|D^*|}$. Suppose
there exists a polynomial time algorithm that approximates 1-distance $m$-tuple $(\ell,r)$-domination problem within
a factor of $(\frac{1}{2}- \varepsilon) \ln N$ for graphs with $N$ vertices. As per our construction of the graph $G'$ from
$G$ (see Figure \ref{hardnessfig1}(a)), $G'$ contains, $N=n+\ell+r - 1 \leq 3n$ for  $n \geq 2$ vertices, where $n$ is the
total number of vertices in $G$, $\ell < n$, and $r < n$. Therefore,\vspace{-0.50cm}

\begin{align*}
\frac{|D|}{|D^*|}\leq  (1- 2\varepsilon) \ln N \leq (1- 2\varepsilon) \ln n(1+ \frac{\ln 4}{\ln n}).
\end{align*}\vspace{-0.50cm}

For sufficiently large $n$, the term $(1+ \frac{\ln 4}{\ln n})$ can be bounded by $1+\frac{\varepsilon}{5}$,
where $\varepsilon \geq \frac{5 \ln 4}{\ln n}$. Now we have\vspace{-0.70cm}

\begin{align*}
(1- 2\varepsilon) \ln n(1+ \frac{\ln 4}{\ln n}) \leq (1- 2\varepsilon)[\ln n + \ln (1+ \frac{\varepsilon}{5})] \leq
(1- 2\varepsilon)[\ln n +  \frac{\varepsilon}{5} \ln n] \leq (1- \varepsilon')\ln n,
\end{align*}\vspace{-0.50cm}

where $\varepsilon' < \frac{9}{5} \varepsilon+ \frac{2}{5}\varepsilon^2$. Therefore, for an arbitrary graph, we can
approximate the domination problem by a factor of $(1-\varepsilon')\ln n$, which leads to a contradiction to
Theorem \ref{thm:inapprox}. Thus, the minimum 1-distance $m$-tuple $(\ell,r)$-domination problem cannot
be approximated within a factor of $(\frac{1}{2}- \varepsilon) \ln(|V|)$ for any $\varepsilon >0$, unless P = NP.
\end{proof}

\subsection{Inapproximability of the $d$-distance $m$-tuple $(\ell,2)$-domination problem}\label{inapproximability2}

In this section, we give a lower bound on the approximation ratio of any approximation algorithm for the
$d$-distance $m$-tuple $(\ell,2)$-domination problem by providing an approximation preserving reduction from the
1-distance $m$-tuple $(\ell,r)$-domination problem for $r=2$.

\begin{theorem}\label{thm:inaprox}
Given a simple undirected graph $G=(V,E)$, the $d$-distance $m$-tuple $(\ell,2)$-domination problem cannot be approximated within a
factor of $(\frac{1}{4}- \varepsilon)\ln |V|$, for any fixed constant $d\geq 2$ and $\varepsilon>0$, unless P = NP.
\end{theorem}

\begin{proof}
Let $G=(V,E)$ be an arbitrary instance of the 1-distance $m$-tuple $(\ell,2)$-domination problem with $n$ vertices.
Given $G=(V,E)$, we construct a graph $G'=(V',E')$, an instance of the $d$-distance $m$-tuple $(\ell,2)$-domination problem as described in Section \ref{hardness2}. Let $L^*$ and $L_d^*$ be the optimal 1-distance $m$-tuple $(\ell,2)$-dominating set and
$d$-distance $m$-tuple $(\ell,2)$-dominating set in $G$ and $G'$, with cardinalities $\gamma_{m \ell}(G)$  and $\gamma_{m \ell}^d(G')$, respectively.
Now we can argue the following claim: $\gamma_{m \ell}^d(G')=\gamma_{m \ell}(G)$.
The inequality $\gamma_{m \ell}^d(G')\leq \gamma_{m \ell}(G)$ is trivial as every 1-distance $m$-tuple $(\ell,2)$-dominating set
of $G$ is a $d$-distance $m$-tuple $(\ell,2)$-dominating set in $G'$. On the other hand, $\gamma_{m \ell}^d(G')=|L_d^*|\geq |L|$ follows from the
sufficiency proof of Claim 2 in Section \ref{hardness2}. \\
Given any 1-distance $m$-tuple $(\ell,2)$-dominating set $L$ of $G$, one can find a $d$-distance $m$-tuple $(\ell,2)$-dominating set $L_d$
of $G'$ with $|L_d|=|L|$. Suppose there exist a polynomial time algorithm to approximate $d$-distance $m$-tuple $(\ell,2)$-domination problem
within a factor of $(\frac{1}{4}-\varepsilon)\ln |V'|$, where $|V'| = n + n(d-1) \leq n^2$ (see Section \ref{hardness2}).
Now $\frac{|L|}{|L^*|}=\frac{|L_d|}{|L_d^*|}\leq (\frac{1}{4}-\varepsilon)\ln n^2 = (\frac{1}{2}-2\varepsilon)\ln n\leq (\frac{1}{2}-\varepsilon')\ln n$, where $\varepsilon' \leq 2\varepsilon$.
Therefore, the result follows from Theorem \ref{thm:own}.
\end{proof}

 \section{Conclusion}\label{sec:conclusion}
In this article, we studied $d$-distance $m$-tuple ($\ell, r$)-domination problem. We provided a common NP-completeness
proof of the 1-distance $m$-tuple ($\ell, r$) domination problem for each fixed value of $m, \ell$, and
$r$. We also presented a common NP-completeness proof of the $d$-distance $m$-tuple  ($\ell, 2$) domination
problem for each fixed value of $d (> 1), m$, and $\ell$. We have showed that the first problem is not approximated
within a factor of $(\frac{1}{2}- \varepsilon)\ln |V|$ for each fixed value of $m, \ell$, and $r$, unless P = NP
and the second problem is not approximated within a factor of $(\frac{1}{4}- \varepsilon)\ln |V|$ for each fixed value of  $d (> 1), m$, and $\ell$, unless P = NP, where $V$ is the vertex set of the input graph. The reduction in the NP-completeness/inapproximability proofs are very powerful as these are common reductions for completely different kind of dominations.

\vspace{-0.15in}
\bibliographystyle{plain}