On Laplacian and distance Laplacian spectra of generalized fan graph and a new graph class

Banerjee, Subarsha; Ganguly, Soumya

doi:10.2478/ijmce-2025-0021

Full Article

1

Introduction

Throughout the paper, G shall denote a finite, simple, and undirected graph. Let V (G) = {v₁,v₂,···, v_n} denote the set of all vertices of G, and let E(G) denote the set of all edges of G. The order of G is the number of elements in V (G). Let v_i,v_j∈V (G). We say that the vertex v_i is adjacent to v_j provided there is an edge from v_i to v_j or vice versa. If the vertices v_i and v_j are adjacent to each other, it shall be denoted by v_i ∼ v_j. The total number of vertices in G that are adjacent to a given vertex v is known as the degree of v. The join of two graphs G₁ and G₂ is is denoted by G₁ + G₂.

The adjacency matrix A(G) of G is defined as A(G) = (a_ij)_n_×_n is an n × n matrix defined as follows: $a_{i j} = \begin{array}{l} 1 & if v_{i} \sim v_{j} \\ 0 & elsewhere \end{array}$ {a_{ij}} = \left\{ {\matrix{ 1 \hfill & {{\rm{if}}{v_i} \sim {v_j}} \hfill \cr 0 \hfill & {{\rm{elsewhere}}} \hfill \cr } } \right. .

The Laplacian matrix L(G) of G is defined as L(G) = (l_ij)_n_×_n is defined as follows: $l_{i j} = \begin{array}{l} d_{i} & if i = j \\ - 1 & if v_{i} \sim v_{j} \\ 0 & elsewhere \end{array}$ {l_{ij}} = \left\{ {\matrix{ {{d_i}} \hfill & {{\bf if} i = j} \hfill \cr { - 1} \hfill & {{\rm{if}}{v_i} \sim {v_j}} \hfill \cr 0 \hfill & {{\rm{elsewhere}}} \hfill \cr } } \right. .

Here, d_i denotes the degree of the i^th vertex v_i. The Laplacian matrix L(G) of a graph G has all its eigenvalues as real numbers. Moreover, L(G) is a positive semidefinite matrix. Consequently, all the real eigenvalues of L(G) are non-negative. It is known that the summation of row entries in a Laplacian matrix is zero. Thus, the determinant of L(G) is always 0. Hence, 0 is always an eigenvalue of L(G).

A sequence of vertices and edges in a graph G is known as a walk. A walk is said to be closed if the starting vertex is the same as the ending vertex. If all the edges are different in a walk, then it is known as a trail. A path is a trail in which no vertex is repeated. A closed path is said to be a cycle. The number of edges in a path is known as the length of the path. The distance matrix of a connected graph G is defined as D(G) = (d_ij)_n_×_n, where d_ij = d(v_i,v_j) is the distance between two vertices v_i and v_j. The sum of distances from a vertex v to all other vertices of G is known as the transmission of v. The transmission of a vertex v is denoted by Tr(v). The transmission matrix of G is an n × n matrix where each diagonal entry denotes the transmission of the vertex v, and each off-diagonal entry is 0. The distance Laplacian matrix D^L(G) of a connected graph G is defined as D^L(G) = Tr(G) − D(G). It was introduced in [1]. The distance signless Laplacian matrix D^Q(G) is defined as D^Q(G) = Tr(G) + D(G). Recently, researchers have studied the two matrices extensively, for example, see [2,3,4,5,6,7,8].

Both the matrices, namely the distance Laplacian matrix and distance signless Laplacian matrix of a graph are positive semi-definite matrices. Consequently, both the matrices have non-negative eigenvalues.

Over the last few decades, various researchers have pondered whether it is possible to predict the eigenvalues of a graph by observing the structure of a graph. One way to study the given problem is to perform various graph operations and create new graphs from existing graphs. Several graph operations have been introduced by researchers till now, some of them being join of two graphs, disjoint union, Cartesian product, direct product, lexicographic product. Several variants of corona product of two graphs have also been introduced and studied by various researchers in the recent past. Readers may refer to the papers [9,10,11,12,13,14] for a detailed discussion in this regard. Moreover, researchers have determined the eigenvalues of the resulting graph operations in terms of existing graphs. Readers are suggested to see the papers [15] and [16] for more details. Recently, in [17], the authors have determined the distance Laplacian and distance signless Laplacian spectrum of generalized wheel graphs. They have also introduced a new graph class and named it the dumbbell graph. The authors continued their study on dumbbell graphs in [18]. The above works motivate us to study the Laplacian as well as the distance Laplacian spectrum of the generalized fan graph in this paper. We have also introduced a new graph class and deduced its Laplacian and the distance Laplacian spectrum.

2

Preliminaries

The following definitions and theorems will be used in the subsequent sections.

Definition 1

[19] Let M be a order n matrix defined as follows: $(\begin{array}{l} M_{11} & \dots & M_{1 t} \\ ⋮ & ⋱ & ⋮ \\ M_{t 1} & \dots & M_{t t} \end{array}) .$ \left( {\matrix{ {{M_{11}}} \hfill & \cdots \hfill & {{M_{1t}}} \hfill \cr \vdots \hfill & \ddots \hfill & \vdots \hfill \cr {{M_{t1}}} \hfill & \cdots \hfill & {{M_{tt}}} \hfill \cr } } \right). Each block M_ij has order n_i × n_j for 1 ≤ i, j ≤ t, and M is equal to its transpose. Moreover, n = n₁ + … + n_t. For 1 ≤ i, j ≤ t, let b_ij denote a matrix in which each element of b_ij is obtained by adding all the entries in M_ij and then dividing by the number of rows. The matrix B = (b_ij) so obtained is known as the quotient matrix of M. Additionally, if for each pair i, j, the sum of the entries in each row of M_ij is constant, then we call B as the equitable quotient matrix of M.

There is a relation between the set of eigenvalues of B and M, which is given by the following theorem.

Theorem 1

[19, Lemma 2.3.1] If ρ(M) is the set of eigenvalues of M, and ρ(B) is the set of eigenvalues of B, then ρ(B) is contained in ρ(M).

3

Laplacian spectra of generalized fan graph and a new graph class

We first determine the eigenvalues of Laplacian matrix of generalized fan graphs. We then introduce a new graph class and determine its Laplacian spectrum.

Definition 2

The generalized fan graph, denoted by F_m,n, is given by $F_{m, n} = {\bar{K}}_{m} + P_{n}$ {F_{m,n}} = {\bar K_m} + {P_n} , where ${\bar{K}}_{m}$ {\bar K_m} is the null graph on m vertices, and P_n is the path graph on n vertices.

To determine the Laplacian spectrum of the generalized fan graph F_m,n, we shall first require the following result from [20, Corollary 3.7].

Theorem 2

Let G₁ + G₂ denote the join of two graphs G₁ and G₂. Then $μ (G_{1} + G_{2}; x) = \frac{x (x - n_{1} - n_{2})}{(x - n_{1}) (x - n_{2})} μ (G_{1}, x - n_{2}) μ (G_{2}, x - n_{1}),$ \mu \left( {{G_1} + {G_2};x} \right) = {{x\left( {x - {n_1} - {n_2}} \right)} \over {\left( {x - {n_1}} \right)\left( {x - {n_2}} \right)}}\mu \left( {{G_1},x - {n_2}} \right)\mu \left( {{G_2},x - {n_1}} \right), where n₁ and n₂ are orders of G₁ and G₂ respectively.

Theorem 3

If m,n ≥ 2, then the Laplacian eigenvalues of F_m,n are 0 having multiplicity 1, m + n having multiplicity 1, n having multiplicity m − 1, and $m + 2 - 2 c o s \frac{π j}{n}$ m + 2 - 2cos{{\pi j} \over n} having multiplicity 1 for 1 ≤ j ≤ n − 1.

Proof

We know that the Laplacian eigenvalues of ${\bar{K}}_{m}$ {\bar K_m} are 0 having multiplicity m. Hence, $μ ({\bar{K}}_{m}; x) = x^{m}$ \mu \left( {{{\bar K}_m};x} \right) = {x^m} . Moreover, using [19, Section 1.4.4], we find that the Laplacian eigenvalues of P_n are $2 - 2 cos (\frac{π j}{n})$ 2 - 2{\rm{cos}}\left( {{{\pi j} \over n}} \right) , where 0 ≤ j ≤ n − 1. Hence, the characteristic polynomial of the Laplacian matrix of P_n is given as follows: $μ (P_{n}; x) = x \times [\prod_{j = 1}^{n - 1} (x - 2 + 2 cos \frac{π j}{n})] .$ \mu \left( {P_n ;x} \right) = x \times \left[ {\mathop \prod \limits_{j = 1}^{n - 1} {\text{}}\left( {x - 2 + 2{\text{cos}}\frac{{\pi j}}{n}} \right)} \right].

Thus, using Theorem (2), we get, $\begin{array}{l} μ (F_{m, n}; x) = \frac{x (x - m - n)}{(x - m) (x - n)} \times μ ({\bar{K}}_{m}, x - n) \times μ (P_{n}, x - m) \\ = \frac{x (x - m - n)}{(x - m) (x - n)} \times {(x - n)}^{m} \times (x - m) \times [\prod_{j = 1}^{n - 1} (x - m - 2 + 2 cos \frac{π j}{n})] \\ = x (x - m - n) \times {(x - n)}^{m - 1} \times [\prod_{j = 1}^{n - 1} (x - m - 2 + 2 cos \frac{π j}{n})] . \end{array}$ \begin{gathered} \mu \left( {F_{m,n} ;x} \right) = \frac{{x\left( {x - m - n} \right)}} {{\left( {x - m} \right)\left( {x - n} \right)}} \times \mu \left( {\bar K_m ,x - n} \right) \times \mu \left( {P_n ,x - m} \right) \hfill \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = \frac{{x\left( {x - m - n} \right)}} {{\left( {x - m} \right)\left( {x - n} \right)}} \times (x - n)^m \times \left( {x - m} \right) \times \left[ {\mathop \prod \limits_{j = 1}^{n - 1} {\text{}}\left( {x - m - 2 + 2{\text{cos}}\frac{{\pi j}} {n}} \right)} \right] \hfill \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = x\left( {x - m - n} \right) \times (x - n)^{m - 1} \times \left[ {\mathop \prod \limits_{j = 1}^{n - 1} {\text{}}\left( {x - m - 2 + 2{\text{cos}}\frac{{\pi j}} {n}} \right)} \right]. \hfill \\ \end{gathered} Hence the result follows.

We shall now introduce a new graph class and derive the Laplacian spectrum of the same. We shall denote the new graph class by 𝒩 𝒞 (F_m,n). We shall define the new graph in what follows.

Definition 3

The graph 𝒩 𝒞 (F_m,n) has 2(m + n) vertices and is obtained by connecting m vertices at the centers of two generalized fan graphs F_m,n, where m,n ≥ 2 through m-edges.

We shall now illustrate the newly defined graph class 𝒩 𝒞 (F_m,n) with an example in what follows.

Example 4

We consider m = 3 and n = 4. We have the following two graphs namely, ${\bar{K}}_{3}$ {\bar K_3} (Figure 1) and P₄ ( Figure 2). We shall first construct the generalized fan graph F_m,n.

Using ${\bar{K}}_{3}$ {\bar K_3} and P₄, the generalized fan graph F_3,4 in Figure (3) is given as follows:

Using Definition (3), the new graph class 𝒩 𝒞 (F_3,4) is given as follows (Figure 4):

We shall now illustrate the Laplacian eigenvalues of 𝒩 𝒞_m,n in what follows. It is known that the Laplacian eigenvalues of P_n are 0 and $2 (1 - cos \frac{π j}{n})$ 2\left( {1 - {\rm{cos}}{{\pi j} \over n}} \right) having multiplicity 1 for 1 ≤ j ≤ n − 1.

Theorem 5

If m,n ≥ 2, then the Laplacian eigenvalues of 𝒩 𝒞 (F_m,n) are as follows:

$2 (1 - cos \frac{π j}{n}) + m$ 2\left( {1 - {\rm{cos}}{{\pi j} \over n}} \right) + m having multiplicity 2 for 1 ≤ j ≤ n − 1,
n having multiplicity m − 1,
n + 2 having multiplicity m − 1,
$\frac{m + n}{2} \pm \frac{\sqrt{(m^{2} + 2 (m + 2) n + n^{2} - 4 m + 4) + 1}}{2}$ {{m + n} \over 2} \pm {{\sqrt {\left( {{m^2} + 2\left( {m + 2} \right)n + {n^2} - 4m + 4} \right) + 1} } \over 2} having multiplicity 1,
m + n having multiplicity 1,
0 having multiplicity 1.

Proof

We shall first index the vertices of P_n, then list the vertices of ${\bar{K}}_{m}$ {\bar K_m} . We again list the vertices of the second copy of ${\bar{K}}_{m}$ {\bar K_m} and finally list the vertices of the second copy of P_n. Thus the Laplacian matrix of 𝒩 𝒞 (F_m,n) is given as follows: $L (N C (F_{m, n})) = (\begin{matrix} L (P_{n}) + m I & - J_{n \times m} & 0_{n \times m} & 0_{n \times n} \\ - J_{m \times n} & (n + 1) I_{m \times m} & - I_{m \times m} & 0_{m \times n} \\ 0_{n \times m} & - I_{m \times m} & (n + 1) I_{m \times m} & - J_{m \times n} \\ 0_{n \times n} & 0_{n \times m} & - J_{n \times m} & L (P_{n}) + m I \end{matrix}) .$ L\left( {{\cal N}{\cal C}\left( {{F_{m,n}}} \right)} \right) = \left( {\matrix{ {L\left( {{P_n}} \right) + mI} & { - {J_{n \times m}}} & {{0_{n \times m}}} & {{0_{n \times n}}} \cr { - {J_{m \times n}}} & {\left( {n + 1} \right){I_{m \times m}}} & { - {I_{m \times m}}} & {{0_{m \times n}}} \cr {{0_{n \times m}}} & { - {I_{m \times m}}} & {\left( {n + 1} \right){I_{m \times m}}} & { - {J_{m \times n}}} \cr {{0_{n \times n}}} & {{0_{n \times m}}} & { - {J_{n \times m}}} & {L\left( {{P_n}} \right) + mI} \cr } } \right).

Now, since L(P_n) is a singular matrix, so zero will be an eigenvalue of L(P_n). The eigenvector corresponding to the eigenvalue 0 is 1 = [1,1,…, 1]^T. For a symmetric matrix, if λ_i and λ_j are two distinct eigenvalues with eigenvectors v_i and v_j respectively, then v_i and v_j are orthogonal to each other. Let λ (≠ = 0) be an eigenvalue of L(P_n) having eigenvector v. Then, 1^T v = 0.

Let v_i, 2 ≤ i ≤ m be an eigenvector corresponding to the eigenvalue $λ_{i} = 2 (1 - cos \frac{π i}{n})$ {\lambda _i} = 2\left( {1 - {\rm{cos}}{{\pi i} \over n}} \right) of P_n. Let $V_{i} = (\begin{matrix} v_{i_{n}} \\ 0_{m} \\ 0_{m} \\ 0_{n} \end{matrix})$ {\bf{V}}_{\bf{i}} = \left( {\matrix{ {{\bf{v}}_{{\bf i}_n } } \cr {{\bf 0}_m } \cr {{\bf 0}_m } \cr {{\bf 0}_n } \cr } } \right) . Now L(𝒩 𝒞 (F_m,n)) V_i = (λ_i + m)V_i. Thus, λ_i + m is an eigenvalue of L(𝒩 𝒞 (F_m,n)). Similarly, let $W_{i} = (\begin{matrix} 0_{n} \\ 0_{m} \\ 0_{m} \\ v_{i_{n}} \end{matrix})$ {\bf{W}}_{\bf{i}} = \left( {\matrix{ {{\bf 0}_n } \cr {{\bf 0}_m } \cr {{\bf 0}_m } \cr {{\bf{v}}_{{\bf i}_n } } \cr } } \right) , we observe that L(𝒩 𝒞 (F_m,n)) W_i = (λ_i +m) W_i. Thus, again, we find that λ_i +m is an eigenvalue of L(𝒩 𝒞 (F_m,n)) for 2 ≤ i ≤ m. Hence, we observe that λ_i + m is an eigenvalue of L(𝒩 𝒞 (F_m,n)) for 2 ≤ i ≤ m having multiplicity 2.

Let $X_{i} = (\begin{matrix} 0_{n} \\ v_{i_{m}} \\ v_{i_{m}} \\ 0_{n} \end{matrix})$ {\bf{X}}_{\bf{i}} = \left( {\matrix{ {{\bf 0}_n } \cr {{\bf{v}}_{{\bf{i}}_m } } \cr {{\bf{v}}_{{\bf{i}}_m } } \cr {{\bf 0}_n } \cr } } \right) .

We have $\begin{array}{l} L (𝒩 𝒞 (F_{m, n})) X_{i} \\ = (\begin{matrix} L (P_{n}) + m I & - J_{n \times m} & 0_{n \times m} & 0_{n \times n} \\ - J_{m \times n} & (n + 1) I_{m \times m} & - I_{m \times m} & 0_{m \times n} \\ 0_{n \times m} & - I_{m \times m} & (n + 1) I_{m \times m} & - J_{m \times n} \\ 0_{n \times n} & 0_{n \times m} & - J_{n \times m} & L (P_{n}) + m I \end{matrix}) (\begin{matrix} 0_{n} \\ v_{i_{m}} \\ v_{i_{m}} \\ 0_{n} \end{matrix}) \\ = (\begin{matrix} 0 \\ ((n + 1) - 1) v_{i_{m}} \\ ((n + 1) - 1) v_{i_{m}} \\ 0 \end{matrix}) \\ = (\begin{matrix} 0 \\ n v_{i_{m}} \\ n v_{i_{m}} \\ 0 \end{matrix}) \\ = n (\begin{matrix} 0 \\ v_{i_{m}} \\ v_{i_{m}} \\ 0 \end{matrix}) . \end{array}$ \eqalign{ & L\left( {{\cal N}{\cal C}\left( {{F_{m,n}}} \right)} \right){{\bf X_i}} \cr & = \left( {\matrix{ {L\left( {{P_n}} \right) + mI} & { - {J_{n \times m}}} & {{0_{n \times m}}} & {{0_{n \times n}}} \cr { - {J_{m \times n}}} & {\left( {n + 1} \right){I_{m \times m}}} & { - {I_{m \times m}}} & {{0_{m \times n}}} \cr {{0_{n \times m}}} & { - {I_{m \times m}}} & {\left( {n + 1} \right){I_{m \times m}}} & { - {J_{m \times n}}} \cr {{0_{n \times n}}} & {{0_{n \times m}}} & { - {J_{n \times m}}} & {L\left( {{P_n}} \right) + mI} \cr } } \right)\left( {\matrix{ {{{\bf 0}_n}} \cr {{\bf{v}}_{i_m } } \cr {{\bf{v}}_{i_m } } \cr {{{\bf 0}_n}} \cr } } \right) \cr & = \left( {\matrix{ 0 \cr {\left( {\left( {n + 1} \right) - 1} \right){{\bf{v}}_{\bf{i}}}_{_m}} \cr {\left( {\left( {n + 1} \right) - 1} \right){{\bf{v}}_{\bf{i}}}_{_m}} \cr 0 \cr } } \right) \cr & = \left( {\matrix{ {\bf 0} \cr {n{{\bf{v}}_{\bf{i}}}_{_m}} \cr {n{{\bf{v}}_{\bf{i}}}_{_m}} \cr {\bf 0} \cr } } \right) \cr & = n\left( {\matrix{ {\bf 0} \cr {{{\bf{v}}_{\bf{i}}}_{_m}} \cr {{{\bf{v}}_{\bf{i}}}_{_m}} \cr {\bf 0} \cr } } \right). \cr}

We thus obtain L(𝒩 𝒞 (F_m,n)) X_i = nX_i. Thus, n is an eigenvalue of L(𝒩 𝒞 (F_m,n)). Hence, we find that n is an eigenvalue of L(𝒩 𝒞 (F_m,n)) having multiplicity m − 1.

Let $Y_{i} = (\begin{matrix} 0_{n} \\ v_{i_{m}} \\ - v_{i_{m}} \\ 0_{n} \end{matrix})$ {\bf{Y}}_{\bf{i}} = \left( {\matrix{ {{\bf 0}_n } \cr {{\bf{v}}_{{\bf{i}}_m } } \cr { - {\bf{v}}_{{\bf{i}}_m } } \cr {{\bf 0}_n } \cr } } \right) . Now L(𝒩 𝒞 (F_m,n)) X_i = (n + 2) Y_i. Thus, n + 2 is an eigenvalue of L(𝒩 𝒞 (F_m,n)) having multiplicity m − 1.

Thus, we determine 2(n + m − 2) eigenvalues of L(𝒩 𝒞 (F_m,n). We shall now use Definition (1). We shall now use Theorem (1) to find the 4 remaining eigenvalues of L(𝒩 𝒞 (F_m,n). We find that they are contained in the spectrum of matrix B given as follows: $B = (\begin{matrix} m & - m & 0 & 0 \\ - n & n + 1 & - 1 & 0 \\ 0 & - 1 & n + 1 & - n \\ 0 & 0 & - m & m \end{matrix}) .$ B = \left( {\matrix{ m & { - m} & 0 & 0 \cr { - n} & {n + 1} & { - 1} & 0 \cr 0 & { - 1} & {n + 1} & { - n} \cr 0 & 0 & { - m} & m \cr } } \right). The characteristic polynomial of B is : $Θ (B, x) = x^{4} + (- 2 m - 2 n - 2) x^{3} + (m^{2} + 2 m n + n^{2} + 4 m + 2 n) x^{2} + (- 2 m^{2} - 2 m n) x .$ {\rm{\Theta }}\left( {B,x} \right) = {x^4} + \left( { - 2m - 2n - 2} \right){x^3} + \left( {{m^2} + 2mn + {n^2} + 4m + 2n} \right){x^2} + \left( { - 2{m^2} - 2mn} \right)x.

On solving Θ(B,x) = 0, we obtain the required result.

Corollary 5.1

The Laplacian spectrum of the usual fan graph F_1,n consists of $2 (1 - c o s \frac{π j}{n}) + 1$ 2\left( {1 - cos{{\pi j} \over n}} \right) + 1 having multiplicity 2 for 1 ≤ j ≤ n − 1, and $\frac{1 + n}{2} \pm \frac{\sqrt{n^{2} + 6 n + 2}}{2}$ {{1 + n} \over 2} \pm {{\sqrt {{n^2} + 6n + 2} } \over 2} , 1 + n, 0 each having multiplicity 1.

Proof

The proof follows from Theorem (5) by putting m = 1.

4

Distance Laplacian spectrum of generalized fan graph and a new graph class

In this section, we evaluate the distance Laplacian spectrum of the generalized fan graph. We then determine the distance Laplacian spectrum of the new graph class that was introduced in the previous section. To determine the distance Laplacian spectrum of the generalized fan graph, we shall need the given theorem.

Theorem 6

Let G₁ be a graph on n₁ vertices having Laplacian eigenvalues 0 = λ₁ ≤ λ₂ ≤ … λ_n₁ and G₂ be a graph on n₂ vertices having Laplacian eigenvalues 0 = µ₁ ≤ µ₂ ≤ … ≤ µ_n₂. Then the distance Laplacian spectrum of G₁ +G₂ consists of n₂ +2n₁ −λ_i having multiplicity 1 for 2 ≤ i ≤ n₁, n₁ +2n₂ −µ_i having multiplicity 1 for 2 ≤ j ≤ n₂, and 0,n₁ + n₂ having multiplicity 1.

Proof

We shall first index the vertices of the graph G₁. We then index the vertices of the graph G₂. We have: $D^{L} (G_{1} + G_{2}) = (\begin{matrix} D^{L_{1}} & - J_{n_{1} \times n_{2}} \\ - J_{n_{1} \times n_{2}} & D^{L_{2}} \end{matrix}) .$ {D^L}\left( {{G_1} + {G_2}} \right) = \left( {\matrix{ {{D^{{L_1}}}} & { - {J_{{n_1} \times {n_2}}}} \cr { - {J_{{n_1} \times {n_2}}}} & {{D^{{L_2}}}} \cr } } \right).

Here, $\begin{array}{l} D^{L_{1}} = T r (G_{1}) - D (G_{1}) \\ = T r (G_{1}) + A (G_{1}) - 2 J_{n_{1} \times n_{1}} + 2 I_{n_{1} \times n_{1}} \\ = ((n_{2} + 2 (n_{1} - 1)) I_{n_{1} \times n_{1}}) - Deg (G_{1}) \\ + A (G_{1}) - 2 J_{n_{1} \times n_{1}} + 2 I_{n_{1} \times n_{1}} \\ = ((n_{2} + 2 (n_{1} - 1) + 2) I_{n_{1} \times n_{1}}) - Deg (G_{1}) + A (G_{1}) - 2 J_{n_{1} \times n_{1}} \\ = ((n_{2} + 2 n_{1}) I_{n_{1} \times n_{1}}) - Deg (G_{1}) + A (G_{1}) - 2 J_{n_{1} \times n_{1}} \\ = ((n_{2} + 2 n_{1}) I_{n_{1} \times n_{1}}) - 2 J_{n_{1} \times n_{1}} - L (G_{1}), \end{array}$ \eqalign{ & {D^{{L_1}}} = Tr\left( {{G_1}} \right) - D\left( {{G_1}} \right) \cr & \,\,\,\,\,\,\,\, = Tr\left( {{G_1}} \right) + A\left( {{G_1}} \right) - 2{J_{{n_1} \times {n_1}}} + 2{I_{{n_1} \times {n_1}}} \cr & \,\,\,\,\,\,\,\, = \left( {\left( {{n_2} + 2\left( {{n_1} - 1} \right)} \right){I_{{n_1} \times {n_1}}}} \right) - {\rm{Deg}}\left( {{G_1}} \right) \cr & \,\,\,\,\,\,\,\, + A\left( {{G_1}} \right) - 2{J_{{n_1} \times {n_1}}} + 2{I_{{n_1} \times {n_1}}} \cr & \,\,\,\,\,\,\,\, = \left( {\left( {{n_2} + 2\left( {{n_1} - 1} \right) + 2} \right){I_{{n_1} \times {n_1}}}} \right) - {\rm{Deg}}\left( {{G_1}} \right) + A\left( {{G_1}} \right) - 2{J_{{n_1} \times {n_1}}} \cr & \,\,\,\,\,\,\,\, = \left( {\left( {{n_2} + 2{n_1}} \right){I_{{n_1} \times {n_1}}}} \right) - {\rm{Deg}}\left( {{G_1}} \right) + A\left( {{G_1}} \right) - 2{J_{{n_1} \times {n_1}}} \cr & \,\,\,\,\,\,\,\, = \left( {\left( {{n_2} + 2{n_1}} \right){I_{{n_1} \times {n_1}}}} \right) - 2{J_{{n_1} \times {n_1}}} - L\left( {{G_1}} \right), \cr} and, $\begin{array}{l} D^{L_{2}} = T r (G_{2}) - D (G_{2}) \\ = ((n_{1} + 2 n_{2}) I_{n_{2} \times n_{2}}) - 2 J_{n_{2} \times n_{2}} - L (G_{2}) . \end{array}$ \eqalign{ & {D^{{L_2}}} = Tr\left( {{G_2}} \right) - D\left( {{G_2}} \right) \cr & \,\,\,\,\,\,\,\, = \left( {\left( {{n_1} + 2{n_2}} \right){I_{{n_2} \times {n_2}}}} \right) - 2{J_{{n_2} \times {n_2}}} - L\left( {{G_2}} \right). \cr}

We know that the Laplacian matrix L(G₁) is a singular matrix having a determinant as 0. Moreover, since the sum of the entries of each row is 0, so 0 will be an eigenvalue of L(G₁). Hence, we have L(G₁) 1 = L(G₁)[1,1,…, 1]^T = 0. Let λ_i be a non-zero eigenvalue of L(G₁) whose eigenvector is v_i, 2 ≤ i ≤ n. Moreover, 1^T v_i = 0.

Let $V_{i} = (\begin{matrix} v_{i_{n_{1}}} \\ 0_{n_{2}} \end{matrix})$ {\bf{V}}_{\bf{i}} = \left( {\matrix{ {{\bf{v}}_{{\bf{i}}_{n_1 } } } \cr {\bf {0}_{n_\bf {2} } } \cr } } \right) . We obtain, $\begin{array}{l} D^{L} (G_{1} + G_{2}) V_{i} \\ = (\begin{matrix} D^{L_{1}} & - J_{n_{1} \times n_{2}} \\ - J_{n_{2} \times n_{1}} & D^{L_{2}} \end{matrix}) (\begin{matrix} v_{i_{n_{1}}} \\ 0_{n_{2}} \end{matrix}) \\ = (\begin{matrix} D^{L_{1}} v_{i} \\ 0 \end{matrix}) \\ = (\begin{matrix} (((n_{2} + 2 n_{1}) I_{n_{1} \times n_{1}}) - 2 J_{n_{1} \times n_{1}} - L (G_{1})) v_{i} \\ 0 \end{matrix}) \\ = (\begin{matrix} (n_{2} + 2 n_{1}) v_{i} - λ_{i} v_{i} \\ 0 \end{matrix}) \\ = (\begin{matrix} (n_{2} + 2 n_{1} - λ_{i}) v_{i} \\ 0 \end{matrix}) \\ = (n_{2} + 2 n_{1} - λ_{i}) V_{i} . \end{array}$ \eqalign{ & {D^L}\left( {{G_1} + {G_2}} \right){{\bf{V}}_{\bf{i}}} \cr & = \left( {\matrix{ {{D^{{L_1}}}} & { - {J_{{n_1} \times {n_2}}}} \cr { - {J_{{n_2} \times {n_1}}}} & {{D^{{L_2}}}} \cr } } \right)\left( {\matrix{ {{{\bf{v}}_{\bf{i}}}_{{n_1}}} \cr {{{\bf 0}_{{n_2}}}} \cr } } \right) \cr & = \left( {\matrix{ {{D^{{L_1}}}{{\bf{v}}_{\bf{i}}}} \cr {\bf 0} \cr } } \right) \cr & = \left( {\matrix{ {\left( {\left( {\left( {{n_2} + 2{n_1}} \right){I_{{n_1} \times {n_1}}}} \right) - 2{J_{{n_1} \times {n_1}}} - L\left( {{G_1}} \right)} \right){{\bf{v}}_{\bf{i}}}} \cr {\bf 0} \cr } } \right) \cr & = \left( {\matrix{ {\left( {{n_2} + 2{n_1}} \right){{\bf{v}}_{\bf{i}}} - {\lambda _i}{{\bf{v}}_{\bf{i}}}} \cr {\bf 0} \cr } } \right) \cr & = \left( {\matrix{ {\left( {{n_2} + 2{n_1} - {\lambda _i}} \right){{\bf{v}}_{\bf{i}}}} \cr {\bf 0} \cr } } \right) \cr & = \left( {{n_2} + 2{n_1} - {\lambda _i}} \right){{\bf{V}}_{\bf{i}}}. \cr}

Thus, if λ_i is an eigenvalue of L(G₁) for 2 ≤ i ≤ n₁, we find that n₂ +2n₁ −λ_i is an eigenvalue of D^L(G₁ +G₂). This provides us with n₁ − 1 distance Laplacian eigenvalues of G₁ + G₂.

Let µ_j be an eigenvalue of L(G₂). Let w be an eigenvector of µ_j. Using similar arguments as given above, we find that n₁ + 2n₂ −µ_i is a distance Laplacian eigenvalue of G₁ + G₂ corresponding to eigenvector W. Here, $W = (\begin{matrix} 0_{n_{1}} \\ w_{n_{2}} \end{matrix})$ {\bf{W}} = \left( {\matrix{ {{\bf 0}_{n_1 } } \cr {{\bf{w}}_{n_2 } } \cr } } \right) .

This provides us with n₁ +n₂ −2 distance Laplacian eigenvalues of G₁ +G₂. The remaining two eigenvalues of D^L(G₁ + G₂) can be obtained by using the concept of equitable partitions ( Definition 1). Since each block matrix of D^L(G₁ + G₂) has a constant row sum, we find that the equitable quotient matrix of D^L(G₁ + G₂) is given as follows: $B = (\begin{matrix} n_{2} & - n_{2} \\ - n_{1} & n_{1} \end{matrix}) .$ B = \left( {\matrix{ {{n_2}} & { - {n_2}} \cr { - {n_1}} & {{n_1}} \cr } } \right).

Since $σ (B) = (\begin{matrix} n_{1} + n_{2} & 0 \\ 1 & 1 \end{matrix})$ \sigma \left( B \right) = \left( {\matrix{ {{n_1} + {n_2}} & 0 \cr 1 & 1 \cr } } \right) , using Theorem (1), we find that the eigenvalues of D^L(G₁ + G₂) are n₂ + 2n₁ −λ_i having multiplicity 1 for 2 ≤ i ≤ n₁, n₁ + 2n₂ − µ_i having multiplicity 1 for 2 ≤ j ≤ n₂, and 0,n₁ + n₂ having multiplicity 1.

We now determine the distance Laplacian spectra of the generalized fan graph F_m,n.

Theorem 7

The spectrum of the distance Laplacian matrix of F_m,n consists of n + m having multiplicity m − 1, $m + 2 n - 2 + 2 c o s (\frac{π j}{n})$ m + 2n - 2 + 2cos\left( {{{\pi j} \over n}} \right) having multiplicity 1 for 0 ≤ j ≤ n − 1, and 0,m + n having multiplicity 1.

Proof.

We know $F_{m, n} = {\bar{K}}_{m} + P_{n}$ {F_{m,n}} = {\bar K_m} + {P_n} . Using Theorem (6), the eigenvalues of the distance Laplacian matrix of F_m,n are n + m having multiplicity m − 1, $m + 2 n - 2 + 2 cos (\frac{π j}{n})$ m + 2n - 2 + 2{\rm{cos}}\left( {{{\pi j} \over n}} \right) having multiplicity 1 for 0 ≤ j ≤ n − 1, and 0,m + n having multiplicity 1.

Corollary 7.1

The distance Laplacian spectrum of the usual fan graph F_1,n consists of $2 n - 1 + 2 c o s (\frac{π j}{n})$ 2n - 1 + 2cos\left( {{{\pi j} \over n}} \right) having multiplicity 1 for 0 ≤ j ≤ n − 1, and 0,n + 1 having multiplicity 1.

Proof.

The proof follows by substituting m = 1 in Theorem (7).

4.1

Distance Laplacian spectrum of 𝒩 𝒞 (F_m,n)

In our next theorem, we shall now determine the distance Laplacian spectrum of the new graph class 𝒩 𝒞 (F_m,n).

Theorem 8

The distance Laplacian spectrum of 𝒩 𝒞 (F_m,n) consists of:

(5n + 3m −λ_i) having multiplicity 2 for 2 ≤ i ≤ n,
3n + 5m − 4 having multiplicity m − 1,
3n + 5m − 2 having multiplicity m − 1,
$\frac{9}{2} (n + m) - 2 \pm \frac{1}{2} \sqrt{A}$ {9 \over 2}\left( {n + m} \right) - 2 \pm {1 \over 2}\sqrt A , where A = 24n + 9n² − 14nm − 24m + 9m² + 16, having multiplicity 1,
3(n + m) having multiplicity 1, and
0 having multiplicity 1.

Proof.

We shall first index the vertices of P_n, then list the vertices of ${\bar{K}}_{m}$ {\bar K_m} . We again list the vertices of the second copy of ${\bar{K}}_{m}$ {\bar K_m} and finally list the vertices of the second copy of P_n. We have: $\begin{array}{l} D^{L} (𝒩 𝒞 (F_{m, n})) \\ = (\begin{matrix} D^{L_{1}} & - J_{n \times m} & - 2 J_{n \times m} & - 3 J_{n \times m} \\ - J_{m \times n} & D^{L_{2}} & - {(3 J - 2 I)}_{m \times m} & - 2 J_{m \times n} \\ - 2 J_{m \times n} & - {(3 J - 2 I)}_{m \times m} & D^{L_{2}} & - J_{m \times n} \\ - 3 J_{n \times n} & - 2 J_{n \times m} & - J_{n \times m} & D^{L_{1}} \end{matrix}) . \end{array}$ \eqalign{ & D^L \left( {{\cal N}{\cal C}\left( {F_{m,n} } \right)} \right) \cr & = \left( {\matrix{ {D^{L_1 } } & { - J_{n \times m} } & { - 2J_{n \times m} } & { - 3J_{n \times m} } \cr { - J_{m \times n} } & {D^{L_2 } } & { - (3J - 2I)_{m \times m} } & { - 2J_{m \times n} } \cr { - 2J_{m \times n} } & { - (3J - 2I)_{m \times m} } & {D^{L_2 } } & { - J_{m \times n} } \cr { - 3J_{n \times n} } & { - 2J_{n \times m} } & { - J_{n \times m} } & {D^{L_1 } } \cr } } \right). \cr}

Here, $\begin{array}{l} D^{L_{1}} = (5 n + 3 m) I_{n} - 2 J_{n \times n} - L (G_{1}), and \\ D^{L_{2}} = (3 n + 5 m - 2) I_{m} - 2 J_{m \times m} . \end{array}$ \eqalign{ & {D^{{L_1}}} = \left( {5n + 3m} \right){I_n} - 2{J_{n \times n}} - L\left( {{G_1}} \right),{\rm{and}} \cr & {D^{{L_2}}} = \left( {3n + 5m - 2} \right){I_m} - 2{J_{m \times m}}. \cr}

Assuming λ_i to be an eigenvalue of L(P_n) with eigenvector v_i for 2 ≤ i ≤ n, we have 1^T v_i = 0.

Considering $V_{i} = (\begin{matrix} v_{i_{n}} \\ 0_{m} \\ 0_{m} \\ 0_{n} \end{matrix})$ {\bf{V}}_{\bf{i}} = \left( {\matrix{ {{\bf{v}}_{{\bf i}_n } } \cr {{\bf 0}_m } \cr {{\bf 0}_m } \cr {{\bf 0}_n } \cr } } \right) , we obtain, $\begin{array}{l} D^{L} (N C (F_{m, n})) \\ = (\begin{matrix} D^{L_{1}} & - J_{n \times m} & - 2 J_{n \times m} & - 3 J_{n \times n} \\ - J_{m \times n} & D^{L_{2}} & - {(3 J - 2 I)}_{m \times m} & - 2 J_{m \times n} \\ - 2 J_{m \times n} & - {(3 J - 2 I)}_{m \times m} & D^{L_{2}} & - J_{m \times n} \\ - 3 J_{n \times m} & - 2 J_{n \times m} & - J_{n \times m} & D^{L_{1}} \end{matrix}) (\begin{matrix} v_{i_{n}} \\ 0_{m} \\ 0_{m} \\ 0_{n} \end{matrix}) \\ = (\begin{matrix} D^{L_{1}} v_{i} \\ 0 \\ 0 \\ 0 \end{matrix}) \\ = (\begin{matrix} ((5 n + 3 m) I_{n} - 2 J_{n \times n} - L (P_{n})) v_{i} \\ 0 \\ 0 \\ 0 \end{matrix}) \\ = (\begin{matrix} (5 n + 3 m) v_{i} - L (P_{n}) v_{i} \\ 0 \\ 0 \\ 0 \end{matrix}) \\ = (5 n + 3 m - λ_{i}) V_{i} . \end{array}$ \eqalign{ & {D^L}\left( {{\cal N}{\cal C}\left( {{F_{m,n}}} \right)} \right) \cr & = \left( {\matrix{ {{D^{{L_1}}}} & { - {J_{n \times m}}} & { - 2{J_{n \times m}}} & { - 3{J_{n \times n}}} \cr { - {J_{m \times n}}} & {{D^{{L_2}}}} & { - {{(3J - 2I)}_{m \times m}}} & { - 2{J_{m \times n}}} \cr { - 2{J_{m \times n}}} & { - {{(3J - 2I)}_{m \times m}}} & {{D^{{L_2}}}} & { - {J_{m \times n}}} \cr { - 3{J_{n \times m}}} & { - 2{J_{n \times m}}} & { - {J_{n \times m}}} & {{D^{{L_1}}}} \cr } } \right)\left( {\matrix{ {{\bf{v}}_{i_n } } \cr {{{\bf 0}_m}} \cr {{{\bf 0}_m}} \cr {{{\bf 0}_n}} \cr } } \right) \cr & = \left( {\matrix{ {{D^{{L_1}}}{{\bf{v}}_{\bf{i}}}} \cr {\bf 0} \cr {\bf 0} \cr {\bf 0} \cr } } \right) \cr & = \left( {\matrix{ {\left( {\left( {5n + 3m} \right){I_n} - 2{J_{n \times n}} - L\left( {{P_n}} \right)} \right){{\bf{v}}_{\bf{i}}}} \cr {\bf 0} \cr {\bf 0} \cr {\bf 0} \cr } } \right) \cr & = \left( {\matrix{ {\left( {5n + 3m} \right){{\bf{v}}_{\bf{i}}} - L\left( {{P_n}} \right){{\bf{v}}_{\bf{i}}}} \cr {\bf 0} \cr {\bf 0} \cr {\bf 0} \cr } } \right) \cr & = \left( {5n + 3m - {\lambda _i}} \right){{\bf{V}}_{\bf{i}}}. \cr}

Thus, we observe that (5n+3m−λ_i) becomes an eigenvalue of D^L(𝒩 𝒞 (F_m,n)) having multiplicity 1. Here, 2 ≤ i ≤ n.

Let $W_{i} = (\begin{matrix} 0_{n} \\ 0_{m} \\ 0_{m} \\ v_{i_{n}} \end{matrix})$ {\bf{W}}_{\bf{i}} = \left( {\matrix{ {{\bf 0}_n } \cr {{\bf 0}_m } \cr {{\bf 0}_m } \cr {{\bf{v}}_{{\bf i}_n } } \cr } } \right) for 2 ≤ i ≤ n. We observe that D^L(𝒩 𝒞 (F_m,n)) W_i = (5n + 3m −λ_i) W_i.

Thus, (5n + 3m −λ_i) is an eigenvalue of D^L(𝒩 𝒞 (F_m,n)) having multiplicity 1 for 2 ≤ i ≤ n. Hence we find that (5n + 3m −λ_i) is an eigenvalue of D^L(𝒩 𝒞 (F_m,n)) having multiplicity 2 for each 2 ≤ i ≤ n.

Moreover, we observe that 3n + 5m and 3n + 5m − 4 are eigenvalues of D^L(𝒩 𝒞 (F_m,n)) having multiplicity m − 1.

This gives us 2(n + m − 2) eigenvalues of D^L(𝒩 𝒞 (F_m,n)). The remaining 4 eigenvalues of D^L(𝒩 𝒞 (F_m,n)) are contained in the spectrum of B where $B = (\begin{array}{l} 3 (n + m) & - m & - 2 m & - 3 n \\ - n & 3 (n + m) - 2 & - (3 m - 2) & - 2 n \\ - 2 n & - (3 m - 2) & 3 (n + m) - 2 & - n \\ - 3 n & - 2 m & - m & 3 (n + m) \end{array}) .$ B = \left( {\matrix{ {3\left( {n + m} \right)} \hfill & { - m} \hfill & { - 2m} \hfill & { - 3n} \hfill \cr {} \hfill \cr { - n} \hfill & {3\left( {n + m} \right) - 2} \hfill & { - \left( {3m - 2} \right)} \hfill & { - 2n} \hfill \cr {} \hfill \cr { - 2n} \hfill & { - \left( {3m - 2} \right)} \hfill & {3\left( {n + m} \right) - 2} \hfill & { - n} \hfill \cr {} \hfill \cr { - 3n} \hfill & { - 2m} \hfill & { - m} \hfill & {3\left( {n + m} \right)} \hfill \cr } } \right).

The characteristic polynomial of B is x⁴ + (−12m − 12n + 4)x³ + (45m² + 98mn + 45n² − 24m − 36n)x² + (−54m³ − 186m²n − 186mn² − 54n³ + 36m² + 108mn + 72n²)x.

On solving, we find that the eigenvalues of B are $\frac{9}{2} (n + m) - 2 \pm \frac{1}{2} \sqrt{A}$ {9 \over 2}\left( {n + m} \right) - 2 \pm {1 \over 2}\sqrt A , 3(n + m) and 0 having multiplicity 1, where A = 24n + 9n² − 14nm − 24m + 9m² + 16.

5

Conclusion

In this paper, our main aim is to determine the Laplacian and the distance Laplacian spectrum of the generalized fan graph F_m,n. Moreover, we also introduce a new graph class and determine its Laplacian as well as its distance Laplacian spectrum. We illustrate our results with various examples.

We now provide the readers with a problem for future work. The matrix D_t(G) = tTr(G) + (1 −t)D(G),0 < t < 1, is known as the generalized distance matrix of a graph G.

We encourage the readers to determine the spectrum of the generalized distance matrix of the generalized fan graph as well as the new graph class introduced in this paper.

On Laplacian and distance Laplacian spectra of generalized fan graph and a new graph class

Full Article

Paradigm

My account