On graphs with distance Laplacian eigenvalues of multiplicity n−4

Abstract

Let G be a connected simple graph with n vertices. The distance Laplacian matrix $D^L(G)$ is defined as $D^L(G)=\mathit{Diag}(Tr)-D(G)$, where $\mathit{Diag}(Tr)$ is the diagonal matrix of vertex transmissions and $D(G)$ is the distance matrix of G. The eigenvalues of $D^L(G)$ are the distance Laplacian eigenvalues of G and are denoted by ${\partial }_1^L(G)\ge {\partial }_2^L(G)\ge \cdots \ge {\partial }_n^L(G)$. The largest eigenvalue ${\partial }_1^L(G)$ is called the distance Laplacian spectral radius. Lu et al. (2017), Fernandes et al. (2018), and Ma et al. (2018) completely characterized the graphs having some distance Laplacian eigenvalue of multiplicity $n-3$. In this paper, we characterize the graphs having distance Laplacian spectral radius of multiplicity $n-4$ together with one of the distance Laplacian eigenvalues as n of multiplicity either 3 or 2. Further, we completely determine the graphs for which the distance Laplacian eigenvalue n is of multiplicity $n-4$.

KEYWORDS:

• Distance matrix
• distance Laplacian matrix
• spectral radius
• multiplicity of distance Laplacian eigenvalue

AMS SUBJECT CLASSIFICATION:

• 05C50
• 05C12
• 15A18

1 Introduction

Throughout this paper, we consider simple and connected graphs. A simple connected graph $G=(V,E)$ consists of the vertex set $V(G)=\{v_1,v_2,\dots ,v_n\}$ and the edge set $E(G)$. The order and size of G are $|V(G)|=n$ and $|E(G)|=m$, respectively. The degree of a vertex v, denoted by $d_G(v)$ (we simply write by $d_v$) is the number of edges incident on the vertex v. For other standard definitions, we refer to [4, 9]. The adjacency matrix $A=(a_{ij})$ of G is an $n\times n$ matrix whose $(i,j)$-entry is equal to 1, if $v_i$ is adjacent to $v_j$ and equal to 0, otherwise. Let $\mathrm{Deg}(G)=\text{diag}(d_G(v_1),d_G(v_2),\dots ,d_G(v_n))$ be the diagonal matrix of vertex degrees $d_G(v_i)$, $i=1,2,\dots ,n$. The positive semi-definite matrix $L(G)=\mathrm{Deg}(G)-A(G)$ is the Laplacian matrix of G. The eigenvalues of $L(G)$ are called the Laplacian eigenvalues of G. The Laplacian eigenvalues are denoted by ${\mu }_1(G),{\mu }_2(G),\dots ,{\mu }_n(G)$ and are ordered as ${\mu }_1(G)\ge {\mu }_2(G)\ge \dots \ge {\mu }_n(G)$. The sequence of the Laplacian eigenvalues is called the Laplacian spectrum (briefly L-spectrum) of G. In G, the distance between two vertices $u,v\in V(G),$ denoted by $d_{uv}=d(u,v)$, is defined as the length of a shortest path between u and v. The diameter of G denoted by $\mathit{diam}(G)$ is ${\max }_{u,v\in G}d(u,v)$, that is, the length of a longest path among the distance between every two vertices of G. The distance matrix of G is defined as $D(G)={(d_{uv})}_{u,v\in V(G)}$. The transmission $T{r}_G(v)$ of a vertex v is the sum of the distances from v to all other vertices in G, that is, $T{r}_G(v)=\sum _{u\in V(G)}{d}_{uv}.$ For any vertex $v_i\in V(G)$, the transmission $T{r}_G(v_i)=T{r}_i$ is also called the transmission degree.

Let $\mathit{Diag}(Tr)=\mathit{Diag}(T{r}_1,T{r}_2,\dots ,T{r}_n)$ be the diagonal matrix of vertex transmissions of G. Aouchiche and Hansen [1] defined the distance Laplacian matrix of G as $D^L(G)=\mathit{Diag}(Tr)-D(G)$ (or simply $D^L$). The eigenvalues of $D^L$ are called the distance Laplacian eigenvalues of G. Clearly, $D^L(G)$ is a real symmetric positive semi-definite matrix so that its eigenvalues can be ordered as ${\partial }_1^L(G)\ge {\partial }_2^L(G)\ge \dots \ge {\partial }_{n-1}^L(G)>{\partial }_n^L(G)=0$. We write ${\partial }_i^L$ in place of ${\partial }_i^L(G)$ if the graph G is clear from the context. If G has k distinct distance Laplacian eigenvalues say ${\partial }_1^L(G),{\partial }_2^L(G),\dots ,{\partial }_k^L(G)$ with corresponding multiplicities as $n_1,n_2,\dots ,n_k$, we write the distance Laplacian spectrum (briefly $D^L$-spectrum) of G as $({\partial }_1^L{}^{(n_1)},{\partial }_2^L{}^{(n_2)},\dots ,{\partial }_k^L{}^{(n_k)})$. The largest eigenvalue ${\partial }_1^L(G)$ is called the distance Laplacian spectral radius of G. We denote the multiplicity of the distance Laplacian eigenvalue ${\partial }_i^L(G)$ by $m({\partial }_i^L(G))$. More work on distance Laplacian eigenvalues can be seen in [10–12].

