Abdollah Alhevaz, Maryam Baghipur, Ebrahim Hashemi

Faculty of Mathematical Sciences, Shahrood University of Technology, P.O. Box: 316-3619995161, Shahrood, Iran.

a.alhevaz@gmail.com, maryamb8989@gmail.com, eb−hashemi@yahoo.com

The distance signless Laplacian spectral radius of a connected graph G is the largest eigenvalue of the distance signless Laplacian matrix of G, defined as D^Q(G) = T r(G) + D(G), where D(G) is the distance matrix of G and T r(G) is the diagonal matrix of vertex transmissions of G. In this paper, we determine some upper and lower bounds on the distance signless Laplacian spectral radius of G based on its order and independence number, and characterize the extremal graphs. In addition, we give an exact description of the distance signless Laplacian spectrum and the distance signless Laplacian energy of the join of regular graphs in terms of their adjacency spectrum.

Keywords: Distance signless Laplacian matrix, spectral radius, independence number, join, distance signless Laplacian energy, connectivity, clique number.

Mathematics Subject Classification: Primary 05C12; Secondary 05C50; 15A18

DOI: 10.5614/ejgta.2018.6.2.12

1. Introduction and preliminaries

All graphs considered here are simple, undirected and connected. A graph is (usually) denoted by G = (V (G), E(G)), where V (G) is its vertex set and E(G) its edge set. The order of G is the number n = |V (G)| of its vertices and its size is the number m = |E(G)| of its edges. The set of vertices adjacent to v ∈ V (G), denoted by N(v), refers to the neighborhood of v. Let N[v] = N(v) ∪ v and C(v) = V (G) − N[v]. The degree of v means the cardinality of N(v) and

Received: 28 June 2016, Revised: 4 June 2018, Accepted: 2 September 2018.

denoted by degG(v). Let S¹ and S² be two subsets of vertices of a graph G. We denote by [S1, S2] the set of edges of G with one vertex in S¹ and the other in S2. For X ⊆ V (G), we denote by G[X] the subgraph of G induced by X. We also denote by G − e the graph obtained from G by deleting an edge e ∈ E(G). Throughout, I and J denote the identity and the all-one matrices of corresponding orders, respectively. The distance between vertices u and v, denoted by dG(u, v) or simply duv, is the length of a shortest path between u and v in G. In particular, dG(u, u) = 0 for any vertex u ∈ V (G). The diameter diam(G) is the maximum distance between any two vertices of G.

Let G be a graph with vertex set V (G) = {v1, v2, . . . , vn}. The distance matrix of G, denoted by D(G), is the symmetric real matrix with (i, j)−entry being d^viv^j . Up to now, the distance matrix has been most extensively studied. We refer the reader to the survey [1] for more details about distance eigenvalues of graphs and their applications. The transmission T rG(v) of a vertex v, is defined to be the sum of the distances from v to all other vertices in G, that is,

\[Tr_G(v) = \sum_{u \in V(G)} d_G(u, v).\]

The transmission of a connected graph G, denoted by σ(G), is the sum of distances between all unordered pairs of vertices in G. Hence, it is clear that

\[\sigma(G) = \frac{1}{2} \sum_{v \in V(G)} Tr_G(v).\]

We say that a graph is k−transmission regular (or transmission regular) if its distance matrix has constant row sum equal to k, that is T rG(v) = k for each v ∈ V (G). Naturally, just as regular graphs, transmission regular graphs are also of interest in spectral graph theory.

Studying the eigenvalues of a matrix associated with a graph is the subject of spectral graph theory, where the main objective is determining what characteristics of the graph are reflected in the spectrum of the matrix under consideration. The distance matrix (spectrum) and Laplacian matrix (spectrum) are conceived in full analogy with the ordinary graph energy and their theory is nowadays extensively elaborated (see e.g., [5], [10], [12], [13], [16], [18], [19], [20], [21]). As the distance matrix is very useful in different fields, including the design of communication networks, graph embedding theory as well as molecular stability, therefore maximizing or minimizing the distance spectral radius over a given class of graphs is of great interest and importance.

The matrix of interest here is the distance signless Laplacian matrix. In [2], Aouchiche and Hansen introduced the distance signless Laplacian matrix of a connected graph G as the n × n matrix defined as, D^Q(G) = T r(G) + D(G), where D(G) is the distance matrix of G and T r(G) is the diagonal matrix of vertex transmissions of G. Since D^Q(G) is symmetric (positive semidefinite), its eigenvalues can be arranged as: ρ1(G) ≥ ρ2(G) ≥ · · · ≥ ρn(G) ≥ 0, where ρ1(G) is called the distance signless Laplacian spectral radius of G. From now onwards, we will denote ρ1(G) by ρ(G). As D^Q(G) is non-negative and irreducible, by the Perron-Frobenius Theorem, ρ(G) is positive, simple and there is a unique positive unit eigenvector X corresponding to ρ(G), which is called the distance signless Laplacian Perron vector of G.

The study of the distance signless Laplacian matrix (spectrum) started only quite recently, and only some of its basic properties have been established so far (see e.g., [6], [7], [14], [24]). In this paper, we determine some upper and lower bounds on the distance signless Laplacian spectral radius of G based on its order and independence number, and characterize the extremal graph. In addition, we give an exact description of the distance signless Laplacian spectrum and the auxiliary distance signless Laplacian energy of the join of regular graphs in terms of their adjacency spectrum.

2. On graphs which maximize the distance signless Laplacian spectral radius

Given a connected graph G on n vertices, a column vector X = (x1, x2, . . . , xn) ^T ∈ R n can be considered as a function defined on V (G) which maps vertex vⁱ to xⁱ , i.e., X(vi) = xⁱ , for i = 1, 2, . . . , n. Then,

