On graphs with a few distinct reciprocal distance Laplacian eigenvalues

1.   Introduction

Throughout the article, we assume that $\Gamma = (V(\Gamma), E(\Gamma))$ is simple and connected graph, where $V(\Gamma) = \{v_{1}, v_{2}, \ldots, v_{\nu}\}$ is the vertex set and $E(\Gamma)$ is the set of edges. No multiple edges and loops are allowed. The number of vertices in $V(\Gamma)$ is denoted by $\nu$ and it is called the order, while the cardinality of $E(\Gamma)$ is the size of $\Gamma$. The number of edges emanating from $v_i$ is denoted by $d_{\Gamma}(v_i)$ (or shortly $d_i$), and it is called degree of a vertex $v_i.$ We denote the complement of $\Gamma$ as $\overline{\Gamma}$.

An $\nu\times \nu$, $(0, 1)$ matrix $A(\Gamma) = (a_{ij})$ is the adjacency matrix of $\Gamma$, $Deg(\Gamma) = \text{diag}(d_1, d_2, \dots, d_\nu)$ is the diagonal matrix of vertex degrees and $L(\Gamma) = Deg(\Gamma)-A(\Gamma)$ is the Laplacian matrix of $\Gamma$. The eigenvalues of semi-definite, symmetric matrix $L(\Gamma)$: $\mu_1 (\Gamma) \geq \mu_2 (\Gamma)\geq \dots \geq \mu_\nu (\Gamma)$ are called the Laplacian eigenvalues of $\Gamma$. The Laplacian spectrum (briefly $L$-spectrum) of $\Gamma$ is the set of all Laplacian eigenvalues, including their multiplicities. For two vertices $v_i, v_j\in V(\Gamma)$, $d(v_i, v_j)$ denotes the length of a shortest path between them. It is called the distance between $v_i$ and $v_j$. The reciprocal distance matrix $RD(\Gamma)$ (also called Harary matrix) of a graph $\Gamma$ ^[1], is a matrix of order $\nu$ defined as

For relevant work regarding the Harary matrix, we refer the reader to ^[2,3,4].

Subsequently, we assume $i\neq j$ when $d(v_i, v_j)$ is considered. The reciprocal distance degree $RTr_\Gamma(v_i)$, (or shortly $RTr(v_i)$) of a vertex $v_i\in V(\Gamma)$ is defined as

The diagonal matrix $\text{diag}(RTr_\Gamma(v_1), \ldots, RTr_\Gamma(v_\nu))$ is denoted by $RT(\Gamma)$.

The reciprocal distance Laplacian matrix $RD^L(\Gamma) = RT(\Gamma)-RD(\Gamma)$ was for the first time introduced in ^[5]. It is a real, symmetric matrix with nonnegative eigenvalues. Its eigenvalues will be given in non-increasing order as follows $\varrho_1(\Gamma)\geq \varrho_2(\Gamma)\geq \dots \geq \varrho_{\nu-1}(\Gamma) > \varrho_\nu(\Gamma) = 0$. The reciprocal distance Laplacian spectral radius is the largest eigenvalue $\varrho_1(\Gamma)$. The reciprocal distance Laplacian spectrum (briefly $RD^L$-spectrum) of $\Gamma$ refers to the multiset of all eigenvalues of $RD^L(\Gamma)$. The multiplicity of the reciprocal distance Laplacian eigenvalue $\varrho_i(\Gamma)$ of $\Gamma$ is denoted by ${{{\rm{mult}}}}_{RD^L}(\varrho_i(\Gamma))$. For the connected graph $\Gamma$ of order $\nu$, the largest eigenvalue of $RD^L(\Gamma)$ does not exceed $\nu$. In addition, the necessary and sufficient conditions for $\nu$ to be the eigenvalue of $RD^L(\Gamma)$ are known and are presented in ^[5]. If $\nu$ is an eigenvalue of $RD^L(\Gamma)$, then its multiplicity provides an information on the number of components in $\overline{\Gamma}$ (see ^[6]). Supplemental results related to the matrix $RD^L(\Gamma)$ can be found in ^[7,8,9].

Graphs having a few distinct eigenvalues are usually of special interest due to their interesting combinatorial properties. These graphs tend to have some kind of regularity and they have been studied in relation to various matrices associated to graphs. In addition, to determine graphs with a given spectrum, it becomes evident that a large number of distinct eigenvalues makes the problem extremely complex. For this reason, the graphs with small number of distinct eigenvalues are usually the first ones to be approached.