As usual, $K_n$, $C_n$, $P_n$ and $S_n$ are respectively, the complete graph, the cycle, the path and the star all on n vertices. A clique of a graph G is an induced subgraph of G that is complete. A kite $K{i}_{n,\omega }$ is the graph obtained from a clique $K_{\omega }$ and a path $P_{n-\omega }$ by adding an edge between an endpoint of the path and a vertex from the clique. $S{K}_{n,\alpha }$ denotes the complete split graph, that is, the complement of the disjoint union of a clique $K_{\alpha }$ and $n-\alpha$ isolated vertices. A complete multipartite graph is denoted by $K_{t_1,t_2,\dots ,t_l}$, where l is the number of partite classes and $t_1+t_2+\dots +t_l=n$. Throughout, we assume that $t_1\ge t_2\ge \dots \ge t_l$. If $l=2$, it is a complete bipartite graph. Usually we will choose the complete bipartite graph $K_{n-r, r}$, for $1\le r\le \frac{n}{2}$. If G is a noncomplete graph on $n\ge 2$ vertices, then $G+e$ is the graph obtained from G by adding an edge e between any two non-adjacent vertices. Further, if f is an edge of G, then $G-f$ is the graph obtained from G by deleting the edge f. The join of two graphs $G_1$ and $G_2$, denoted by $G_1\vee G_2$, is a graph obtained from $G_1$ and $G_2$ by joining each vertex of $G_1$ to all vertices of $G_2$.

Fernandes et al. [6] and Lu et al. [7] determined the graphs having distance Laplacian spectral radius of multiplicity $n-3$. Further, the investigation of the graphs having some distance Laplacian eigenvalue of multiplicity $n-3$ was done by Ma et al. in [8].

The rest of the paper is organized as follows. In Section 2, we state some preliminary results, which will be used to prove our main results. In Section 3, we characterize the graphs having distance Laplacian spectral radius of multiplicity $n-4$ together with one of the distance Laplacian eigenvalues as n of multiplicity either 3 or 2. In Section 4, we completely determine the graphs for which the distance Laplacian eigenvalue n is of multiplicity $n-4$.

2 Preliminaries

Lemma 2.1 .

[4] Let G be a graph on n vertices with Laplacian eigenvalues ${\mu }_1(G)\ge {\mu }_2(G)\ge \dots \ge {\mu }_n(G)=0$. Then the Laplacian eigenvalues of $\overline{G}$ are given by ${\mu }_i(\overline{G})=n-{\mu }_{n-i}(G)$ for $i=1,\dots ,n-1$ and ${\mu }_n(\overline{G})=0$.

Lemma 2.2.

[1] Let G be a connected graph on n vertices with $\mathit{diam}(G)\le 2$. Let ${\mu }_1(G)\ge {\mu }_2(G)\ge \dots \ge {\mu }_n(G)=0$ be the Laplacian eigenvalues of G. Then the distance Laplacian eigenvalues of G is $2n-{\mu }_{n-1}(G)\ge 2n-{\mu }_{n-2}(G)\ge \dots \ge 2n-{\mu }_1(G)>{\partial }_n^L(G)=0$. Moreover, for every $i\in \{1,2,\dots ,n-1\}$ the eigenspaces corresponding to ${\mu }_i(G)$ and $2n-{\mu }_i(G)$ are the same.

Lemma 2.3.

[1] Let G be a connected graph on n vertices. Then ${\partial }_{n-1}^L(G)\ge n$ with equality holding if and only if $\overline{G}$ is disconnected. Furthermore, the multiplicity of n as a distance Laplacian eigenvalue is one less than the number of connected components of $\overline{G}$.

Lemma 2.4.

[3] Let $t_1,t_2,\dots ,t_k$ and n be integers such that $t_1+t_2+\cdots +t_k=n$ and $t_i\ge 1$ for $i=1,2,\dots ,k$. Let $p=\left|\right\{i:t_i\ge 2\left\}\right|$. The distance Laplacian spectrum of the complete $k-\mathit{partite}$ graph $K_{t_1,t_2,\dots ,t_k}$ is $({(n+t_1)}^{(t_1-1)},\dots ,{(n+t_p)}^{(t_p-1)},n^{(k-1)},0)$.

Lemma 2.5.

[6] Let G be a connected graph of order $n\ge 4$. Then, $G\cong K_n-e$ if and only if the $L-\mathit{spectrum}$ of G is $({\mu }_1^{(n-2)},{\mu }_2,0)$, with ${\mu }_1>{\mu }_2>0$.

Let $v\in V(G)$. By $N(v)$ we mean the set of all vertices which are adjacent to v in G.

Lemma 2.6.

[2] Let G be a graph with n vertices. If $K=\{v_1,v_2,\dots ,v_p\}$ is a clique of G such that $N(v_i)-K=N(v_j)-K$ for all $i,j\in \{1,2,\dots ,p\}$, then $\partial =Tr(v_i)=Tr(v_j)$ for all $i,j\in \{1,2,\dots ,p\}$ and $\partial +1$ is an eigenvalue of $D^L(G)$ with multiplicity at least $p-1$.

Lemma 2.7.