\[X^{T} D^{Q}(G) X = \sum_{\{u,v\} \subseteq V(G)} d_{uv} (x_{u} + x_{v})^{2},\]

and λ is an eigenvalue of D^Q(G) corresponding to the eigenvector X if and only if X 6= 0 and for each v ∈ V (G),

\[\lambda x_v = \sum_{u \in V(G)} d_{uv}(x_u + x_v).\]

These equations are called the (λ, x)−eigenequations of G. For a normalized column vector X ∈ R ⁿ with at least one non-negative component, by the Rayleigh's principle, we have

\[\rho(G) \ge X^T D^Q(G) X,\]

with equality if and only if X is the distance signless Laplacian Perron vector of G.

Let e = uv be an edge of G such that G − e is also connected. The removal of e does not decrease distance, while it does increase the distance by at least one unit, as the distance between u and v is 1 in G and at least 2 in G − e. Similarly, adding a new edge to G does not increase distances, while it does decrease the distance by at least one. By Perron-Frobenius Theorem, we have the following lemma immediately.

Lemma 2.1. [17] Let G be a connected graph with u, v ∈ V (G). If uv /∈ E(G), then ρ(G+uv) < ρ(G). If uv ∈ E(G) such that G − uv is also connected, then ρ(G) < ρ(G − uv).

The following lemma will be useful in the sequel.

Lemma 2.2. [24] Let G be a connected graph on n vertices. Then

\[\rho(G) \ge \frac{4\sigma(G)}{n},\]

with equality if and only if G is transmission regular.

In this section, we are interested to find graphs which maximize the distance signless Laplacian spectral radius and also to find graphs whose distance signless Laplacian spectral radius is close to the maximum value. In order to better understanding these graphs, we consider the set Gn,∆, where ∆ ≥ 2, of connected graphs with n vertices having the fixed value of the maximum degree ∆. Otherwise, if we only bound the maximum degree by ∆, the maximum graphs will inevitably be the paths. Still, even with the requirement that a graph contains a vertex of degree ∆, the extremal graphs resemble a path-like structure.

Definition 2.1. The broom Bn,^∆ is a tree on n vertices obtained by taking a path Pn−∆+1 and an empty graph K¯∆−1, and joining one end-vertex of a path with every vertex of the empty graph. The other end-vertex of the path Pn−∆+1 with degree 1 in Bn,^∆ will be called the distant-leaf of Bn,∆.

Figure 1. The broom tree B10,4.

The following theorem is known to some extent in mathematical chemistry; however, we give a direct proof here for the sake of completeness.

Theorem 2.1. For every graph G ∈ Gn,∆, it holds that

\[\sigma(G) \le \sigma(B_{n,\Delta}),\]

with equality if and only if G is isomorphic to Bn,∆.

Proof. Let G be a graph in Gn,∆. Note first that by Lemma 2.1, removing an edge {u, v} from G strictly increases its distance signless Laplacian spectral radius. Thus, for any spanning tree T of G it holds that

\[\sigma(G) \le \sigma(T),\]

with equality if and only if G = T. As any graph in Gn,^∆ has a spanning tree with the same maximum degree ∆, we may thus in the sequel restrict our proof to such trees only.

We shall now prove the theorem by induction on n. For n = ∆ + 1, there exists only one tree with ∆ + 1 vertices and the maximum degree ∆, which is the star K1,^∆ ∼= B∆+1,∆. So, the base case of our induction is established.

Now, suppose by induction hypothesis that for n ≥ ∆+1, the broom Bn,^∆ attains the maximum transmission in Gn,^∆ and let T be any tree in Gn+1,∆. The tree T contains a leaf q whose removal does not decrease the maximum degree of T. Otherwise, T would contain only one vertex of degree ∆ and all leaves would be adjacent to that vertex, yielding that T would be isomorphic to a star, which is a contradiction with n + 1 ≥ ∆ + 2.

Let p be the unique neighbor of q in T. For any vertex u of T it holds that d^T (u, q) = d^{T −}q(u, p) + 1, while the distance between all other pairs of vertices of T − q remains unchanged. Thus, it holds that σ(T) = σ(T −q) +T r^{T −}q(p) +n. From the inductive hypothesis it follows that

\[\sigma(T - q) \le \sigma(B_{n,\Delta}),\tag{1}\]

thus, σ(T) ≤ σ(Bn+1,∆).

The equality holds if and only if the equality holds in (1). Then we have, by inductive hypothesis, that T − q ∼= Tn,^∆ and that q is a distant leaf of Bn,∆. This shows that T ∼= Bn+1,∆, and thus, Bn+1,^∆ is the unique graph (up to isomorphism) in Gn+1,^∆ that attains the maximum value of the transmission, and the proof is complete.

Notice that the path Pⁿ has the maximum distance signless Laplacian spectral radius. Let G be a simple graph and v one of its vertices. For k, l ≥ 0, we denote by G(v, k) the graph obtained from G ∪ P^k by adding an edge between v and the end vertex of Pk, and by G(v, k, l) the graph obtained from G ∪ P^k ∪ P^l by adding edges between v and one of the end vertices in both P^k and Pl .

Lemma 2.3. [14, Lemma 3.3] Let G be a simple graph and v be one of its vertices. If k ≥ l ≥ 1, then

\[\rho\Big(G(v,k,l)\Big)<\rho\Big(G(v,k+1,l-1)\Big).\]

Next, for ∆ > 2, we can apply the transformation of Lemma 2.3 at the vertex of degree ∆ in Bn,^∆ and obtain Bn,∆−1. Thus ρ(Bn,∆) < ρ(Bn,∆−1) for ∆ > 2, which shows the chain of inequalities