A plethora of different matrices have been associated with graphs. Most of them possess some distinguishable property suitable for retrieving important information on a graph. In that sense, the crucial contribution of $RD^L$ spectrum is on graph connectivity, as mentioned above. So far, the reciprocal distance Laplacian spectrum of a graph has been subject of ^[5,6,7,8]. There, one can find results on connectivity, bounds on the largest $RD^L$ eigenvalue, information on distribution of eigenvalues, etc. Here, our focus is on the determination of connected graphs with small numbers of distinct $RD^L$ eigenvalues. As a main tool in our approach, we employ an interplay between the Laplacian and $RD^L$ spectra of a graph.

As usual, $S_{\nu}$ and $K_\nu$ are, respectively, the star graph and the complete $\nu$-vertex graph. A complete multipartite graph is denoted by $K_{t_1, t_2, \dots, t_k}$, where $k$ is the number of partite classes and $t_1 +t_2 +\dots+t_k = \nu$. If $k = 2$, then it is called a complete bipartite graph. Let $\Gamma_1$ and $\Gamma_2$ be the graphs with disjoint vertex sets $V(\Gamma_1)$ and $V(\Gamma_2)$. Then the union $\Gamma_1\cup \Gamma_2$ is the graph whose vertex set is $V(\Gamma_1)\cup V(\Gamma_2)$ and edge set is $E(\Gamma_1)\cup E(\Gamma_2)$. The join of $\Gamma_1$ and $\Gamma_2$ is the graph $\Gamma_1\cup\Gamma_2$ along with all the edges with one end in $V_1$ and the other one in $V_2$. It is denoted by $\Gamma_1\vee \Gamma_2$. By $q\Gamma$, we abbreviate the $q$ copies of $\Gamma$, for some positive integer $q$. For more important notions and definitions in graph theory, see ^[10].

The organization on the remaining content of the paper is as follows. In Section $2$, we determine the graph with only two distinct reciprocal distance Laplacian eigenvalues and also completely determine the classes of graphs with a $RD^L$ eigenvalue of multiplicity $|V(\Gamma)|-2$. In Section $3$, we determine some graph classes with the reciprocal distance Laplacian eigenvalues of multiplicity $|V(\Gamma)|-3$.

2.   Graph with $RD^L(\Gamma)$ eigenvalues of multiplicity $\nu-1$ and $\nu-2$

We begin this section with two observations: The multiplicity of $0$ as an eigenvalue of $L(\Gamma)$ equals the number of components in $\Gamma$; for any connected graph $\Gamma$, $0 < \varrho_i(\Gamma) \le \nu$, for all $1\le i \le \nu-1$.

We first characterize the unique graph of given order with exactly two distinct reciprocal distance Laplacian eigenvalues.

Theorem 2.1. Let $\Gamma$ be a connected graph with $\nu \ge 2$ vertices. Then ${{{\rm{mult}}}}_{RD^L}(\varrho_1(\Gamma))\le \nu-1$. The equality holds if and only if $\Gamma$ is a complete graph on $\nu$ vertices.

Proof. The $RD^L$-spectrum of $K_\nu$ is equal to $\{\nu^{(\nu-1)}, 0\}$, which proves that the equality holds for $\Gamma = K_\nu$. Suppose further that ${{{\rm{mult}}}}_{RD^L}(\varrho_1(\Gamma)) = \nu-1$. We order the vertices of $\Gamma$ so that $RT_{min} = RTr(v_1)\le RTr(v_2)\le \dots \le RTr(v_\nu) = RT_{max}$, where $RT_{min}$ and $RT_{max}$ are the minimum and the maximum reciprocal distance degrees in $\Gamma$, respectively. Since $\Gamma$ has only two distinct eigenvalues, $0$ and $\varrho_1(\Gamma)$, and $\textbf{1} = (1, 1, \dots, 1)^\intercal$ is an eigenvector of $RD^L(\Gamma)$ afforded by $0$, each vector $\mathbf{y} = (y_1, y_2, \dots, y_\nu)^\intercal$ with $y_1 = 1$, $y_j = -1$ and $y_i = 0$ for $i\ne1, j$ is an eigenvector of $RD^L(\Gamma)$ associated to the eigenvalue $\varrho_1(\Gamma)$. By equating the first entries of $RD^L(\Gamma)\mathbf{y} = \varrho_1(\Gamma)\mathbf{y}$, we obtain $RT_{min}+\frac{1}{d(v_1, v_j)} = \varrho_1(\Gamma)$ or $\frac{1}{d(v_1, v_j)} = \varrho_1(\Gamma)-RT_{min}$. The above equation holds for all $2\le j\le n$, that is,

It is clear that the above equalities are valid only if $d(v_1, v_j) = 1$ for all $2\le j\le \nu$. This shows that the vertex $v_1$ is adjacent to every other vertex in $\Gamma$. Thus, $RT_{min} = \nu-1$ which is true if and only if $\Gamma$ is $K_\nu$.