[2] Let G be a graph with n vertices. If $K=\{v_1,v_2,\dots ,v_p\}$ is an independent set of G such that $N(v_i)=N(v_j)$ for all $i,j\in \{1,2,\dots ,p\}$, then $\partial =Tr(v_i)=Tr(v_j)$ for all $i,j\in \{1,2,\dots ,p\}$ and $\partial +2$ is an eigenvalue of $D^L(G)$ with multiplicity at least $p-1$.

3 Multiplicity of distance Laplacian spectral radius

The following fact will be used frequently in the sequel.

Fact 1 .

A complete graph and a complete graph minus an edge are determined by their L-spectrum which is given by $({(n)}^{n-1},0)$ and $({(n)}^{n-2},n-2,0)$, respectively.

Given a connected graph G with order $n\ge 5$, we observe that one of the following possibilities can occur.

1. $m({\partial }_1^L(G))=n-4$ and ${\partial }_{n-1}^L(G)=n$ with multiplicity 3,

2. $m({\partial }_1^L(G))=n-4$ and ${\partial }_{n-1}^L(G)=n$ with multiplicity 2,

3. $m({\partial }_1^L(G))=n-4$ and ${\partial }_{n-1}^L(G)=n$ with multiplicity 1,

4. $m({\partial }_1^L(G))=n-4$ and ${\partial }_{n-1}^L(G)\ne n$.

In the following theorem, we address Cases (a) and (b), that is, we determine those graphs having the distance Laplacian spectral radius of multiplicity $n-4$ together with one of the distance Laplacian eigenvalue n with multiplicity 3 or 2.

Theorem 3.1.

Let G be a connected graph with order $n\ge 6$. Then

1. $m({\partial }_1^L(G))=n-4$ and ${\partial }_{n-1}^L(G)=n$ with multiplicity 3 if and only if $G\cong K_{\frac{n}{4},\frac{n}{4},\frac{n}{4},\frac{n}{4}}$ if $n\equiv 0(\mathit{mod} 4)$, or $G\cong K_{\frac{n-1}{3},\frac{n-1}{3},\frac{n-1}{3},1}$ if $n\equiv 1(\mathit{mod} 3)$, or $G\cong K_{\frac{n-2}{2},\frac{n-2}{2},1,1}$ if $n\equiv 2(\mathit{mod} 2)$ or $G\cong S{K}_{n,n-3}$.

2. $m({\partial }_1^L(G))=n-4$ and ${\partial }_{n-1}^L(G)=n$ with multiplicity 2 if and only if $G\cong S{K}_{n,n-2}+e$ or $G\cong K_{n,n-3}-e$ or $G\cong K_{p,p,1}+e$; $p=\frac{n-1}{2}\ge 3$ or $G\cong K_{p,p,2}$; $p=\frac{n-2}{2}\ge 3$ or $G\cong K_{p,p,p}+e$; $p=\frac{n}{3}\ge 3$.

Proof.

1. Using Lemma 2.3, we note that $\overline{G}$ is disconnected having 4 components and $\mathit{diam}(G)=2$. Applying Lemmas 2.1 and 2.2, the L-spectrum of $\overline{G}$ is $({({\partial }_1^L(G)-n)}^{(n-4)},0,0,0,0)$ so that every component of $\overline{G}$ is either an isolated vertex or complete graphs with same order. Thus, $\overline{G}$ contains less or equal to three isolated vertices, that is, $\overline{G}\cong K_{\frac{n}{4}}\cup K_{\frac{n}{4}}\cup K_{\frac{n}{4}}\cup K_{\frac{n}{4}}$ if $n\equiv 0(\mathit{mod} 4)$, or $\overline{G}\cong K_{\frac{n-1}{3}}\cup K_{\frac{n-1}{3}}\cup K_{\frac{n-1}{3}}\cup K_1$ if $n-1\equiv 0(\mathit{mod} 3)$, or $\overline{G}\cong K_{\frac{n-2}{2}}\cup K_{\frac{n-2}{2}}\cup K_1\cup K_1$ if $n-2\equiv 0(\mathit{mod} 2)$ or $\overline{G}\cong K_{n-3}\cup K_1\cup K_1\cup K_1$. Hence, $G\cong K_{\frac{n}{4},\frac{n}{4},\frac{n}{4},\frac{n}{4}}$, or $G\cong K_{\frac{n-1}{3},\frac{n-1}{3},\frac{n-1}{3},1}$, or $G\cong K_{\frac{n-2}{2},\frac{n-2}{2},1,1}$ according as $n\equiv 0(\mathit{mod} 4)$, or $n-1\equiv 0(\mathit{mod} 3)$, or $n-2\equiv 0(\mathit{mod} 2)$, or simply $G\cong S{K}_{n,n-3}$.

   Conversely, by the help of Lemma 2.4, it is easy to see that the $D^L$-spectrum of $G\cong K_{\frac{n}{4},\frac{n}{4},\frac{n}{4},\frac{n}{4}}$, $G\cong K_{\frac{n-1}{3},\frac{n-1}{3},\frac{n-1}{3},1}$, $G\cong K_{\frac{n-2}{2},\frac{n-2}{2},1,1}$ and $G\cong S{K}_{n,n-3}$ are $({\frac{5n}{4}}^{(n-4)},n^{(3)},0)$, $({\frac{4n-1}{3}}^{(n-4)},n^{(3)},0)$, $({\frac{3n-2}{2}}^{(n-4)},n^{(3)},0)$ and $({(2n-3)}^{(n-4)},n^{(3)},0)$, respectively.