\[\rho(S_n) = \rho(B_{n,n-1}) < \rho(B_{n,n-2}) < \ldots < \rho(B_{n,3}) < \rho(B_{n,2}) = \rho(P_n).\]

A subset S of a vertex set V (G) of a graph G is said to be an independent set, if no two vertices of S are adjacent in G. The independence number of G is the maximum number of vertices in the independent sets in G. The following theorem will gives the lower bound for distance signless Laplacian spectral radius in terms of the order and the independence number of G. A clique in a graph is a set of mutually adjacent vertices. The maximum size of a clique in a graph G is called the clique number of G.

Theorem 2.2. Let G be a connected simple graph of order n, with independence number s, then

\[\rho(G) \ge \frac{2s + 3n - 6 + \sqrt{4s(3s - 4) + n(n + 4) - 4ns + 4}}{2}.\] (2)

Proof. Let S be the maximum independent set with independence number s. Let x be the principal eigenvector of G. It is easily seen that the components of x have the same value, say x(v1) for vertices in S and x(vn) for vertices in V (G) \ S. Then, by the (ρ(G), x)−eigenequations of G, we have

\[\rho(G)x(v_1) \geq 2(s-1)(x(v_1)+x(v_1))+(n-s)(x(v_1)+x(v_n)), \rho(G)x(v_n) \geq (n-s-1)(x(v_n)+x(v_n))+s(x(v_1)+x(v_n)),\]

and thus ρ(G) is the largest root of the equation

\[\rho^2 + (6 - 2s - 3n)\rho + (2n^2 - 2s^2 + 4ns - 10n - 2s + 8) \ge 0.\]

From this we get the required result.

Graph operations are natural techniques for producing new graphs from old ones, and their spectra and energy have received considerable attention in recent years. The join of two vertexdisjoint connected graphs G and H, denoted G ∨ H, is the graph obtained from the union G ∪ H by joining each vertex of G and a vertex of H.

Remark 2.1. We can easily verify that in (2) the equality holds if and only if G = K¯ ^s ∨ Kn−s, with independence number s.

Theorem 2.3. Let G be a connected simple graph, with independence number s and clique number ω. Then

\[\rho(G) \ge \frac{5s + 3\omega - 8 + \sqrt{(3s + \omega - 4)^2 - 7(s - 1)(\omega - 1)}}{2},\tag{3}\]

with equality if and only if G ∼= Kω−¹ ∨ K¯ s.

Proof. Let S and C be a maximum independent set and a maximum clique of G, respectively. Let x be the principal eigenvector of G. It is easily seen that the components of x have the same value, say x(v1) for vertices in V (S) and x(vn) for vertices in V (C). We have ∀u, v ∈ C : d(u, v) = 1, ∀u, v ∈ S : d(u, v) ≥ 2. On the other hand, |S ∩ C| ≤ 1. Then, by the (ρ(G), x)-eigenequations of G, we have

\[\rho(G)x(v_1) \geq 2(s-1)(x(v_1) + x(v_1)) + (\omega - 1)(x(v_1) + x(v_n)) \rho(G)x(v_n) \geq (\omega - 1)(x(v_n) + x(v_n)) + (s-1)(x(v_1) + x(v_n)),\]

and thus ρ(G) is the largest root of the equation

\[\rho^{2}(G) - (5s + 3\omega - 8)\rho(G) + (8(s - 1)(\omega - 1) + 2(\omega - 1)^{2} + 4(s - 1)^{2}) \ge 0.\]

It follows that ρ(G) ≥ 5s+3ω−8+^√ (3s+ω−4)2−7(s−1)(ω−1) 2 .

If G ∼= Kω−¹ ∨ K¯ ^s, we can easily verify that in (3) the equality holds. Conversely, if the equality in (3) holds, then S ∪ C = V (G) and |C ∩ S| = 1. Let |C ∩ S| = {u}. Since u ∈ C, then for every v ∈ C we have uv ∈ E(G). Similarly, u ∈ S and P u∈C,v∈S d(u, v) = (s − 1)(ω − 1) results for every x ∈ S and y ∈ C − {u}, xy ∈ E(G). Therefore, G ∼= Kω−¹ ∨ K¯ s.

Corollary 2.1. Let G be a connected graph with G¯ connected graph. Then

\[\rho(\bar{G}) \ge \frac{5\omega + 3s - 8 + \sqrt{(3\omega + s - 4)^2 - 7(\omega - 1)(s - 1)}}{2},\]

with equality if and only if G ∼= K^ω ∨ K¯ ^s−1, and

\[\rho(\bar{G}) \ge \frac{3n + 2\omega - 8 + \sqrt{(n + 2\omega - 4)^2 - 7(\omega - 1)(n - \omega - 1)}}{2},\]

with equality if and only if G ∼= K^ω ∨ K¯ ⁿ−ω−1.

Proof. Follows from Theorem 2.3 and equality s(G¯) = ω(G).

3. On distance signless Laplacian spectral radius of the complete k-partite graphs

Recall that the matrix \(D^Q(G)\) is non-negative and irreducible, so the eigenvalues of \(D^Q(G)\) are real and we can order the eigenvalues as \(\rho(G) = \rho_1(G) \ge \rho_2(G) \ge \cdots \ge \rho_n(G)\). We start this section recalling the well-known Cauchy interlace theorem [4] that relates the eigenvalues of an arbitrary Hermitian matrix with its principal submatrix. More precisely, this theorem states that the eigenvalues of a Hermitian matrix A of order n are interlaced with those of any principal submatrix. This theorem plays an important role in the study of the distance signless Laplacian spectral radius of the complete k-partite graphs.