A class of graphs that do not contain a path on $4$ vertices as an induced subgraph is known as a class of cographs (see ^[11]). The following characterizations of cographs will be needed in the following.

Lemma 2.2. ^[11] Given a graph $\Gamma$ the following are equivalent:

a) $\Gamma$ is a cograph.

b) The complement of any nontrivial connected subgraph of $\Gamma$ is disconnected.

c) Every connected subgraph of $\Gamma$ is of diameter less than $3.$

In order to make the paper self-contained, we include a useful observation on the structure of eigenvectors corresponding to the multiple eigenvalues.

Lemma 2.3. ^[12] Let $S$ be an $\nu\times \nu$ symmetric matrix and $\lambda$ an eigenvalue of $S$ with multiplicity $k$. If $\gamma\subset\{1, 2, \dots, \nu\}$ with $k-1$ elements, then there exists an eigenvector $\mathbf{z} = (z_1, z_2, \ldots, z_\nu)^\intercal$ of $S$ afforded by $\lambda$ such that $z_i = 0$ whenever $i \in \gamma$.

The subsequent result provides the relation between the existence of induced $P_4$ in $\Gamma$ and the $RD^L$-spectrum of $\Gamma$.

Lemma 2.4. Let $\Gamma$ be a connected graph that is not a cograph with $\nu\ge4$ vertices, different from the complete graph. Then ${{{\rm{mult}}}}_{RD^L}(\varrho_1(\Gamma))\le \nu-3.$

Proof. Since $\Gamma$ is not a cograph, $\Gamma$ contains a path on $4$ vertices as an induced subgraph. Assume that the vertices $v_1, v_2, v_3, v_4$ induce $P_4$. Denote by $R$ the principal submatrix of $RD^L(\Gamma)$ induced by the rows/columns corresponding to $v_1, v_2, v_3, v_4$. Let $\delta_1\ge \delta_2\ge \delta_3 \ge \delta_4$ be the eigenvalues of $R$. If possible, let ${{{\rm{mult}}}}_{RD^L}(\varrho_1(\Gamma))\ge \nu-2$. By Theorem 2.1, it follows that ${{{\rm{mult}}}}_{RD^L}(\varrho_1(\Gamma)) = \nu-2$, due to $\Gamma\ncong K_\nu$. Next, Cauchy interlacing theorem implies that $\delta_1 = \delta_2 = \varrho_1(\Gamma)$. By Lemma 2.3, there is an eigenvector $\textbf{r} = (r_1, r_2, 0, r_4, 0, \dots, 0)^\intercal$ of $RD^L(\Gamma)$ associated to the eigenvalue $\varrho_1(\Gamma)$ with $\textbf{r}\bot \textbf{1}$. Consequently, $\textbf{r}^* = (r_1, r_2, 0, r_4)^\intercal$ is an eigenvector of $R$ for $\varrho_1(\Gamma)$ satisfying $r_1+r_2+r_4 = 0$, as $\textbf{r}\bot \textbf{1}$. We observe that there are only two possible choices $R_1$ and $R_2$ for the matrix $R$:

when there exists no vertex $v_5$ such that $H_i$, $1\le i \le 4$, is an induced subgraph of $\Gamma$ as can be seen in Figure 2.1,

or

when $\Gamma$ contains one of $H_i$, $1\le i \le 4$ as an induced subgraph.

The third entry of the equation $R_1\textbf{r}^* = \varrho_1(\Gamma)\textbf{r}^*$ gives $-\frac{r_1}{2}-r_2-r_4 = 0$ or $\frac{r_1}{2} = 0$, since $r_1+r_2+r_4 = 0$. Thus, $r_1 = 0$ and $r_1+r_2+r_4 = 0$ imply $r_2 = -r_4$. Let $r_2 = s$. Then the vector $\textbf{r}^*$ has the form $\textbf{r}^* = (0, s, 0, -s)^\intercal$. Now, by comparing the first entries of the equation $R_1\textbf{r}^* = \varrho_1(\Gamma)\textbf{r}^*$, we obtain $-s +\frac{s}{3} = 0$ or $-\frac{2s}{3} = 0$ or $s = 0$, which is a contradiction as $\textbf{r}^* = (0, s, 0, -s)^\intercal$ is an eigenvector. Similar arguments lead to a contradiction when we take $R_2$ instead of $R_1$. These contradictions show that the multiplicity of eigenvalue $\varrho_1(\Gamma)$ cannot be greater than or equal to $\nu-2$. This completes the proof.

We recall two lemmas to be employed in the continuation.