2. For the graph G, let n be a distance Laplacian eigenvalue with multiplicity 2. Using Lemma 2.3, we see that $\overline{G}$ has three components, say $Q, R$ and S, that is, $\overline{G}\cong Q\cup R\cup S$. This also shows that $\mathit{diam}(G)=2$. Assume that $\left|Q\right|\ge \left|R\right|\ge \left|S\right|$. By application of Lemmas 2.1 and 2.2, we observe that the L-spectrum of $\overline{G}$ is $({({\partial }_1^L(G)-n)}^{(n-4)},{\partial }_{n-3}^L(G)-n,0,0,0)$. We have the following possibilities.

Figure 1: All connected graphs on four vertices.

• Case 1. Let $\left|R\right|=\left|S\right|=1$. Then L-spectrum of Q is $({({\partial }_1^L(G)-n)}^{(n-4)},{\partial }_{n-3}^L(G)-n,0)$. So, by Lemma 2.5, Q is isomorphic to $K_{n-4}\vee \overline{K_2}$. Therefore, $\overline{G}\cong (K_{n-4}\vee \overline{K_2})\cup K_1\cup K_1$ which shows that $G\cong S{K}_{n,n-2}+e$.

• Case 2. Let $\left|R\right|=2$, $\left|S\right|=1$. In order to find the L-spectrum of $\overline{G}$, we have to consider the following two subcases.

• Subcase 2.1. Let the L-spectrum of R be $({\partial }_{n-3}^L(G)-n,0)$. Therefore, the L-spectrum of Q is $({({\partial }_1^L(G)-n)}^{(n-4)},0)$. Using Fact 1, from the above argument, it follows that ${\partial }_{n-3}^L(G)-n=2$ and ${\partial }_1^L(G)-n=n-3$. Thus, $R\cong K_2$ and $Q\cong K_{n-3}$. From this, we obtain $\overline{G}\cong K_{n-3}\cup K_2\cup K_1$ or $G\cong S{K}_{n,n-3}-e$ where e is an edge connecting two vertices of degree $n-3$.

• Subcase 2.2. Let L-spectrum of R be $({\partial }_1^L(G)-n,0)$. Therefore, the L-spectrum of Q is $({\partial }_1^L(G)-n^{(n-5)},{\partial }_{n-3}^L(G)-n,0)$. Thus, $R\cong K_2$. Using Lemma 2.5, we have $Q\cong K_{n-5}\vee \overline{K_2}$. This shows that ${\partial }_1^L(G)-n=2$. Also, ${\partial }_1^L(G)-n=n-3$. Combining these two, we get $n=5$. This further implies that ${\partial }_1^L(G)-n={\partial }_{n-3}^L(G)-n$ or ${\partial }_1^L(G)={\partial }_{n-3}^L(G)$, a contradiction.

• Case 3. Let $\left|S\right|=1$, $\left|R\right|=p\ge 3$. To find the L-spectrum of $\overline{G}$, we see that either L-spectrum of R is $({({\partial }_1^L(G)-n)}^{(p-1)},0)$ and L-spectrum of Q is $({({\partial }_1^L(G)-n)}^{(n-p-3)},{\partial }_{n-3}^L(G)-n,0)$, or L-spectrum of R is $({({\partial }_1^L(G)-n)}^{(p-2)},{\partial }_{n-3}^L(G)-n,0)$ and L-spectrum of Q is $({({\partial }_1^L(G)-n)}^{(n-p-2)},0)$. Using Fact 1, we get $n=2p+1$, $\overline{G}\cong K_P\cup K_{p-2}\vee \overline{K_2}\cup K_1$ in both the cases. Hence $G\cong K_{p,p,1}+e$, $p=\frac{n-1}{2}\ge 3$.

• Case 4. Let $\left|S\right|=2$, $\left|R\right|=p\ge 2$. We have to consider the following subcases.

• Subcase 4.1 Let L-spectrum of S be $({\partial }_1^L(G)-n,0)$. Then we see that the L-spectrum of R can be $({({\partial }_1^L(G)-n)}^{(p-1)},0)$ or $({({\partial }_1^L(G)-n)}^{(p-2)},{\partial }_{n-3}^L(G)-n,0)$. Again, using Fact 1, we get ${\partial }_1^L(G)={\partial }_{n-3}^L(G)$ in both the cases, which is a contradiction.

• Subcase 4.2 Let L-spectrum of S be $({\partial }_{n-3}^L(G)-n,0)$. For the L-spectrum of $\overline{G}$ and Fact 1, we observe that the L-spectrum of R and S is same and is given by $({({\partial }_1^L(G)-n)}^{(p-1)},0)$. Clearly, $p\ge 3$, otherwise we have ${\partial }_1^L(G)={\partial }_{n-3}^L(G)$, which is a contradiction. Hence, in this case $\overline{G}\cong K_P\cup K_p\cup K_2$ or $G\cong K_{p,p,2}$, $p=\frac{n-2}{2}\ge 3$.