Lemma 3.1. [4] (Cauchy Interlace Theorem) Let A be a Hermitian matrix of order n, and let B be a principal submatrix of A of order m. If \(\lambda_1(A) \geq \lambda_2(A) \geq \ldots \geq \lambda_n(A)\) lists the eigenvalues of A and \(\mu_1(B) \geq \mu_2(B) \geq \ldots \geq \mu_m(B)\) the eigenvalues of B, then \(\lambda_{n-m+i}(A) \leq \mu_i(B) \leq \lambda_i(A)\) for \(i = 1, 2, \ldots, m\).

The following inequalities are well-known Courant-Weyl inequalities.

Lemma 3.2. [23] (Courant-Weyl inequalities) Let A and B be \(n \times n\) Hermitian matrices and C = A + B. Then

\[\lambda_i(C) \le \lambda_j(A) + \lambda_{i-j+1}(B)(n \ge i \ge j \ge 1),\]
\[\lambda_i(C) \ge \lambda_j(A) + \lambda_{i-j+n}(B)(1 \le i \le j \le n).\]

Lemma 3.3. Let \(G = K_{n_1,...,n_k}\) be a complete k-partite graph for \(2 \le k \le n-1\). Then \(\rho_n(G) \ge n + n_1 - 4\). Moreover, if \(n_1 = n_2 = \cdots = n_k\) and \(n = kn_1\), then \(\rho_n(G) = n + n_1 - 4\) with multiplicity n - k.

Proof. Without loss of generality, we may assume that \(n_1 \ge n_2 \ge ... \ge n_k\). It is clear that the diameter of G is 2. In a connected graph with diameter 2, we have Tr(v) = d(v) + 2(n - d(v) - 1) = 2n - 2 - d(v), and therefore Tr(G) = (2n - 2)I - Diag(Deg). Then \(D^Q(G) = J - I + A^c + (2n - 2)I - Diag(Deg)\), where \(A^c\) is the adjacency matrix of \(G^c\). Note that \(G^c\) is the union of complete graphs, then by the Courant-Weyl inequality,

\[\rho_n(G) \geq \rho_n(J-I) + \rho_n(A^c) + \rho_n((2n-2)I) + \rho_n(-Diag(Deg))\]
\[\geq -2 + (2n-2) - (n-n_1) = n + n_1 - 4.\]

In the following, we shall show that there exists an eigenvalue which equals to \(n+n_1-4\). Suppose \(V(G)=V_1\cup V_2\cup\ldots\cup V_k\) for \(2\leq k\leq n-1\) and \(n_1=|V_i|(i=1,\ldots,k)\). Then, the distance signless Laplacian matrix of G is

\[D^{Q}(G) = \begin{pmatrix} S & J_{n_{1} \times n_{1}} & J_{n_{1} \times n_{1}} \dots J_{n_{1} \times n_{1}} \\ J_{n_{1} \times n_{1}} & S & J_{n_{1} \times n_{1}} \dots J_{n_{1} \times n_{1}} \\ \vdots & \vdots & \vdots \ddots & \vdots \\ J_{n_{1} \times n_{1}} & J_{n_{1} \times n_{1}} & J_{n_{1} \times n_{1}} \dots J_{n_{1} \times n_{1}} \\ J_{n_{1} \times n_{1}} & J_{n_{1} \times n_{1}} & J_{n_{1} \times n_{1}} \dots S \end{pmatrix},\]

where \(S = 2J_{n_1 \times n_1} + (n + n_1 - 4)I_{n_1}\). Hence

\[\begin{array}{lcl} P_{D^Q(G)}(\rho) & = & \det\Bigl(\rho I - D^Q(G)\Bigr) \\ \\ & = & \Bigl(\rho - (n+n_1-4)\Bigr)^{n-k} \begin{vmatrix} \zeta & -n_1 & -n_1 \ldots - n_1 \\ -n_1 & \zeta & -n_1 \ldots - n_1 \\ \vdots & \vdots & \vdots \ddots \\ -n_1 & -n_1 & -n_1 \ldots - n_1 \\ -n_1 & -n_1 & -n_1 \ldots \zeta \end{vmatrix}, \\ \end{array}\]

where \(\zeta = \rho - n - 3n_1 + 4\). Since \(k \leq n - 1\), thus the multiplicity of \(n + n_1 - 4\) is at least n - k > 1.

Note that \(D^Q(G) = J - I + A^c + (2n-2)I - Diag(Deg)\). Then by Courant-Weyl inequalities, we obtain \(\rho_n(J-I) + \rho_i(A^c) + \rho_n((2n-2)I - Diag(Deg)) \le \rho_i(G) \le \rho_1(J-I) + \rho_{i-1}(A^c) + \rho_2((2n-2)I - Diag(Deg))\) for \(2 \le i \le n\). Note that \(G^c\) is a union of complete graphs \(K_{n_1}, \ldots, K_{n_k}\). It follow that \(\rho_i(A^c) = n_i - 1\) for \(i = 1, \ldots, k\). Therefore, \(\rho_i(G) \ge n + n_1 + n_i - 4\) for \(2 \le i \le k\). Thus \(\rho_i(G) \ge n + n_1 - 3\) for \(i = 2, \ldots, k\) since \(n_i \ge 1\) and \(\rho_1(G) > 2n - 2\). Thus the multiplicity of \(n + n_1 - 4\) is n - k, as desired. \(\square\)

Now, we will focus on the connected graphs with diameter equal to 2.

Lemma 3.4. The graph \(K_{1,n-1}\) is the unique graph with the maximizing distance signless Laplacian spectral radius among all graphs with diameter 2.

Proof. Let G be an arbitrary connected graph of diameter 2 with \(V(G) = \{v_1, \ldots, v_n\}\). Suppose that \(X = (x_1, x_2, \ldots, x_n)\) is the Perron vector of G, where \(x_i\) corresponds to \(v_i\) for \(i = 1, \ldots, n\). Let \(v_t\) be a vertex of V(G) such that \(x_t = min\{x_i | v_i \in V(G)\}\). Then, we shall follow the following two cases.