Lemma 2.5. ^[5] Let $\Gamma$ be a connected graph. Then, ${{{\rm{mult}}}}_{RD^L}(0) = 1$.

Lemma 2.6. ^[6] Let $\Gamma$ be a connected graph of order $\nu$. If $\nu$ is an eigenvalue of $RD^L(\Gamma)$, then its multiplicity is equal to the number of components in the complement graph $\overline{\Gamma}$ minus $1$.

Next, we pursue the complete characterization of the graphs satisfying ${{{\rm{mult}}}}_{RD^L}(\varrho_1) = \nu-2$.

Theorem 2.7. If $\Gamma\ncong K_\nu$ is a connected graph with $\nu \ge 4$ vertices, then ${{{\rm{mult}}}}_{RD^L}(\varrho_1(\Gamma))\le \nu-2$. The equality holds if and only if $\Gamma\cong K_\nu-e$, where $e$ is an arbitrary edge in $K_\nu$.

Proof. As $\Gamma\ncong K_\nu$, ${{{\rm{mult}}}}_{RD^L}(\varrho_1(\Gamma)) \le \nu-2$, by Theorem 2.1. We will prove that $K_\nu-e$ is the unique graph that satisfies the equality. For that, assume that ${{{\rm{mult}}}}_{RD^L}(\varrho_1(\Gamma)) = \nu-2$. Lemma 2.5 implies that $0$ is a simple eigenvalue of $RD^L(\Gamma)$. Henceforth, the remaining eigenvalue $\varrho_{\nu-1}(\Gamma)$ is also simple eigenvalue of $RD^L(\Gamma)$, that is, ${{{\rm{mult}}}}_{RD^L}(\varrho_{\nu-1}(\Gamma)) = 1$. We distinguish two cases.

Case 1. Let $\varrho_{1}(\Gamma)\ne \nu$. Then, $RD^L$-spectrum of $\Gamma$ is comprised of $\{(\varrho_{1}(\Gamma))^{(\nu-1)}, \varrho_{\nu-1}(\Gamma), 0\}$ with $\varrho_{\nu-1}(\Gamma)\ne\varrho_{1}(\Gamma)$. Since $\varrho_{1}(\Gamma)\ne \nu$, by Lemma 2.6, $\overline{\Gamma}$ is connected, which further shows, by Lemma 2.2, that $\Gamma$ is not a cograph. Additionally, by Lemma 2.4, ${{{\rm{mult}}}}_{RD^L}(\varrho_{1}(\Gamma)) \le \nu-3$, which is a contradiction to our supposition that ${{{\rm{mult}}}}_{RD^L}(\varrho_{1}(\Gamma)) = \nu-2$. Therefore, there exists no graph $\Gamma$ having $RD^L$-spectrum equal to $\{(\varrho_{1}(\Gamma))^{(\nu-1)}, \varrho_{\nu-1}(\Gamma), 0\}$ with $\varrho_{\nu-1}(\Gamma)\ne\varrho_{1}(\Gamma)$ and $\varrho_{1}(\Gamma) \ne \nu$.

Case 2. Let $\varrho_{1}(\Gamma) = \nu$. Then, $RD^L$-spectrum of $\Gamma$ is equal to $\{\nu^{(\nu-2)}, \varrho_{\nu-1}(\Gamma), 0\}$ with $\varrho_{\nu-1}(\Gamma)\ne\varrho_{1}(\Gamma) = \nu$. By Lemma 2.6, $\overline{\Gamma}$ is disconnected with exactly $\nu-1$ components. Thus, $\overline{\Gamma}\cong(\nu-2)K_1\cup K_2$ or $\Gamma\cong K_\nu-e$.

The proof gets completed after observing (see ^[6]) that the $RD^L$-spectrum of $K_\nu-e$ is equal to $\{\nu^{(\nu-2)}, \nu-1, 0\}$. □

Similar to Lemma 2.4, the following result relates the existence of the induced $P_4$ in a graph $\Gamma$ with the $RD^L$-spectrum of $\Gamma$.

Lemma 2.8. If $\Gamma$ is a connected graph with $\nu\ge4$ vertices that is not a cograph, then ${{{\rm{mult}}}}_{RD^L}(\varrho_2(\Gamma))\le \nu-3.$

Proof. The proof follows by proceeding and using arguments similar to Lemma 2.4. □

We continue by recalling two important results on connected graphs that relate the $L$-spectrum and $RD^L$-spectrum for the graphs of diameter $2$.