• Case 5. Let $p=\left|S\right|\ge 3$. From the L-spectrum of $\overline{G}$ and $\left|Q\right|\ge \left|R\right|\ge \left|S\right|=p\ge 3$, we see that ${\partial }_1^L(G)-n$ is contained in the L-spectrum of all of Q, R and S. Again, by Fact 1, we easily get $\overline{G}\cong K_p\cup K_p\cup K_{p-2}\vee \overline{K_2}$. Hence $G\cong K_{p,p,p}+e$, $p=\frac{n}{3}\ge 3$.

For the converse, taking Lemmas 2.3, 2.4, 2.6, 2.7 and the fact that the trace of a matrix equals to the sum of all its eigenvalues into consideration, it can be easily seen that the $D^L$-spectrum of $G\cong S{K}_{n,n-2}+e$, $G\cong S{K}_{n,n-3}-e$ where e is an edge connecting two vertices of degree $n-3$, $G\cong K_{p,p,1}+e$, $G\cong K_{p,p,2}$ and $G\cong K_{p,p,p}+e$ are $({(2n-2)}^{(n-4)},2n-4,n^{(2)},0)$, $({(2n-3)}^{(n-4)},n+2,n^{(2)},0)$, $({(\frac{3n-1}{2})}^{(n-4)},\frac{3n-5}{2},n^{(2)},0)$, $({(\frac{3n-2}{2})}^{(n-4)},n+2,n^{(2)},0)$ and $({(\frac{4n}{3})}^{(n-4)},\frac{4n-6}{3},n^{(2)},0)$, respectively. ▪

To completely characterize the connected graphs with $n\ge 5$ vertices, where distance Laplacian spectral radius has multiplicity $n-4$, we need to find the solution for the Cases (c) and (d), which are left as open problems.

4 Multiplicity of any distance Laplacian eigenvalue

To prove the next theorem, we need the following lemma.

Lemma 4.1.

[5] Let G be a graph on $n\ge 3$ vertices whose distinct Laplacian eigenvalues are $0<\alpha <\beta$. The multiplicity of $\alpha$ is $n-2$ if and only if G is one of the graphs $K_{\frac{n}{2},\frac{n}{2}}$ or $S_n$.

Theorem 4.2.

Let G be a connected graph of order $n\ge 5$ having ${\partial }_1^L(G)$ of multiplicity one. Then ${\partial }_{n-1}^L(G)=n$ with multiplicity 2 and $m({\partial }_{n-3}^L(G))=n-4$ if and only if $G\cong S_3\vee (K_2\cup K_2)$ for $n=7$ or $G\cong (K_{n-1}\cup K_1)+2e$ or $G\cong K_2\vee (K_{\frac{n-2}{2}}\cup K_{\frac{n-2}{2}})$ or $G\cong K_{\frac{n}{4},\frac{n}{4}}\vee (K_{\frac{n}{4}}\cup K_{\frac{n}{4}})$.

Proof.

Let n be a distance Laplacian eigenvalue with multiplicity 2. Using Lemma 2.3, we observe that $\overline{G}$ has 3 components and $\overline{G}$. Let $\overline{G}\cong F\cup T\cup S$, where $\left|F\right|\ge \left|T\right|\ge \left|S\right|$. Using Lemmas 2.1 and 2.2, we note that the L-spectrum of $\overline{G}$ is $({\partial }_1^L(G)-n,{({\partial }_{n-3}^L(G)-n)}^{(n-4)},0,0,0)$. We have the following cases to consider.

• Case 1. If $\left|S\right|=\left|T\right|=1$, then L-spectrum of F is $({\partial }_1^L(G)-n,{({\partial }_{n-3}^L(G)-n)}^{(n-4)},0)$. Applying Lemma 4.1, it is easy to see that either $F\cong S_{n-2}$ or $F\cong K_{\frac{n-2}{2},\frac{n-2}{2}}$. Since S and T are both isomorphic to $K_1$, therefore $\overline{G}\cong S_{n-2}\cup K_1\cup K_1$ or $\overline{G}\cong K_{\frac{n-2}{2},\frac{n-2}{2}}\cup K_1\cup K_1$ . This shows that G is one of the graphs $(K_{n-1}\cup K_1)+2e$ and $K_2\vee (K_{\frac{n-2}{2}}\cup K_{\frac{n-2}{2}})$.

• Case 2. If $\left|S\right|=1$ and $\left|T\right|=2$, then L-spectrum of T is either $({\partial }_1^L(G)-n,0)$ or $({\partial }_{n-3}^L(G)-n,0)$. The following two subcases arise.

• Subcase 2.1. Let the L-spectrum of T be $({\partial }_1^L(G)-n,0)$. So $T\cong K_2$ and the L-spectrum of F is $({({\partial }_{n-3}^L(G)-n)}^{(n-4)},0)$. Using Fact 1, from the above argument, we observe that ${\partial }_1^L(G)-n=2$ and ${\partial }_{n-3}^L(G)-n=n-3\ge 2$. Therefore, ${\partial }_{n-3}^L(G)\ge {\partial }_1^L(G)$, a contradiction.