Case 1. \(d(v_t) = n - 1\).

Then, we delete all edges in \(N(v_t)\), and then the resulting graph is \(K_{1,n-1}\). Hence we have \(\rho(K_{1,n-1}) \ge \rho(G)\) and the equality holds if and only if \(G \cong K_{1,n-1}\).

Case 2. \(d(v_t) \le n - 2\).

Then \(C(v_t) \neq \phi\). Obviously, each vertex of \(C(v_t)\) is adjacent to at least one vertex of \(N(v_t)\). Let \(G' = G - [N(v_t), C(v_t)] + \{v_t v_i | v_i \in C(v_t)\}\). Clearly, the diameter of G' is 2 and \(\Delta(G') = n - 1\). But

\[\rho(G') - \rho(G) \ge x^t (D^Q(G') - D^Q(G))x\] \[= \frac{1}{2} \sum_{v_i \in V(C_t)} (x_i + x_t)^2 - \sum_{v_i \in C(v_t)} (x_i + x_t)^2\] \[+ \sum_{v_i v_j \in [N(v_t), C(v_t)]} (x_i + x_j)^2 - \frac{1}{2} \sum_{v_i v_j \in [N(v_t), C(v_t)]} (x_i + x_j)^2\] \[= \frac{1}{2} \sum_{v_i v_i \in [N(v_t), C(v_t)]} (x_i + x_j)^2 - \frac{1}{2} \sum_{v_i \in C(v_t)} (x_i + x_t)^2 \ge 0.\]

Therefore, we have \(\rho(G') \geq \rho(G)\). Then by case 1, we get \(\rho(K_{1,n-1}) \geq \rho(G') \geq \rho(G)\). If \(\rho(K_{1,n-1}) = \rho(G)\), then \(G' \cong K_{1,n-1}\) and \(\rho(G) = \rho(G')\). It follows that X is also the Perron vector of \(K_{1,n-1}\). Then if \(v_i, v_j \neq v_t\), then \(x_i = x_j > x_t\). Since all the above inequalities are equalities, we have

\[\sum_{v_i v_j \in [N(v_t), C(v_t)]} (x_i + x_j)^2 = \sum_{v_i \in C(v_t)} (x_i + x_t)^2.\]

Then for each edge \(v_i v_j \in [N(v_t), C(v_t)], v_i \in N(v_t), v_j \in C(v_t)\), we get \(x_i = x_t\), a contradiction. Hence, \(\rho(K_{1,n-1}) > \rho(G)\). This completes the proof.

It is well-known that if G is regular, then G has exactly three distinct A-eigenvalues if and only if G is strongly regular. We have the following result for connected graphs with diameter 2.

Theorem 3.1. Let G be a connected graph of diameter 2. If G is k-regular, then G has exactly three distinct \(D^Q(G)\)-eigenvalues if and only if G is strongly regular.

Proof. Since the diameter of G is 2, thus \(D^Q(G) = J - I + A^c + (2n-2)I - Diag(Deg)\), where \(A^c\) is the adjacency matrix of \(G^c\). Obviously \(\rho(G) = 4(n-1) - 2k\) and \(X = (1, \dots, 1)^T\) is the distance signless Laplacian Perron vector corresponding to \(\rho(G)\). Note that since G is k-regular, then \(G^c\) is (n-1-k)-regular and \(X = (1, \dots, 1)^T\) is also an eigenvector corresponding to \(\rho(A^c)\). Let \(X_i\) be the eigenvector of \(A^c\) corresponding to \(\rho_i(A^c)\) for \(1 \le i \le n\). Then \(1 \le i \le n\) and then \(1 \le i \le n\). Then \(1 \le i \le n\) and then \(1 \le i \le n\) are eigenvalues if and only if \(1 \le i \le n\) are eigenvalues if and only if \(1 \le i \le n\) are eigenvalues if and only if \(1 \le i \le n\) are eigenvalues if and only if \(1 \le i \le n\) are eigenvalues.

Theorem 3.2. Let \(G = K_{n_1,...,n_k}\) be a complete k-partite graph with \(n_1 = \cdots = n_k\) and \(n = kn_1\). Then the characteristic polynomial of \(D^Q(G)\) is

\[P_{D^{Q}(G)}(\rho) = \left(\rho - (n+n_1-4)\right)^{n-k} (\rho - n - 2n_1 + 4)^{k-1} (\rho - 2n - 2n_1 + 4).\]

Proof. By Lemma 3.3,

\[P_{D^Q(G)}(\rho) = \det(\rho I - D^Q(G))\]

\[= \left(\rho - (n+n_1-4)\right)^{n-k} \begin{vmatrix} \rho - n - 3n_1 + 4 & -n_1 & -n_1 \dots - n_1 \\ -n_1 & \rho - n - 3n_1 + 4 & -n_1 \dots - n_1 \\ \vdots & \vdots & \vdots \\ -n_1 & -n_1 & -n_1 \dots - n_1 \\ -n_1 & -n_1 & -n_1 \dots \rho - n - 3n_1 + 4 \end{vmatrix}\]

\[= \left(\rho - (n+n_1-4)\right)^{n-k} \begin{vmatrix} \rho - n - 3n_1 + 4 & -n_1 & -n_1 \dots - n_1 \\ n + 2n_1 - 4 - \rho & \rho - n - 2n_1 + 4 & 0 \dots 0 \\ \vdots & \vdots & \vdots \\ n + 2n_1 - 4 - \rho & 0 & 0 \dots 0 \\ n + 2n_1 - 4 - \rho & 0 & 0 \dots \rho - n - 2n_1 + 4 \end{vmatrix}\]

On distance signless Laplacian spectrum and energy of graphs | Abdollah Alhevaz et al.

\[= \left(\rho - (n+n_1-4)\right)^{n-k} \left((\rho - n - 2n_1 + 4)^k - n(\rho - n - 2n_1 + 4)^{k-1}\right)\]\[= \left(\rho - (n+n_1-4)\right)^{n-k} (\rho - n - 2n_1 + 4)^{k-1} (\rho - 2n - 2n_1 + 4).\]

Now, we give a lower bound on the spectral radius of D^Q(G) of a bipartite graph.

Theorem 3.3. Let G = (V, E) be a connected bipartite graph of order n with bipartition V (G) = A ∪ B, where |A| = p, |B| = q. Then

\[\rho(G) \ge \frac{3n + 2p - 8 + \sqrt{9n^2 + 16q^2 - 28pq}}{2},\tag{4}\]

with equality if and only if G is a complete bipartite graph Kp,q.

Proof. Since V (G) = A ∪ B and A ∩ B = ∅, |A| = p, |B| = q, we can assume that A = {1, 2, . . . , p} and B = {p + 1, p + 2, . . . , p + q}, where p + q = n. Let X = (x1, x2, . . . , xn) T be an eigenvector of D^Q(G) corresponding to the largest eigenvalue ρ(G). We can assume that xⁱ = min{xk| k ∈ A} and also x^j = min{xk| k ∈ B}. For i ∈ A,

\[\rho(G)x_i = \sum_{k=1, k \neq i}^{p} d_{i,k}(x_k + x_i) + \sum_{k=p+1}^{p+q} d_{i,k}(x_k + x_i) \ge 4(p-1)x_i + q(x_j + x_i).\] (5)

For j ∈ B,

\[\rho(G)x_j = \sum_{k=1}^p d_{j,k}(x_k + x_j) + \sum_{k=p+1, k \neq j}^{p+q} d_{j,k}(x_k + x_j) \ge p(x_i + x_j) + 4(q-1)x_j.\] (6)

Since G is a connected graph, x^k > 0 for all k ∈ V . From (5) and (6), we get

\[\rho^{2}(G) + (8 - 5p - 5q)\rho(G) + 4p^{2} + 4q^{2} + 16pq - 20p - 20q + 16 \ge 0.\]

From this we get the required result (4).

Now suppose that equality holds in (4). Then, all inequalities in the above argument must be equalities. From equality in (5), we get x^k = x^j and ik ∈ E(G), for all k ∈ B. From equality in (6), we get x^k = xⁱ and jk ∈ E(G), for all k ∈ A. Thus, each vertex in each set is adjacent to all the vertices on the other set and vice versa. Hence, G is a complete bipartite graph Kp,q, and the proof is complete.

4. On distance signless Laplacian energy of join of regular graphs

Energy of a graph is a concept defined in 1978 by Ivan Gutman in [8] and originating from theoretical chemistry. Let G be a simple graph of order n with adjacency matrix A(G) having eigenvalues \(\lambda_1, \lambda_2, \ldots, \lambda_n\). Then the energy of a graph G, denoted E(G), is defined as \(E(G) = \sum_{i=1}^{n} |\lambda_i|\) (see [9] for details and recent survey). Nowadays many results have been obtained about the energy of different graph structures. The pioneering paper [8] further proposes the study of energy in graphs with an analogue of the energy defined with respect to other (than adjacency) matrices assigned to the graphs. This proposal has been put into effect and extended: the energy of a graph with respect to Laplacian matrix as well as the energy of a graph with respect to distance matrix, have been studied (see [10] and [12] for more details in this subject). For distance signless Laplacian matrix, we define the sum of its eigenvalues as auxiliary energy and denote by \(E_{DG}(G)\).

Our main aim in the following results is the description of the distance signless Laplacian spectrum and the auxiliary distance signless Laplacian energy of the join of regular graphs in terms of their adjacency spectrum.

Theorem 4.1. Let \(G_i\) be an \(r_i\)-regular graph with \(n_i\) vertices and eigenvalues of the adjacency matrix \(A_{G_i}\), \(\lambda_{i,1} = r_i \ge \lambda_{i,2} \ge \cdots \ge \lambda_{i,n_i}\), where \(i \in \{1,2\}\). Then the distance signless Laplacian spectrum of \(G_1 \lor G_2\) consists of eigenvalues \(2n_1 + n_2 - \lambda_{1,j} - r_1 - 4\) and \(2n_2 + n_1 - \lambda_{2,j} - r_2 - 4\) for \(j = 2, 3, \ldots, n_i\) and two more eigenvalues of the form

\[\frac{5(n_1+n_2)-2(r_1+r_2)-8\pm\sqrt{(3(n_1-n_2)-2(r_1-r_2))^2+4n_1n_2}}{2}.\] (7)

Proof. The distance signless Laplacian matrix \(D^Q(G)\) of the join \(G_1 \vee G_2\) has the form

\[D^{Q}(G) = \begin{pmatrix} 2J - A_{G_1} + (2n_1 + n_2 - r_1 - 4)I & J_{n_1 \times n_2} \\ J_{n_2 \times n_1} & 2J - A_{G_2} + (2n_2 + n_1 - r_2 - 4)I \end{pmatrix}.\]

As a regular graph, \(G_1\) has the all-one vector j as an eigenvector corresponding to eigenvalue \(r_1\), while all other eigenvectors are orthogonal to j. (Note that \(G_1\) need not be connected, and thus, \(r_1\) need not be a simple eigenvalue of \(G_1\)).

Let \(\lambda\) be an arbitrary eigenvalue of the adjacency matrix of \(G_1\) with corresponding eigenvector x, such that \(j^Tx=0\). Then \((x0_{n_2\times 1})^T\) is the eigenvector of \(D^Q(G)\) corresponding to eigenvalue \(2n_1+n_2-\lambda_{1,j}-r_1-4\). A similar argument holds for an arbitrary eigenvalue \(\mu\) of \(A_{G2}\), with the corresponding eigenvector y such that \(j^Ty=0\). In this way, forming the eigenvectors of the forms \((x0)^T\) and \((0y)^T\), we can construct a total of \(n_1+n_2-2\) mutually orthogonal eigenvectors of \(D^Q(G)\). This implies that the two remaining eigenvectors of \(D^Q(G)\) have the form \((\alpha_j\beta_j)^T\) for a suitable choice of \(\alpha\) and \(\beta\).

Suppose now that \(\rho\) is an eigenvalue of \(D^Q(G)\) with an eigenvector of the form \((\alpha_j\beta_j)^T\). Then, using \(A_{G_1}j=r_1j\) and \(A_{G_2}j=r_2j\), we get the system

\[\rho\alpha = (2n_1 - r_1 - 2)(\alpha + \alpha) + n_2(\alpha + \beta)\]
\[\rho\beta = n_1(\alpha + \beta) + (2n_2 - r_2 - 2)(\beta + \beta).\]

Eliminating α and β we get the quadratic equation in ρ

\[\rho^{2} - \rho((4n_{1} + n_{2} - 2r - 4) + (4n_{2} + n_{1} - 2r_{2} - 4)) + (4n_{1} + n_{2} - 2r - 4)(4n_{2} + n_{1} - 2r_{2} - 4) - n_{1}n_{2} = 0\]

whose solutions are given by (7). One easily checks that these two solutions are indeed the remaining two eigenvalues of D^Q(G).

Theorem 4.2. For i = 1, 2, let Gⁱ be an ri-regular graph with nⁱ vertices. Then

\[E_{DQ}(G_1 \vee G_2) = n_1(2n_1 + n_2 - r_1) + n_2(2n_2 + n_1 - r_2) - 2(n_1 + n_2).\]

Proof. For i = 1, 2, denote the eigenvalues of the adjacency matrix A^Gi by λi,¹ = rⁱ ≥ λi,² ≥ . . . ≥ λi,nⁱ . According to the Theorem 4.1, the distance signless Laplacian eigenvalues of G¹ ∨ G² are

\[\frac{5(n_1+n_2)-2(r_1+r_2)-8\pm\sqrt{(3(n_1-n_2)-2(r_1-r_2))^2+4n_1n_2}}{2}\] (8)

and 2n1+n2−λ1,j−r1−4, 2n2+n1−λ2,j−r2−4 for j = 2, 3, . . . , nⁱ . The eigenvalues given by (8) are both non-negative, thus the sum of eigenvalues (8) is equal to (5n1−2r1−4)+ (5n2−2r2−4). For the remaining eigenvalues of G¹ ∨ G2, we have,

\[\sum_{j=2}^{n_1} (2n_1 + n_2 - \lambda_{1,j} - r_1 - 4) + \sum_{j=2}^{n_2} (2n_2 + n_1 - \lambda_{2,j} - r_2 - 4) = (n_1 - 1)(2n_1 + n_2 - r_1 - 4) + r_1 + (n_2 - 1)(2n_2 + n_1 - r_2 - 4) + r_2,\]

concluding that the auxiliary distance signless Laplacian energy of G¹ ∨ G² is equal to n1(2n¹ + n² − r1) + n2(2n² + n¹ − r2) − 2(n¹ + n2), as desired.

Our goal here is to compute the auxiliary distance signless Laplacian energy of a complete multipartite graph on n vertices.

Theorem 4.3. If n¹ = · · · = n^k ≥ 2 and n = kn1, then

\[E_{DQ}(K_{n_1,\dots,n_k}) = n(n+n_1-2).\]

In the sequel we want to prove this theorem. In order to estimate the eigenvalues of D^Q, we have to resort to the concept of equitable matrix partition, an analog of the concept of equitable partition of a graph. A partition V = ∪ k ⁱ=1Vⁱ of the index set of matrix A is called an equitable matrix partition if there exists an k ×k matrix B such that for every i, j ∈ {1, . . . , r} and for every u ∈ Vⁱ holds

\[\sum_{v \in V_j} A_{u,v} = B_{i,j}.\]

Apparently, from an equitable matrix partition of D^Q(G), with the matrix B being equal to

\[B = n_1 J + (n + 2n_1 - 4)I, (9)\]

where J is the all-ones matrix and I is the unit matrix. We have the following fundamental lemma.

Lemma 4.1. Let matrix \(D^Q(G)\) has an equitable matrix partition \(V = \bigcup_{i=1}^k V_i\) with the corresponding matrix B. Each eigenvalue of B is then also an eigenvalue of \(D^Q(G)\).

Proof. Let \(\rho\) be an eigenvalue of B with an eigenvector x such that \(Bx = \rho x\). Form a vector y, indexed by V, given by

\[y_u = x_i \quad if \quad u \in V_i.\]

Then for \(u \in V_i\) holds

\[(D^{Q}(G)y)_{u} = \sum_{v \in V} D^{Q}(G)_{u,v} y_{v} = \sum_{j=1}^{k} \sum_{v \in V_{j}} D^{Q}(G)_{u,v} x_{j}\]\[= \sum_{j=1}^{k} B_{i,j} x_{j} = (Bx)_{i} = \rho x_{i} = \rho y_{u}.\]

Since this holds for arbitrary u, we have \(D^Q(G)y=\rho y\) and \(\rho\) is an eigenvalue of \(D^Q(G)\). \(\square\)

If \(\rho\) has multiplicity k as an eigenvalue of B, then there is a set of k mutually independent eigenvectors of B corresponding to \(\rho\). Clearly, linear independence is preserved by the construction in the proof of previous lemma, so we obtain a set of k mutually independent eigenvectors of \(D^Q(G)\) corresponding to \(\rho\). This implies that \(\rho\), as an eigenvalue of \(D^Q(G)\), has multiplicity at least k. The characteristic polynomial of the matrix B given by (9) after subtracting the last row from each of the previous rows, becomes

\[\det(\rho I - B) = \det\left((\rho - (n + 2n_1 - 4))I - n_1 J\right) = (\rho - n - 2n_1 + 4)^k \left(1 - \frac{n}{\rho - n - 2n_1 + 4}\right).\]

Therefore, the eigenvalues of B are non-negative and so

\[\sum_{i=1}^k |\rho_i| = \sum_{i=1}^k \rho_i.\]

From the Vieta's formula for the characteristic polynomial of B we further have

\[\sum_{i=1}^{k} \rho_i = k(n+3n_1-4).\]

Therefore, the auxiliary distance signless Laplacian energy of \(K_{n_1,\dots,n_k}\), if \(n_1 = \dots = n_k \ge 2\), is equal to

\[E_{DQ}(K_{n_1,\dots,n_k}) = |n+n_1-4| \sum_{i=1}^k (n_i-1) + \sum_{i=1}^k |\rho_i|\]\[= |n+n_1-4|(n-k)+nk+3n-4k\]\[= n(n+n_1-2),\]

as desired.

Acknowledgement

The authors thanks the anonymous referee for the helpful remarks that greatly improved the presentation of the material. This research was in part supported by a grant from Shahrood University of Technology.

References

• [1] M. Aouchiche and P. Hansen, Distance spectra of graphs: a survey, Linear Algebra Appl. 458 (2014), 301–386.
• [2] M. Aouchiche and P. Hansen, Two Laplacians for the distance matrix of a graph, Linear Algebra Appl. 439 (2013), 21–33.
• [3] N.L. Biggs, Algebraic Graph Theory, Cambridge University Press, 1974.
• [4] A. Cauchy, Cours dAnalyse de l ´ Ecole Polytechnique, In oeuvres completes, 1821. ´
• [5] K.C. Das, On the largest eigenvalue of the distance matrix of a bipartite graph, MATCH Commun. Math. Comput. Chem. 62 (2009), 667–672.
• [6] K.C. Das, Proof of conjectures on the distance signless Laplacian eigenvalues of graphs, Linear Algebra Appl. 467 (2015), 100–115.
• [7] K.C. Das, C. Silva Junior, M. De Freitas and R. R. Del-Vecchio, Bounds on the entries of the principal eigenvector of the distance signless Laplacian matrix, Linear Algebra Appl. 483 (2015), 200–220.
• [8] I. Gutman, The energy of a graph, Ber. Math. Statist. Sekt. Forschungsz. Graz, 103 (1978), 1–22.
• [9] I. Gutman, The energy of a graph: Old and new results, in: A. Betten, A. Kohnert, R. Laue, A. Wassermann (Eds.), Algebraic Combinatorics and Applications, Springer-Verlag, Berlin, (2001), 196–211.
• [10] I. Gutman and B. Zhou, Laplacian energy of a graph, Linear Algebra Appl. 414 (2006), 29– 37.
• [11] F. Harary, Graph Theory, Narosa Publishing House, New Delhi, 1999.
• [12] G. Indulal, I. Gutman and A. Vijayakumar, On distance energy of graphs, MATCH Commun. Math. Comput. Chem. 60 (2008), 461–472.
• [13] H. Lin, Y. Hong, J. Wang and J. Shu, On the distance spectrum of graphs, Linear Algebra Appl. 439 (2013), 1662–1669.
• [14] H. Lin and X. Lu, Bounds on the distance signless Laplacian spectral radius in terms of clique number, Linear Multilinear Algebra 63 (9) (2015), 1750–1759.

• [15] H. Lin and K.C. Das, Characterization of extremal graphs from distance signless Laplacian eigenvalues, Linear Algebra Appl. 500 (2016), 77–87.
• [16] H. Lin and B. Zhou, On the distance Laplacian spectral radius of graphs, Linear Algebra Appl. 475 (2015), 265–275.
• [17] H. Minc,´ Non-negative Matrices, New York: John Wiley Sons;1988.
• [18] K.L. Patra and B.K. Sahoo, Bounds for the Laplacian spectral radius of graphs, Electron. J. Graph Theory Appl. 5(2) (2017), 276–303.
• [19] H.S. Ramane and A.S. Yalnaik, Reciprocal complementary distance spectra and reciprocal complementary distance energy of line graphs of regular graphs, Electron. J. Graph Theory Appl. 3(2) (2015), 228–236.
• [20] D. Stevanovic, Distance spectral radius of trees with fixed maximum degree, ´ Electron. J. Linear Algebra 20 (2010), 168–179.
• [21] D. Stevanovic and G. Indulal, The distance spectrum and energy of the compositions of reg- ´ ular graphs, Appl. Math. Letters 22 (2009), 1136–1140.
• [22] D. Stevanovic, M. Milo ´ sevi ˇ c, P. H ´ ´ıc and M. Pokorny, Proof of a conjecture on distance energy ´ of complete multipartite graphs, MATCH Commun. Math. Comput. Chem. 70 (2013), 157– 162.
• [23] H. Weyl, Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen. Math. Ann. 71 (1912), 441–479.
• [24] R. Xing, B. Zhou and J. Li, On the distance signless Laplacian spectral radius of graphs, Linear Multilinear Algebra 62 (2014), 1377–1387.