Lemma 2.9. ^[5] If $\Gamma$ is a connected graph of order $\nu$ and diameter $d = 2$, then $\varrho_i(\Gamma) = \frac{\nu+\mu_i(\Gamma)}{2}$, for $i = 1, 2, \dots, \nu-1$. In addition, both $\frac{\nu+\mu_i(\Gamma)}{2}$ and $\mu_i(\Gamma)$ are of the same multiplicity for all $i = 1, 2, \dots, \nu-1$ in $L(\Gamma)$, $RD^L(\Gamma)$, respectively.

Lemma 2.10. ^[13] Let $\Gamma$ be a graph with $\nu\geq 3$ vertices. Then, the Laplacian spectrum of $\Gamma$ consists of $0, \alpha^{(\nu-2)}, \beta$, $\alpha < \beta$ if and only if $\Gamma\cong K_{\frac{\nu}{2}, \frac{\nu}{2}}$ if $2|\nu$ or $\Gamma\cong S_\nu$.

Now we are in position to completely characterize the graphs with the multiplicity of the second largest reciprocal distance Laplacian eigenvalues equal to $\nu-2$.

Theorem 2.11. Let $\Gamma$ be a connected graph on $\nu \ge 4$ vertices. Then ${{{\rm{mult}}}}_{RD^L}(\varrho_2(\Gamma)) \le \nu-2$. The equality holds if and only if $\Gamma\cong S_\nu$ or $\Gamma\cong K_{\frac{\nu}{2}, \frac{\nu}{2}}.$

Proof. According to Lemma 2.5, $0$ is a simple eigenvalue of $RD^L(\Gamma)$. Therefore, ${{{\rm{mult}}}}_{RD^L}(\varrho_2(\Gamma)) \le \nu-2$. Next, we show that $S_\nu$ and $K_{\frac{\nu}{2}, \frac{\nu}{2}}$ are the only two graphs for which the equality holds. Suppose that ${{{\rm{mult}}}}_{RD^L}(\varrho_2(\Gamma)) = \nu-2$. We separate two cases.