• Subcase 2.2. Let L-spectrum of T be $({\partial }_{n-3}^L(G)-n,0)$. Therefore, L-spectrum of F is $({\partial }_1^L(G)-n,{({\partial }_{n-3}^L(G)-n)}^{(n-5)},0)$. If $n\ge 8$, then using Lemma 4.1 and Fact 1, we get ${\partial }_{n-3}^L(G)-n=2$ from L-spectrum of T and ${\partial }_{n-3}^L(G)-n=1$ or ${\partial }_{n-3}^L(G)-n=\frac{n-3}{2}$ from L-spectrum of F, which is a contradiction. If $n=5$, we have ${\partial }_{n-3}^L(G)={\partial }_1^L(G)$, a contradiction. If $n=6$, using Lemma 4.1, ${\partial }_{n-3}^L(G)-n=1$ from L-spectrum of F which is a again a contradiction. If $n=7$, using the same arguments as above, F is one of the graphs $S_4$ or $K_{2,2}$. $F\cong S_4$ gives a contradiction while as $F\cong K_{2,2}$ shows that $G\cong S_3\vee (K_2\cup K_2)$.

• Case 3. If $\left|S\right|=1$ and $k=\left|T\right|\ge 3$, then from the L-spectrum of $\overline{G}$, we see that either F contains three distinct Laplacian eigenvalues or T contains three distinct Laplacian eigenvalues. It suffices to consider one of the two cases. Without loss of generality, assume that T contains three distinct Laplacian eigenvalues. So the Laplacian spectrum of F is $({({\partial }_{n-3}^L(G)-n)}^{(n-k-2)},0)$ and the Laplacian spectrum of T is $({\partial }_1^L(G)-n,{({\partial }_{n-3}^L(G)-n)}^{(k-2)},0)$. Applying Lemma 4.1 and Fact 1, we get ${\partial }_{n-3}^L(G)-n=1$ or $\frac{k}{2}$ from L-spectrum of T and ${\partial }_{n-3}^L(G)-n=n-k-1$ from L-spectrum of F, a contradiction.

• Case 4. If $\left|S\right|\ge 2$, then we observe from the L-spectrum of $\overline{G}$ that only one component among the $F, T$ and S contains ${\partial }_1^L(G)-n$ as a Laplacian eigenvalue. The L-spectrum of the remaining two is the same. Note that for $n=6$, ${\partial }_{n-3}^L(G)={\partial }_1^L(G)$, which is a contradiction. Let b be the cardinality of the component containing ${\partial }_1^L(G)-n$ as Laplacian eigenvalue. For $n\ge 7$, if $b=2$, we observe that ${\partial }_1^L(G)-n=2$ from the L-spectrum of the component containing ${\partial }_1^L(G)-n$ as Laplacian eigenvalue and ${\partial }_{n-3}^L(G)-n\ge 2$ from the spectrum of remaining two components, a contradiction. Let $b\ge 3$, using Lemma 4.1, ${\partial }_{n-3}^L(G)-n=1$ or ${\partial }_{n-3}^L(G)-n=\frac{b}{2}$. ${\partial }_{n-3}^L(G)-n=1$ gives a contradiction and ${\partial }_{n-3}^L(G)-n=\frac{b}{2}$ shows that $n=2b$ and $\overline{G}\cong K_{\frac{b}{2},\frac{b}{2}}\cup K_{\frac{b}{2}}\cup K_{\frac{b}{2}}$ so that $G\cong K_{\frac{n}{4},\frac{n}{4}}\vee (K_{\frac{n}{4}}\cup K_{\frac{n}{4}})$.

Conversely, noting that all the graphs in the statement of the theorem are of diameter two and using Lemmas 2.1 and 2.2, it is easy to see that the $D^L$-spectrum of $G\cong S_3\vee (K_2\cup K_2)$, $G\cong K_n-(n-3)e$, $G\cong K_2\vee (K_{\frac{n-2}{2}}\cup K_{\frac{n-2}{2}})$ and $G\cong K_{\frac{n}{4},\frac{n}{4}}\vee (K_{\frac{n}{4}}\cup K_{\frac{n}{4}})$ are $(11,9^{(3)},7^{(2)},0)$, $(2n-2,{(n+1)}^{(n-4)},n^{(2)},0)$, $(2n-2,{(\frac{3n-2}{2})}^{(n-4)},n^{(2)},0)$ and $(\frac{3n}{2},{(\frac{5n}{4})}^{(n-4)},n^{(2)},0)$, respectively. ▪

Now, we will completely determine the graphs for which n is a distance Laplacian eigenvalue of multiplicity $n-4$.

Theorem 4.3.

Let G be a connected graph with order $n\ge 5$. Then

1. $m({\partial }_1^L(G))=3$ and ${\partial }_{n-1}^L(G)=n$ with multiplicity $n-4$ if and only if $G\cong K_{4,1,\dots ,1}$ or $G\cong K_{2,2,2,1,\dots ,1}$.

2. $m({\partial }_1^L(G))=2$ and ${\partial }_{n-1}^L(G)=n$ with multiplicity $n-4$ if and only if $G\cong S{K}_{n,4}+e$ or $G\cong K_{3,2,1,\dots ,1}$.

3. $m({\partial }_1^L(G))=1$ and ${\partial }_{n-1}^L(G)=n$ with multiplicity $n-4$ if and only if G is isomorphic to any one of the following graphs, $\overline{S_4\cup (n¯4)K_1}$ or $\overline{C_4\cup (n¯4)K_1}$ or $\overline{P_4\cup (n¯4)K_1}$ or $\overline{K{i}_{4,3}\cup (n¯4)K_1}$ or $\overline{S_3\cup K_2\cup (n¯5)K_1}$.

Proof.

1. Let n be a distance Laplacian eigenvalue of G with multiplicity $n-4$ and $m({\partial }_1^L(G))=3$. Using Lemma 2.3, $\overline{G}$ is disconnected with $n-3$ components and $\mathit{diam}(G)=2$. Applying Lemmas 2.1 and 2.2, the L-spectrum of $\overline{G}$ is $({({\partial }_1^L(G)-n)}^3,0,0,\dots ,0)$. From the L-spectrum of $\overline{G}$, we observe that $\overline{G}$ has exactly one non-zero Laplacian eigenvalue. So all the components of $\overline{G}$ are either isolated vertices or complete graphs of same order. Therefore, $\overline{G}\cong K_4\cup (n-4)K_1$ or $\overline{G}\cong K_2\cup K_2\cup K_2\cup (n-6)K_1$. This further implies that $G\cong K_{4,1,\dots ,1}$ or $G\cong K_{2,2,2,1,\dots ,1}$.

   Conversely, by using Lemma 2.4, we see that the $D^L$-spectrum of $S{K}_{n,4}$ and $K_{2,2,2,1,\dots ,1}$ are respectively, $({(n+4)}^3,n^{(n-4)},0)$ and $({(n+2)}^3,n^{(n-4)},0)$.

2. Now, let n be a distance Laplacian eigenvalue of G with multiplicity $n-4$ and $m({\partial }_1^L(G))=2$. So by using the same argument as in (a), we observe that $\overline{G}$ is disconnected with $n-3$ components, $\mathit{diam}(G)=2$ and the L-spectrum of $\overline{G}$ is $({({\partial }_1^L(G)-n)}^2,{\partial }_3^L(G)-n,0,\dots ,0)$. Let $\overline{G}\cong G_1\cup G_2\cup \dots \cup G_{n-3}$, where $G_i$, $i=1,2,\dots ,n-3$, are the components of $\overline{G}$. Clearly, either one or two or at most three components of $\overline{G}$ can contain all the non-zero Laplacian eigenvalues. So we have the following cases to consider.

   • Case 1. Only one component contains all the non-zero Laplacian eigenvalues of $\overline{G}$. Without loss of generality, let $G_1$ contain all the non-zero Laplacian eigenvalues of $\overline{G}$. So the L-spectrum of $G_1$ is $({({\partial }_1^L(G)-n)}^2,{\partial }_3^L(G)-n,0)$. Note that there are only six connected graphs of order 4 as shown in Figure 1. By Fact 1, only one graph $(K_4-e)$ has Laplacian spectral radius of multiplicity 2. Hence in this case $\overline{G}\cong (K_4-e)\cup (n-4)K_1$, so that $G\cong S{K}_{n,4}+e$.

   • Case 2. Now, let two components contain all the non-zero Laplacian eigenvalues of $\overline{G}$. Without loss of generality, let $G_1$ and $G_2$ contain all the non-zero Laplacian eigenvalues of $\overline{G}$. Also, assume that $G_1$ contains two out of three non-zero Laplacian eigenvalues and the remaining one is contained in $G_2$. Now, consider the following subcases.

     Subcase 2.1. First, let the L-spectrum of $G_1$ be $({({\partial }_1^L(G)-n)}^2,0)$ and L-spectrum of $G_2$ be $({\partial }_3^L(G)-n,0)$. Therefore, $G_1\cong K_3$ and $G_2\cong K_2$ which further implies that $\overline{G}\cong K_3\cup K_2\cup (n-5)K_1$. Hence, $G\cong K_{3,2,1,\dots ,1}$ in this case.

     Subcase 2.2. Let the L-spectrum of $G_1$ be $({\partial }_1^L(G)-n,{\partial }_3^L(G)-n,0)$ and L-spectrum of $G_2$ be $({\partial }_1^L(G)-n,0)$. Using Lemma 4.1 and Fact 1, from L-spectrum of $G_1$, we get ${\partial }_1^L(G)-n=3$, and from L-spectrum of $G_2$ we get ${\partial }_1^L(G)-n=2$. Clearly, this is a contradiction.

   • Case 3. Let three components contain all the non-zero Laplacian eigenvalues of $\overline{G}$. Suppose that $G_1$, $G_2$ and $G_3$ be those components. Without loss of generality, let their spectrum be $({\partial }_1^L(G)-n,0)$, $({\partial }_1^L(G)-n,0)$ and $({\partial }_3^L(G)-n,0)$. Using Fact 1, we get ${\partial }_1^L(G)={\partial }_3^L(G)$, which is a contradiction.

     Conversely, using Lemmas 2.6 and 2.7 and the fact that the trace of a matrix equals to the sum of all its eigenvalues, we see that that $D^L$-spectrum of $S{K}_{n,4}+e$ is $({(n+4)}^2,n+2,n^{(n-4)},0)$. From Lemma 2.4, $D^L$-spectrum of $K_{3,2,1,\dots ,1}$ is $({(n+3)}^2,n+2,n^{(n-4)},0)$.