Case 1. Let $\varrho_{1}(\Gamma)\ne \nu$. Then, the $RD^L$-spectrum of $\Gamma$ consists of $\{\varrho_{1}(\Gamma), \varrho_{2}(\Gamma)^{(\nu-2)}, 0\}$ with $\varrho_{2}(\Gamma)\ne\varrho_{1}(\Gamma)$. Since $\varrho_{1}(\Gamma)\ne \nu$, then by Lemma 2.6, $\overline{\Gamma}$ is connected, which further shows, by Lemma 2.2, that $\Gamma$ is not a cograph. Next, Lemma 2.8 implies ${{{\rm{mult}}}}_{RD^L}(\varrho_{2}(\Gamma))\le \nu-3$, which is a contradiction to our supposition that ${{{\rm{mult}}}}_{RD^L}(\varrho_{2}(\Gamma) = \nu-2$. From the above reasoning, we conclude that there exists no graph $\Gamma$ having $RD^L$-spectrum equal to $\{\varrho_{1}(\Gamma), \varrho_{2}(\Gamma)^{(\nu-2)}, 0\}$ with $\varrho_{2}(\Gamma)\ne\varrho_{1}(\Gamma)$ and $\varrho_{1}(\Gamma) \ne \nu$.

Case 2. Assume that $\varrho_{1}(\Gamma) = \nu$. Consequently, the $RD^L$-spectrum of $\Gamma$ is $\{\nu, \varrho_{2}(\Gamma)^{(\nu-2)}, 0\}$ with $\varrho_{2}(\Gamma)\ne\varrho_{1}(\Gamma) = \nu$. By Lemma 2.6, $\overline{\Gamma}$ is disconnected with exactly $2$ components. This assures that the diameter of $\Gamma$ is $2$. By Lemma 2.9, the $L-$spectrum of $\Gamma$ is equal to $\{\nu, (2\varrho_2(\Gamma)-\nu)^{(\nu-2)}, 0\}$ with $\nu\ne 2\varrho_2(\Gamma)-\nu$. Therefore, by Lemma 2.10, either $\Gamma\cong K_{\frac{\nu}{2}, \frac{\nu}{2}}$ or $\Gamma\cong S_\nu$.

We note (see ^[6]) that the $RD^L$-spectrum of $K_{\frac{\nu}{2}, \frac{\nu}{2}}$ and $S_\nu$ are respectively, $\{\nu, (\frac{3\nu}{4})^{(\nu-2)}, 0\}$ and $\{\nu, (\frac{\nu+1}{2})^{(\nu-2)}, 0\}$. Thus, the proof is completed. □

Amalgamating Theorems 2.7 and 2.11, we obtain the complete characterization of the graphs that have an $RD^L$ eigenvalue of multiplicity $\nu-2$.

Theorem 2.12. If $\Gamma$ is a connected graph with $\nu \ge 4$ vertices having an $RD^L(\Gamma)$ eigenvalue less than $\nu$ of multiplicity $2$, then either

(1) ${{{\rm{mult}}}}_{RD^L}(\varrho_1(\Gamma)) = \nu-2$ and $\Gamma\cong K_\nu-e$;

(2) ${{{\rm{mult}}}}_{RD^L}(\varrho_2(\Gamma)) = \nu-2$ and $\Gamma\cong S_\nu$ or $\Gamma\cong K_{\frac{\nu}{2}, \frac{\nu}{2}}.$

3.   On graphs with an eigenvalue of $RD^L(\Gamma)$ with multiplicity $\nu-3$

We commence this section with the observation that the Laplacian eigenvalues of $\overline{\Gamma}$ are determined by the corresponding eigenvalues of $\Gamma$. In particular, $\mu_{\nu-i}(\overline {\Gamma}) = \nu-\mu_i(\Gamma)$, for all $1 \le i \le \nu-1$, where $\{\mu_1(\Gamma), \ldots, \mu_\nu(\Gamma)\}$ is the Laplacian spectrum of $\Gamma$ (see ^[14] for more details). Graphs with a few Laplacian eigenvalues (up to four) have been determined in ^[15]. We revisit one of its results, needed in the proof of the main result of current section.

Lemma 3.1. ^[15] Let $\Gamma$ be a connected graph with $\nu \ge 5$ vertices. Then the $L$-spectrum of $\Gamma$ is $\{\nu, \alpha^{(\nu-3)}, \beta, 0\}$, $\nu \ne \alpha > \beta > 0$, if and only if $\Gamma\cong \overline{K_1 \cup S_{\nu-1}}$ or $\Gamma\cong (K_{\frac{\nu-1}{2}}\cup K_{\frac{\nu-1}{2}})\vee K_1$ when $2|(\nu-1)$; or $\Gamma \cong \frac{\nu}{3} K_1 \vee (K_{\frac{\nu}{3}} \cup K_{\frac{\nu}{3}})$ when $3|\nu$.

We continue with another auxiliary result.

Lemma 3.2. Let $\Gamma$ be a connected graph with $\nu \ge 5$ vertices. Then the $L-$spectrum of $\Gamma$ is $\{\nu, \nu, \alpha^{(\nu-3)}, 0\}$, $\nu \ne \alpha > 0$, if and only if $\Gamma \cong K_{\frac{\nu}{3}, \frac{\nu}{3}, \frac{\nu}{3}}$ when $3|\nu$, or $\Gamma \cong K_{\frac{\nu-1}{2}, \frac{\nu-1}{2}}\vee K_1$ if $2|(\nu-1)$, or $\Gamma \cong (\nu-2)K_1 \vee K_2$.

Proof. Assume that $\Gamma$ is a connected graph with $\nu \ge 5$ vertices whose $L$-spectrum is $\{\nu^{(2)}, \alpha^{(\nu-3)}, 0\}$. Therefore, the $L$-spectrum of $\overline{\Gamma}$ is equal to $\{ (\nu-\alpha)^{(\nu-3)}, 0, 0, 0\}$. Using the fact that the complete graph is determined from its $L$-spectrum, we observe that every component in $\overline{\Gamma}$ is either an isolated vertex or complete graph with the same order. Clearly, the number of isolated vertices in $\overline{\Gamma}$ can be at most $2$, that is, $\overline{\Gamma} \cong K_{\frac{\nu}{3}} \cup K_{\frac{\nu}{3}} \cup K_{\frac{\nu}{3}}$ when $3|\nu$, and $\overline{\Gamma}$ has no isolated vertex, or $\overline{\Gamma} \cong K_{\frac{\nu-1}{2}} \cup K_{\frac{\nu-1}{2}}\cup K_1$ when $2|(\nu-1)$, and $\overline{\Gamma}$ has one isolated vertex, or $\overline{\Gamma} \cong K_{\nu-2} \cup K_1 \cup K_1$ if $\overline{\Gamma}$ has two isolated vertices. Hence, $\Gamma \cong K_{\frac{\nu}{3}, \frac{\nu}{3}, \frac{\nu}{3}}$ if $3|\nu$, or $\Gamma \cong (K_{\frac{\nu-1}{2}, \frac{\nu-1}{2}})\vee K_1$ if $2|(\nu-1)$, or $\Gamma \cong (\nu-2)K_1 \vee K_2$.

Conversely, it is straightforward to check that the $L$-spectra of $K_{\frac{\nu}{3}, \frac{\nu}{3}, \frac{\nu}{3}}$, $(K_{\frac{\nu-1}{2}, \frac{\nu-1}{2}})\vee K_1$ and $(\nu-2)K_1 \vee K_2$ are $\{\nu^{(2)}, (\frac{2\nu}{3})^{(\nu-3)}, 0\}$, $\{\nu^{(2)}, (\frac{\nu-1}{2})^{(\nu-3)}, 0\}$ and $\{\nu^{(2)}, 2^{(\nu-3)}, 0\}$, respectively. □

Next we state one of our main results. We determine some classes of graphs for which the second largest eigenvalue of reciprocal distance Laplacian matrix appears in the corresponding spectrum repeated $\nu-3$ times.

Theorem 3.3. Let $\Gamma$ be a connected graph with $\nu \ge 5$ vertices and ${{{\rm{mult}}}}_{RD^L}(\varrho_2(\Gamma)) = \nu-3$. Then

(a) $\varrho_1(\Gamma) = \nu$ with multiplicity $1$ if and only if $\Gamma\cong \overline{K_1 \cup S_{\nu-1}}$ or $\Gamma\cong (K_{\frac{\nu-1}{2}}\cup K_{\frac{\nu-1}{2}})\vee K_1$ when $2|(\nu-1)$, or $\Gamma \cong \frac{\nu}{3} K_1 \vee (K_{\frac{\nu}{3}} \cup K_{\frac{\nu}{3}})$ when $3|\nu$.

(b) $\varrho_1(\Gamma) = \nu$ with multiplicity $2$ if and only if $\Gamma \cong K_{\frac{\nu}{3}, \frac{\nu}{3}, \frac{\nu}{3}}$ when $3|\nu$, or $\Gamma \cong (K_{\frac{\nu-1}{2}, \frac{\nu-1}{2}})\vee K_1$ when $2|(\nu-1)$, or $\Gamma \cong (\nu-2)K_1 \vee K_2$.

Proof. $(a)$ Given that $\varrho_1(\Gamma) = \nu$ is simple and ${{{\rm{mult}}}}_{RD^L}(\varrho_2(\Gamma)) = \nu-3$, we conclude that the $RD^L$-spectrum of $\Gamma$ is equal to $\{\nu, (\varrho_2(\Gamma))^{(\nu-3)}, \varrho_3(\Gamma), 0\}$. As $\nu$ is simple eigenvalue of $RD^L(\Gamma)$, by Lemma 2.6, $\overline{\Gamma}$ has exactly two components. This implies that the diameter of $\Gamma$ is $2$. By Lemma 2.9, we obtain that the $L$-spectrum of $\Gamma$ is equal to $\{\nu, (2\varrho_2(\Gamma)-\nu)^{(\nu-3)}, 2\varrho_3(\Gamma)-\nu, 0\}$. Consequently, according to Lemma 3.1, $\Gamma\cong \overline{K_1 \cup S_{\nu-1}}$ or $\Gamma\cong (K_{\frac{\nu-1}{2}}\cup K_{\frac{\nu-1}{2}})\vee K_1$ when $2|(\nu-1)$ or $\Gamma \cong \frac{\nu}{3} K_1 \vee (K_{\frac{\nu}{3}} \cup K_{\frac{\nu}{3}})$ when $3|\nu$.

$(b)$ Suppose that $\varrho_1(\Gamma) = \nu$ is of multiplicity $2$ and ${{{\rm{mult}}}}_{RD^L}(\varrho_2(\Gamma)) = \nu-3$. Then the $RD^L$-spectrum of $\Gamma$ is equal to $\{\nu^{(2)}, (\varrho_2(\Gamma))^{(\nu-3)}, 0\}$. By Lemma 2.6, $\overline{\Gamma}$ has exactly three components. This implies that the diameter of $\Gamma$ is $2$. According to Lemma 2.9, the $L$-spectrum of $\Gamma$ is equal to $\{\nu^{(2)}, (2\varrho_2(\Gamma)-\nu)^{(\nu-3)}, 0\}$. Thus, by Lemma 3.2, $\Gamma \cong K_{\frac{\nu}{3}, \frac{\nu}{3}, \frac{\nu}{3}}$ if $3|\nu$, or $\Gamma \cong (K_{\frac{\nu-1}{2}, \frac{\nu-1}{2}})\vee K_1$ if $2|(\nu-1)$, or $\Gamma \cong (\nu-2)K_1 \vee K_2$.

Conversely, by Lemmas 2.9 and 3.2, we see that the $RD^L$-spectrum of $K_{\frac{\nu}{3}, \frac{\nu}{3}, \frac{\nu}{3}}$, $(K_{\frac{\nu-1}{2}, \frac{\nu-1}{2}})\vee K_1$ and $(\nu-2)K_1 \vee K_2$ are, respectively, $\{\nu^{(2)}, (\frac{5\nu}{6})^{(\nu-3)}, 0\}$, $\{\nu^{(2)}, (\frac{3\nu-1}{4})^{(\nu-3)}, 0\}$ and $\{\nu^{(2)}, (\frac{\nu+2}{2})^{(\nu-3)}, 0\}$. □

Finally, we completely determine the graphs having $\nu$ as the largest reciprocal distance Laplacian eigenvalue of multiplicity $\nu-3$.

Theorem 3.4. If $\Gamma$ is a connected graph on $\nu \ge 5$ vertices, then $\varrho_1(\Gamma) = \nu$ is of multiplicity $\nu-3$ if and only if $\Gamma \cong K_{3, 1, 1, \ldots, 1}$ or $\Gamma \cong K_{2, 2, 1, 1, \ldots, 1}$ or $\Gamma\cong \overline{(\nu-3)K_1 \cup S_3}$.

Proof. Let $\varrho_1(\Gamma) = \nu$ with ${{{\rm{mult}}}}_{RD^L}(\varrho_1(\Gamma)) = \nu-3$. Then the $RD^L$-spectrum of $\Gamma$ is $\{\nu^{(\nu-3)}, \varrho_2(\Gamma), \varrho_3(\Gamma), 0\}$. We separate two cases:

Case 1. Let $\varrho_2(\Gamma) = \varrho_3(\Gamma)$. Since the eigenvalue $\nu$ is of multiplicity $\nu-3$, $\overline{\Gamma}$ has $\nu-2$ components, by Lemma 2.6. This also implies that the diameter of $\Gamma$ is $2$. Using Lemma 2.9, we obtain that the Laplacian spectrum of $\Gamma$ is equal to $\{\nu^{(\nu-3)}, (2\varrho_2(\Gamma)-\nu)^{(2)}, 0\}$, which further shows that $L$-spectrum of $\overline{\Gamma}$ is equal to $\{(2\nu-2\varrho_2(\Gamma))^{(2)}, 0, \dots, 0\}$. Therefore, every component of $\overline{\Gamma}$ is either an isolated vertex or complete graph of the same order. Furthermore, $\overline{\Gamma}$ has either $\nu-3$ or $\nu-4$ isolated vertices, because $\overline{\Gamma}$ has $\nu-2$ components. Thus, the only two possibilities for $\overline{\Gamma}$ are either $\overline{\Gamma}\cong (\nu-3)K_1 \cup K_3$ or $\overline{\Gamma} \cong (\nu-4)K_1\cup K_2 \cup K_2$, and therefore $\Gamma\cong K_{3, 1, 1, \dots, 1}$ or $\Gamma\cong K_{2, 2, 1, 1, \dots, 1}.$

Case 2. Let $\varrho_2(\Gamma) \ne\varrho_3(\Gamma)$. By following the same arguments as in the above case, we see that the Laplacian spectrum of $\overline{\Gamma}$ is equal to $\{2\nu-2\varrho_3(\Gamma), 2\nu-2\varrho_2(\Gamma), 0, \dots, 0\}$. Since $\varrho_2(\Gamma) \ne\varrho_3(\Gamma)$ and $K_\nu$ is determined by its Laplacian spectrum, then the only possibility for $\overline{\Gamma}$ is that $\overline{\Gamma}\cong (\nu-3)K_1 \cup S_3$. Hence, $\Gamma \cong \overline{(\nu-3)K_1 \cup S_3}$.

Conversely, we see that the $RD^L-$spectrum of $K_{3, 1, 1, \dots, 1}$, $K_{2, 2, 1, 1, \dots, 1}$ and $\overline{(\nu-3)K_1 \cup S_3}$ are, respectively, $\{\nu^{(\nu-3)}, (\frac{2\nu-3}{2})^{(2)}, 0\}$, $\{\nu^{(\nu-3)}, (\nu-1)^{(2)}, 0\}$ and $\{\nu^{(\nu-3)}, \frac{2\nu-1}{2}, \frac{2\nu-3}{2}, 0\}$. □

4.   Conclusions

The problem to determine graphs with small numbers of distinct eigenvalues has been considered in the literature for different types of spectra. Recently, it has been extended to signed graphs (see ^[16] and references therein). No matter what kind of spectra is considered, most graphs with a few distinct eigenvalues show some type of regularity. The results of this paper can be seen as contributions to this topic with respect to the reciprocal distance Laplacian matrix. As expected, the obtained graphs are either regular or close to being regular.

Use of AI tools declaration

The authors declare that they have not used Artificial Intelligence (AI) tools in the creation of this article.

Conflict of interest

The authors declare no conflicts of interests.