3. Using the same arguments as in part (a) and (b), we observe that the L-spectrum of $\overline{G}$ is $({\partial }_1^L(G)-n,{\partial }_2^L(G)-n,{\partial }_3^L(G)-n,0,\dots ,0)$ with $n-3$ components and $\mathit{diam}(G)=2$. We have the following two cases to consider.

   • Case 4. Let ${\partial }_2^L(G)={\partial }_3^L(G)$. Now, if only one component, say $G_1$, of $\overline{G}$ contains all its non-zero Laplacian eigenvalues, then clearly L-spectrum of $G_1$ is given by $({\partial }_1^L(G)-n,{({\partial }_2^L(G)-n)}^{(}2),0)$. Among all the six connected graphs on four vertices as shown in Figure 1, only the star and the cycle have second largest Laplacian eigenvalue of multiplicity two. Thus, either $G_1\cong S_4$ or $G_1\cong C_4$, so that either $\overline{G}\cong S_4\cup (n-4)K_1$ or $\overline{G}\cong C_4\cup (n-4)K_1$. Therefore, $G\cong \overline{S_4\cup (n¯4)K_1}$ or $G\cong \overline{C_4\cup (n¯4)K_1}$. Finally, if two or three components of $\overline{G}$ contain all its non-zero Laplacian eigenvalues, then proceeding similarly as in (b), we arrive at a contradiction in both cases.

   • Case 5. Let ${\partial }_2^L(G)\ne {\partial }_3^L(G)$. If only one component, say $G_1$ of $\overline{G}$ contains all its non-zero Laplacian eigenvalues, then clearly L-spectrum of $G_1$ is given by $({\partial }_1^L(G)-n,{\partial }_2^L(G)-n,{\partial }_3^L(G)-n,0)$. Among all the six connected graphs on four vertices as shown in Figure 1, only the path $P_4$ and the kite $K{i}_{4,3}$ have all the three non-zero Laplacian eigenvalues different. Thus, $G_1\cong P_4$ or $G_1\cong K{i}_{4,3}$, so that $\overline{G}\cong P_4\cup (n-4)K_1$ or $\overline{G}\cong K{i}_{4,3}\cup (n-4)K_1$. Therefore, $G\cong \overline{P_4\cup (n¯4)K_1}$ or $G\cong \overline{K{i}_{4,3}\cup (n¯4)K_1}$. Using the arguments as in part (b), the only case that remains to be discussed is when two components, say $G_1$ and $G_2$, of $\overline{G}$ contain all its non-zero Laplacian eigenvalues and L-spectrum of one, say $G_1$, is $({\partial }_1^L(G)-n,{\partial }_3^L(G)-n,0)$ and of $G_2$ is $({\partial }_2^L(G)-n,0)$. Clearly, $G_1\cong S_3$ and $G_2\cong K_2$, so that $\overline{G}\cong S_3\cup K_2\cup (n-5)K_1$. Therefore, $G\cong \overline{S_3\cup K_2\cup (n¯5)K_1}$.

Conversely, note that the Laplacian spectrum of graphs $S_4\cup (n-4)K_1$, $C_4\cup (n-4)K_1$, $P_4\cup (n-4)K_1$, $K{i}_{4,3}\cup (n-4)K_1$ and $S_3\cup K_2\cup (n-5)K_1$ are $(4,1^{(2)},0^{(n-3)})$, $(4si{n}^2(\frac{\pi }{4}),4si{n}^2(\frac{2\pi }{4}),4si{n}^2(\frac{3\pi }{4}),0^{(n-3)})$, $(4si{n}^2(\frac{\pi }{8}),4si{n}^2(\frac{2\pi }{8}),4si{n}^2(\frac{3\pi }{8}),0^{(n-3)})$, $(4,3,1,0^{(n-3)})$ and $(3,2,1,0^{(n-3)})$, respectively. Also the complement of all these graphs are of diameter two. Using Lemmas 2.1 and 2.2, we see that the $D^L$-spectrum of $\overline{S_4\cup (n¯4)K_1}$, $\overline{C_4\cup (n¯4)K_1}$, $\overline{P_4\cup (n¯4)K_1}$, $\overline{K{i}_{4,3}\cup (n¯4)K_1}$ and $\overline{S_3\cup K_2\cup (n¯5)K_1}$ are $(n+4,{(n+1)}^2,n^{(n-4)},0)$, $(n+4,{(n+2)}^2,n^{(n-4)},0)$, $(n+4si{n}^2(\frac{3\pi }{8}),n+4si{n}^2(\frac{2\pi }{8}),n+4si{n}^2(\frac{\pi }{8}),n^{(n-4)},0)$, $(n+4,n+3,n+1,n^{(n-4)},0)$ and $(n+3,n+2,n+1,n^{(n-4)},0)$, respectively. ▪

Data availability statement

Data sharing is not applicable to this article as no data sets were generated or analyzed during the current study.

Additional information

Funding

The research of S. Pirzada is supported by SERB-DST, New Delhi under the research project number CRG/2020/000109. The research of Saleem Khan is supported by MANUU.