# Algebraic connectivity of Kronecker products of line graphs

Shivani Chauhan, A. Satyanarayana Reddy

Department of Mathematics, Shiv Nadar Institution of Eminence, India-201314
(e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Let $X$ be a tree with $n$ vertices and $L(X)$ be its line graph. In this
work, we completely characterize the trees for which the algebraic
connectivity of $L(X)\times K_{m}$ is equal to $m-1$, where $\times$ denotes
the Kronecker product. We provide a few necessary and sufficient conditions
for $L(X)\times K_{m}$ to be Laplacian integral. The algebraic connectivity of
$L(X)\times K_{m}$, where $X$ is a tree of diameter 4 and $k$-book graph is
discussed.

Keywords: Tree, line graph, Kronecker product of graph, Laplacian matrix,
algebraic connectivity.
Subject Classification (2020): 05C05, 05C76.

##  1 Introduction

The Laplacian matrix $\mathfrak{L}(X)$ of a graph $X$ is defined as
$\mathfrak{D}(X)-A(X)$, where $A(X)$ is the adjacency matrix and
$\mathfrak{D}(X)$ is the diagonal matrix with diagonal entries as the row sums
of $A(X).$ It is well known that $\mathfrak{L}(X)$ is singular and positive
semidefinite. Fiedler [10], showed that the second smallest eigenvalue of
$\mathfrak{L}(X)$ is zero if and only if $X$ is disconnected. This eigenvalue
is termed as the algebraic connectivity of graph $X$, denoted by $a(X)$, and
the corresponding eigenvector is known as the Fiedler vector. The collection
of all the eigenvalues of a matrix together with its multiplicities is known
as the spectrum of that matrix. The spectrum of the Laplacian matrix is called
Laplacian spectrum. For more information on Laplacian matrices and algebraic
connectivity one can refer to the survey article of Merris [18] and Maria [7],
respectively. The path graph, complete graph and the star graph on $n$
vertices are denoted by $P_{n},K_{n}$ and $K_{1,n-1}$, respectively. Grone et
al.[11] proved that if $X\neq K_{1,n-1}$ is a tree with $n\geq 6$ vertices,
then $a(X)<0.49.$ Also, if $X\neq K_{2}$ is a tree, then $a(X)\in(0,1]$, and
it is 1 if and only if $X=K_{1,n-1}.$

The Kronecker product $X_{1}\times X_{2}$ of graphs $X_{1}$ and $X_{2}$ is a
graph such that the vertex set is $V(X_{1})\times V(X_{2})$, vertices
$(x_{1},x_{2})$ and $(x_{1}^{\prime},x_{2}^{\prime})$ are adjacent if $x_{1}$
is adjacent to $x_{1}^{\prime}$ and $x_{2}$ is adjacent to $x_{2}^{\prime}.$
The adjacency matrix of $X_{1}\times X_{2}$ is $A(X_{1})\otimes A(X_{2})$,
where $A\otimes B$ denotes the Kronecker product of matrices $A$ and $B.$ We
use $\mathbb{I}_{n}$ and $\mathbb{J}_{n}$ to denote the identity matrix and
the matrix with all entries 1 of order $n$, respectively, and
$\mathbb{0_{m\times n}}$ denotes the null matrix. It is easy to see that

$\mathfrak{L}(X\times
K_{m})=\mathbb{J}_{m}\otimes(-A(X))+\mathbb{I}_{m}\otimes(A(X)+(m-1)\mathfrak{D}(X)).$

The structure of $\mathfrak{L}(X\times K_{m})$ is given by

$\mathfrak{L}(X\times
K_{m})=\begin{bmatrix}(m-1)\mathfrak{D}(X)&-A(X)&-A(X)&\cdots&-A(X)\\\
-A(X)&(m-1)\mathfrak{D}(X)&-A(X)&\cdots&-A(X)\\\
-A(X)&-A(X)&(m-1)\mathfrak{D}(X)&\cdots&-A(X)\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
-A(X)&-A(X)&-A(X)&\cdots&(m-1)\mathfrak{D}(X)\end{bmatrix}.$

The spectrum of $\mathfrak{L}(X\times K_{m})$ can be obtained from the
spectrum of $(m-1)\mathfrak{L}(X)$ and $A(X)+(m-1)\mathfrak{D}(X).$ Let
$\lambda$ be an eigenvalue of $\mathfrak{L}(X)$ with its corresponding
eigenvector $v$, then for $V=(v,v,\ldots,v)^{T}$, $\mathfrak{L}(X\times
K_{m})V=(m-1)\lambda V.$ Suppose that $\lambda^{\prime}$ be an eigenvalue of
$A(X)+(m-1)\mathfrak{D}(X)$ with corresponding eigenvector $v^{\prime}.$ Then

$\\{(v^{\prime},-v^{\prime},\mathbb{0_{n\times 1}},\mathbb{0_{n\times
1}},\ldots,\mathbb{0_{n\times 1}})^{T},(v^{\prime},\mathbb{0_{n\times
1}},-v^{\prime},\mathbb{0_{n\times 1}},\ldots,\mathbb{0_{n\times
1}})^{T},\ldots,(v^{\prime},\mathbb{0_{n\times 1}},\mathbb{0_{n\times
1}},\ldots,-v^{\prime})^{T}\\}$

are $m-1$ dimensional linearly independent eigenvectors of
$\mathfrak{L}(X\times K_{m}).$ As the sum of the multiplicities of the
obtained eigenvalues equals the number of vertices in $X\times K_{m}$, it
shows that the union of the spectrum of $A(X)+(m-1)\mathfrak{D}(X)$ and
$(m-1)\mathfrak{L}(X)$ with multiplicity $m-1$ and 1 respectively, yields the
spectrum of $\mathfrak{L}(X\times K_{m}).$ For the sake of convenience, we
denote the matrix $A(X)+(m-1)\mathfrak{D}(X)$ by $Q_{m-1}(X)$ or simply
$Q_{m-1}.$ One can see that $Q_{1}(X)$ is the signless Laplacian matrix of the
graph $X.$ For more information about $Q_{1}$ one can refer [2, 3, 4]. We
illustrate the above process by computing the spectrum of $K_{n-1}\times
K_{m}$ in Example 1.

######  Example 1.

The eigenvalues of $\mathfrak{L}(K_{n-1}\times K_{m})$ are given by the union
of spectra of $\mathbb{J}_{n-1}+((m-1)(n-2)-1)\mathbb{I}_{n-1}$ and
$(m-1)(-\mathbb{J}_{n-1}+(n-1)\mathbb{I}_{n-1}).$ The eigenvalues of
$\mathbb{J}_{n}$ are $0$ and $n$ with multiplicity $n-1$ and $1,$
respectively. It is easy to check that the eigenvalues of
$\mathfrak{L}(K_{n-1}\times K_{m})$ are $0,(m-1)(n-2)-1,n+(m-1)(n-2)-2$ and
$(n-1)(m-1).$ Therefore, $a(K_{n-1}\times K_{m})=(n-2)(m-1)-1.$

If $X$ is a tree, we denote the graph $L(X)\times K_{m}$ by ${\beta_{m}}(X)$,
where $L(X)$ denotes the line graph of $X.$ The objective of this paper is to
compute $a({\beta_{m}}(X)).$ Note that,
$a({\beta_{m}}(X))=min\\{(m-1)a(L(X)),q_{min}^{m-1}(L(X))\\},$ where
$q_{min}^{m-1}(Y)$ denotes the smallest eigenvalue of $Q_{m-1}(Y).$ Hence, the
problem boils down to computing $a(L(X))$ and $q_{min}^{m-1}(L(X)).$ From
Example 1, $a({\beta_{m}}(K_{1,n-1}))\linebreak=(n-2)(m-1)-1$ as
$L(K_{1,n-1})=K_{n-1}.$ The converse is also true i.e., if
$a({\beta_{m}}(X))=(n-2)(m-1)-1$, then $X=K_{1,n-1}.$ It is well known that
the line graph of a tree has a cut vertex and $a(X)\leq\kappa(X)$, where
$X\neq K_{n}$ and $\kappa(X)$ denotes the vertex connectivity of $X.$ This
implies $a(L(X))\leq 1.$ The spectrum of $(m-1)\mathfrak{L}(L(X))$ is
contained in the spectrum of $\mathfrak{L}({\beta_{m}}(X))$, therefore $0\leq
a({\beta_{m}}(X))\leq m-1.$ Thus one can see that there is a large gap between
$a({\beta_{m}}(K_{1,n}))$ and $a({\beta_{m}}(X)),$ where $X$ is different from
$K_{1,n-1}$.

We know that $a({\beta_{m}}(X))\geq 0.$ By the result of Imrich and Klav̌zar
[13], which states that $X_{1}\times X_{2}$ is connected if and only if both
$X_{1}$ and $X_{2}$ are connected and at least one of them is non-bipartite,
we deduce that $a({\beta_{m}}(X))=0$ if and only if $X=P_{n}$ and $m=2.$ So we
define,

$\mathfrak{S}_{m}=\\{X\mid\mbox{$X$ is a tree and}\;0<a({\beta_{m}}(X))\leq
m-1\\}.$

In Figure 1, we demonstrate the structure of
$X,L(X),\beta_{3}(X),\beta_{4}(X)$ and $\beta_{5}(X)$, where $X=P_{4}.$ More
examples of $a({\beta_{m}}(X))$ can be found in Table 2.

|  |  |  |
---|---|---|---|---
Figure 1: $P_{4},L(P_{4}),\beta_{3}(P_{4}),\beta_{4}(P_{4})$ and
$\beta_{5}(P_{4})$

This paper is organized as follows: In Section 2, we explore all
$X\in\mathfrak{S}_{m}$ for which $a({\beta_{m}}(X))=m-1$, and necessary and
sufficient conditions for ${\beta_{m}}(X)$ to be Laplacian integral is given.
In Section 3, we compute the algebraic connectivity of $L(X)\times K_{m},$
where $X$ is a tree of diameter 4 and $k$-book graph.

##  2 Main results

Let $T(k,s,t)$ denotes the tree with $n=s+t+k+1$ vertices, constructed by
taking a path on vertices $\\{1,2,\ldots,k+1\\}$, adding $s$ and $t$ pendant
vertices adjacent to vertex $1$ and $k+1$, respectively. In Figure 2,
$T(2,3,2)$ is given. In this section, it is proved that if
$X\in\mathfrak{S}_{m}$, then $a({\beta_{m}}(X))=m-1$ if and only if $X$ is a
$T(1,s,t)$, where $s,t\geq 2$. As a consequence, we find all $X$ for which
${\beta_{m}}(X)$ is the Laplacian integral. We observed that $L(T(k,s,t))$ is
a restricted graph. Hence, we defined a restricted graph and classified all
restricted graphs $X$ for which $a(X\times K_{m})=m-1.$ We mention a few
results that will be used later.

123 |  |
---|---|---
Figure 2: $T(2,3,2),L(T(2,3,2))$ and $\beta_{2}(T(2,3,2))$

######  Proposition 2.

[14, Corollary 2.1] Let $X$ be a connected graph with a cut vertex $v.$ Then
$a(X)=1$ if and only if $v$ is adjacent to every vertex of $X$.

######  Theorem 3.

[5, Theorem 3.3] Let $X=(V,E)$ be a graph with
$N_{X}(v_{1})=N_{X}(v_{2})=\cdots=N_{X}(v_{k})=\\{w_{1},w_{2},\ldots,w_{p}\\}$,
where $N_{X}(v)$ denotes the neighborhood of vertex $v$ in $X$. If $X^{+}$ is
the graph obtained from $X$ by adding any $q$ $\left(1\leq
q\leq\frac{k(k-1)}{2}\right)$ edges among $\\{v_{1},v_{2},\ldots,v_{k}\\}$,
then the eigenvalues of $\mathfrak{L}(X^{+})$ are as follows: Laplacian
eigenvalues of the graph $X$ which are equal to $p$(k-1 in number) are
incremented by $\lambda_{i}(X^{+}[G])$, $i=1,2,\ldots,k-1$ and, the remaining
eigenvalues are same, where $X^{+}[G]$ denotes the induced subgraph of $X^{+}$
with vertex set $G=\\{v_{1},v_{2},\ldots,v_{k}\\}$.

######  Example 4.

The line graph of $T(1,s,t)$ has exactly one cut vertex which is adjacent to
every vertex of $L(T(1,s,t)).$ In Figure 3, $v$ is the cut vertex of
$L(T(1,3,2)).$

|  $v$
---|---
Figure 3: $T(1,3,2),L(T(1,3,2))$

The next lemma is immediate from Proposition 2.

######  Lemma 5.

Let $X$ be a tree. Then $a(L(X))=1$ if and only if $X$ is a $T(1,s,t).$

Let $X$ be a $T(k,s,t)$ with $n$ vertices, where $k\neq 1,n\geq 7$, then
$a(L(X))<0.49.$ The line graph of $T(k,s,t)$ is a graph obtained from
$T(k-1,s,t)$ by placing all possible edges among the pendant vertices attached
at vertex $1$ and $k.$ We apply Theorem 3 to $X$ to find the Laplacian
eigenvalues of $L(X).$ Let $V(X_{1}^{\prime})$ and $V(X_{2}^{\prime})$
contains vertices whose neighborhood is $1$ and $k,$ respectively. Consider
$X^{+}=L(X)$, so $X^{+}[X_{1}^{\prime}]=K_{s}$ and
$X^{+}[X_{2}^{\prime}]=K_{t}.$ The Laplacian eigenvalues of $K_{b}$ are 0 and
$b$. By Theorem 3, those eigenvalues of $X$ which are equal to $1$ ($s+t-2$ in
number), $s-1$ and $t-1$ number of eigenvalues are incremented by $s$ and $t$,
respectively. The rest of the eigenvalues are the same as $\mathfrak{L}(X)$.
This implies $a(L(X))=a(T(k-1,s,t))$ and, it is known that
$a(T(k-1,s,t))<0.49.$

######  Theorem 6.

Let $X\in\mathfrak{S}_{m}.$ Then $a({\beta_{m}}(X))=m-1$ if and only if $X$ is
a $T(1,s,t)$, where $s,t\geq 2$.

###### Proof.

Suppose that $a({\beta_{m}}(X))=m-1$. We know

$a({\beta_{m}}(X))=min\\{(m-1)a(L(X)),q_{min}^{m-1}(L(X))\\}.$

Since $a(L(X))\leq 1$, this implies that $a(L(X))=1$ and
$q_{min}^{m-1}(L(X))\geq m-1.$ By Lemma 5, $X$ is a $T(1,s,t).$ To prove
$s,t\geq 2$, it is sufficient to prove that if $s=1$ and $t\geq 1$, then
$q_{min}^{m-1}L(X)<m-1.$

$Case1:$ Let $s=t=1.$ The characterstic polynomial for $Q_{m-1}(P_{3})$ is
$\phi_{\lambda}=\lambda^{3}-4(m-1)\lambda^{2}+(5(m-1)^{2}-2)\lambda-2m(m-1)(m-2)=0.$
Its roots are $m-1,\frac{3(m-1)\pm\sqrt{m^{2}-2m+9}}{2}.$ It can be easily
observed that, $\frac{3(m-1)-\sqrt{(m-1)^{2}+8}}{2}<m-1.$

$Case2:$ Let $s=1$ and $t>1$, then we show that $q_{min}^{m-1}(L(X))<m-1.$ To
prove this we choose the principal submatrix $\begin{bmatrix}(m-1)(t+1)&1\\\
1&(m-1)\end{bmatrix}$ of

$Q_{m-1}=\begin{bmatrix}(m-1)(1+t)&1&\mathbb{1_{1\times t}}\\\
1&m-1&\mathbb{0_{1\times(n-3)}}\\\ \mathbb{1_{t\times
1}}&\mathbb{0_{(n-3)\times
1}}&\mathbb{J}_{t}+((m-1)t-1)\mathbb{I}_{t}\end{bmatrix},$

where $\mathbb{1_{m\times n}}$ denotes the $m\times n$ matrix with all entries
equal to $1.$ Its eigenvalues are

$\frac{(m-1)(t+2)\pm\sqrt{t^{2}(m-1)^{2}+4}}{2}.$

By Cauchy’s interlacing theorem,
$q_{min}^{m-1}(L(X))\leq\frac{(m-1)(t+2)-\sqrt{t^{2}(m-1)^{2}+4}}{2}<\frac{(t+2)(m-1)-t(m-1)}{2}=m-1.$

Conversely, suppose that $X$ is a $T(1,s,t)$, where $s,t\geq 2.$ We first show
$a(\beta_{2}(X))=1.$ The eigenvalues of $\mathfrak{L}(\beta_{2}(X))$ is given
by the union of spectra of $\mathfrak{L}(L(X))$ and $Q_{1}(L(X)).$ By Lemma 5,
$a(L(X))=1$. The matrix $Q_{1}$ has the following form

$Q_{1}=\begin{bmatrix}s+t&\mathbb{1_{1\times s}}&\mathbb{1_{1\times t}}\\\
\mathbb{1_{s\times 1}}&U_{1}&\mathbb{0_{s\times(n-s-2)}}\\\ \mathbb{1_{t\times
1}}&\mathbb{0_{t\times(n-t-2)}}&V_{1}\end{bmatrix},$

where $U_{1}=\mathbb{J}_{s}+(s-1)\mathbb{I}_{s}$ and
$V_{1}=\mathbb{J}_{t}+(t-1)\mathbb{I}_{t}.$ Let $v_{i},$ where $1\leq i\leq
s-1$ be an eigenvector corresponding to eigenvalue $s-1$ of $U_{1}.$ A simple
check shows that $Q_{1}V_{i}=(s-1)V_{i}$, where $V_{i}=\begin{pmatrix}0\\\
v_{i}\\\ \mathbb{0}_{t\times 1}\end{pmatrix}.$ Similarly, it can be seen that
$t-1$ is an eigenvalue of $Q_{1}$ with multiplicity $t-1.$ Let $s\geq t$, for
$v=(t-s,\underbrace{1,\ldots,1}_{s},\underbrace{-1,\ldots,-1}_{t})$, note that
$Q_{1}v=(s+t-1)v$. Suppose that $\lambda_{t}$ and $\lambda_{t}^{\prime}$ are
the remaining eigenvalues. Thus we have Equation 1

$\lambda_{t}+\lambda_{t}^{\prime}=2(s+t)-1.$ (1)

Since $Tr(Q_{1}^{2})=\sum_{i=1}^{n}\lambda_{i}^{2}$, we obtain Equation 2

$\lambda_{t}\lambda_{t}^{\prime}=-2(s+t)+4st.$ (2)

From Equation 1 and 2, we have
$\lambda_{t}^{2}-(2(s+t)-1)\lambda_{t}+(-2s-2t+4st)=0.$ Hence,
$\lambda_{t}=(s+t)-\frac{1}{2}\pm\frac{\sqrt{4(t-s)^{2}+4(s+t)+1}}{2}.$ For
$s,t\geq 2$, all the eigenvalues of $Q_{1}$ are greater than or equal to $1.$
Therefore, $a(\beta_{2}(X))=1$.

Now we prove for $m\geq 3.$ By Theorem 4.3.1 of [12],

$q_{min}^{1}L(X)+(m-2)\delta(L(X))\leq q_{min}^{m-1}(L(X)),$

where $\delta(X)$ denotes the minimum of vertex degrees of $X.$ We have
$q_{min}^{1}L(X)\geq 1.$ Since $\delta(L(X))\geq 2$, then $2m-3\leq
q_{min}^{m-1}(L(X)).$ Thus, $q_{min}^{m-1}(L(X))\geq m-1.$ The proof is
complete. ∎

Theorem 6 will help us to find graph $X$ for which ${\beta_{m}}(X)$ is
Laplacian integral. Recall, a graph is Laplacian integral if the spectrum of
its Laplacian matrix consists entirely of integers. A lot of work has been
done on investigating the class of Laplacian integral graphs (see [9, 15, 16,
17]). The spectrum of ${\beta_{m}}(X)$ consists of eigenvalues of
$(m-1)\mathfrak{L}(L(X)).$ We know $0<a(L(X))\leq 1,$ therefore by Theorem 6,
$X$ is a $T(1,s,t)$, where $s,t\geq 2.$ Theorem 6 gives a necessary condition
for ${\beta_{m}}(X)$ to be Laplacian integral. Also, the proof of converse
part of Theorem 6 shows that, let $X\in\mathfrak{S}_{m}$, then $\beta_{2}(X)$
is Laplacian integral if and only if $X$ is a $T(1,s,t)$ tree, where $s,t\geq
2$ and $4(s-t)^{2}+4(s+t)+1$ is a perfect square. In Corollary 7, we
generalise it for $m.$

######  Corollary 7.

Let $X\in\mathfrak{S}_{m}.$ Then ${\beta_{m}}(X)$ is Laplacian integral if and
only if $X$ is a $T(1,s,t)$, where $s,t\geq 2$ and
$\lambda^{3}-a\lambda^{2}+b\lambda-c=0$ has integral roots, where

$a=(s+t)(2m-1)-2$ $b=m(m-1)s^{2}+m(m-1)t^{2}-(3m-1)s-(3m-1)t+m(3m-2)st+1$
$c=m(-m+1)s^{2}+m(-m+1)t^{2}+ms+mt-2m^{2}st+m^{2}(m-1)s^{2}t+m^{2}(m-1)st^{2}.$

###### Proof.

We first give the spectrum of $\mathfrak{L}(L(X)),$ where $X=T(1,s,t).$ The
Laplacian matrix of $L(X)$ can be expressed in the following form

$\begin{bmatrix}s+t&\mathbb{-1_{1\times s}}&\mathbb{-1_{1\times t}}\\\
\mathbb{-1_{s\times 1}}&U&\mathbb{0_{s\times(n-s-2)}}\\\ \mathbb{-1_{t\times
1}}&\mathbb{0_{t\times(n-t-2)}}&V\end{bmatrix},$

where $U=-\mathbb{J}_{s}+(s+1)\mathbb{I}_{s}$,
$V=-\mathbb{J}_{t}+(t+1)\mathbb{I}_{t}.$

It is easy to see that $1,s+1,t+1$ and $s+t-1$ are eigenvalues of
$\mathfrak{L}(L(X))$ with multiplicity $1,s-1,t-1$ and 1, respectively. The
remaining eigenvalues are the eigenvalues of the following matrix

$Q=Q_{m-1}(L(X))=\begin{bmatrix}(m-1)(s+t)&\mathbb{1_{1\times
s}}&\mathbb{1_{1\times t}}\\\ \mathbb{1_{s\times
1}}&\mathbb{J}_{s}+((m-1)s-1)\mathbb{I}_{s}&\mathbb{0_{s\times(n-s-2)}}\\\
\mathbb{1_{t\times
1}}&\mathbb{0_{t\times(n-t-2)}}&\mathbb{J}_{t}+((m-1)t-1)\mathbb{I}_{t}\end{bmatrix}.$

It can be easily seen that $(m-1)s-1$ and $(m-1)t-1$ are eigenvalues of
$Q_{m-1}(L(X))$ with multiplicity $s-1$ and $t-1$, respectively. Let
${\lambda_{1}},{\lambda_{2}}$ and ${\lambda_{3}}$ be the remaining three
eigenvalues of $Q_{m-1}$. As the trace of a matrix is equal to the sum of its
eigenvalues, we have Equation 3

${\lambda_{1}}+{\lambda_{2}}+{\lambda_{3}}=(2m-1)(s+t)-2.$ (3)

Since
$Tr(Q^{2})=Tr(A^{2})+(m-1)^{2}Tr(\mathfrak{D}^{2})=s(s+1)+t(t+1)+(m-1)^{2}((s+t)^{2}+s^{3}+t^{3})$
and
$Tr(Q^{2})=\sum_{i=1}^{3}\lambda_{i}^{2}+((m-1)s-1)^{2}(s-1)+((m-1)t-1)^{2}(t-1)$,
we get Equation 4

$\sum_{i=1}^{3}\lambda_{i}^{2}=(1+2(m-1)^{2}+2(m-1))s^{2}+(1+2(m-1)^{2}+2(m-1))t^{2}-2(m-1)s-2(m-1)t+2(m-1)^{2}st+2.$
(4)

Now using Equation 4 and the algebraic identity of
$({\lambda_{1}}+{\lambda_{2}}+{\lambda_{3}})^{2}$, we deduce Equation 5

${\lambda_{1}}{\lambda_{2}}+{\lambda_{2}}{\lambda_{3}}+{\lambda_{3}}{\lambda_{1}}=m(m-1)s^{2}+m(m-1)t^{2}-(3m-1)s-(3m-1)t+m(3m-2)st+1.$
(5)

A simple computation reveals that
$Tr(Q^{3})=Tr(A^{3})+(m-1)^{3}Tr(\mathfrak{D}^{3})+3(m-1)Tr(\mathfrak{D}^{2})$.
Furthermore, $Tr(Q^{3})$ is equal to
$\sum_{i=1}^{3}\lambda_{i}^{3}+((m-1)s-1))^{3}(s-1)+((m-1)t-1))^{3}(t-1)$.
Substitute Equation 3 and 5 into the algebraic identity
$\sum_{i=1}^{3}\lambda_{i}^{3}-3{\lambda_{1}}{\lambda_{2}}{\lambda_{3}}=({\lambda_{1}}+{\lambda_{2}}+{\lambda_{3}})(({\lambda_{1}}+{\lambda_{2}}+{\lambda_{3}})^{2}-3({\lambda_{1}}{\lambda_{2}}+{\lambda_{2}}{\lambda_{3}}+{\lambda_{3}}{\lambda_{1}}))$
and obtain Equation 6

${\lambda_{1}}{\lambda_{2}}{\lambda_{3}}=m(-m+1)s^{2}+m(-m+1)t^{2}+ms+mt-2m^{2}st+m^{2}(m-1)s^{2}t+m^{2}(m-1)st^{2}.$
(6)

From Equation 3, 5 and 6, the proof is complete. ∎

In the next result, all restricted graphs $X$ are provided that have
$a(X\times K_{m})=m-1.$ Before that, we state a couple of results and recall
some terminologies from Bapat’s paper [1] as it will be required to prove
Theorem 10. A restricted graph is a graph with the restriction that each block
can have at most two cut vertices. For example, $L(T(k,s,t))$ is a restricted
graph. A block graph is a graph in which each block is complete. Let $X$ be a
connected restricted graph with blocks $B_{1},B_{2},\ldots,B_{k}.$ Replace the
block $B_{i}$ by a path $P_{i}=[u_{i},v_{i}]$ on two vertices such that
$B_{i},B_{j}$ have a common vertex if and only if $P_{i},P_{j}$ have a common
vertex. The resulting graph is a tree that we call the block structure of $X.$

######  Definition 8.

[8] Fix $\delta\geq 2$ and consider the minimal family of graphs $P(\delta)$
satisfying the following properties:
(a) if $r$ is an integer and $r>\delta$, then $K_{r}\in P(\delta)$;
(b) if $H\in P(\delta)$, $r$ and $k$ are integers, $r>\delta$ and $r-2\geq
k\geq 0$, then every $k$-sum of $H$ and $K_{r}$ belongs to $P(\delta)$.
Recall, let $X_{1}$ and $X_{2}$ be vertex disjoint graphs, and let
$X_{1}^{\prime}$ be a $k$-clique of $X_{1}$ and $X_{2}^{\prime}$ be a
$k$-clique of $X_{2}$. A graph that is obtained by identifying $X_{1}$ and
$X_{2}$ is called a $k$-sum of $X_{1}$ and $X_{2}.$

######  Theorem 9.

[8, Theorem 2.6] Suppose that $\delta\geq 2$ and $X$ is a graph that has a
spanning subgraph $H\in P(\delta).$ Also, suppose that X has two vertices of
degree $\delta$ with the same closed neighborhoods. Then
$q_{min}^{1}(X)=\delta-1.$

######  Theorem 10.

Let $X$ be a connected restricted graph with blocks
$K_{s_{1}},\ldots,K_{s_{k}}$, where $k\geq 3$ and $X\times K_{m}$ is
connected. Then $a(X\times K_{m})=m-1$ if and only if $\delta(X)\geq 2$ and
the block structure of $X$ is a star graph.

###### Proof.

If $a(X\times K_{m})=m-1$, then $a(X)=1$ and $q_{min}^{m-1}(X)\geq(m-1).$ By
Proposition 2, the block structure of $X$ is a star graph. Note that $X$ has
exactly one cut vertex. Suppose that there exists a pendant vertex (say
$v_{n}$), and $v_{1}$ is the cut vertex of $X$. The degree of $v_{1}$ is
$x=s_{1}+s_{2}+\cdots+s_{k-1}-k+2.$ That is,

$\begin{bmatrix}(m-1)x&1\\\ 1&(m-1)\end{bmatrix}$

is a principal submatrix of $Q_{m-1}.$ Its eigenvalues are
$\frac{(m-1)(x+1)\pm\sqrt{(m-1)^{2}(x-1)^{2}+4}}{2}.$ By Cauchy’s interlacing
theorem, $q_{min}^{m-1}(X)<m-1$, which is a contradiction.

Conversely, suppose that $\delta(X)\geq 2$ and the block structure of $X$ is a
star graph. By Proposition 2, $a(X)=1.$ We show that $q_{min}^{m-1}(X)>m-1$.
By hypothesis, $X$ is a graph obtained by attaching at least three complete
graphs at one vertex. Graph $X$ satisfies the hypothesis of Theorem 9, hence
$q_{min}^{1}(X)=\delta(X)-1$. By Theorem 4.3.1 of [12],
$q_{min}^{1}(X)+(m-2)\delta\leq q_{min}^{m-1}(X)$, which proves the claim. ∎

##  3 Algebraic connectivity of some classes of graphs

In this section, we describe the Laplacian spectrum and the algebraic
connectivity of some classes of graphs. We start by defining some terms that
will be used later. The graph $W(\eta,\mu)$ is a restricted graph. It is
formed by attaching ${\eta}$ copies of $K_{{\mu}}$ in a common vertex, where
${\eta}\geq 2,{\mu}\geq 3$. It is also known as windmill graph. Friendship
graphs, $W({\eta},3)$ are a special case of a windmill graph. The graph
$W^{\prime}({\eta},{\mu})$ is obtained by attaching $K_{{\mu}}$ to each vertex
of $K_{{\eta}}.$ It can be seen that $W^{\prime}({\eta},{\mu})$ is the line
graph of $T(n,{\eta};{\mu}-1,{\mu}-1,\ldots,{\mu}-1)$. The tree
$T(n,k;x_{1},x_{2},\ldots,x_{k})$ is obtained from the star graphs
$K_{1,k},K_{1,x_{1}},\ldots,K_{1,x_{k}}$, by identifying the pendant vertices
of $K_{1,k}$ and the centers of $K_{1,x_{1}},\ldots,K_{1,x_{k}}$ respectively,
where $x_{1}\geq x_{2}\geq x_{3}\geq\cdots\geq x_{k}\geq 0$, $x_{1}\geq
x_{2}>0$, $k\geq 2$ and $1+k+x_{1}+x_{2}+\cdots+x_{k}=n$ (see Figure 4). In
Figure 5, we give an example of $W(2,3)$ and $W^{\prime}(3,3).$ The $k$-book
graph, denoted by $\mathbb{B}_{k}$, is defined as the graph cartesian product
of $K_{1,k}$ with $K_{2}$. Recall that the cartesian product $X\Box Y$ of
graphs $X$ and $Y$ is a graph such that the vertex set of $X\Box Y$ is the
cartesian product $V(X_{1})\times V(X_{2})$ and two vertices $(x_{1},x_{2})$
and $(x_{1}^{\prime},x_{2}^{\prime})$ are adjacent in $X\Box Y$ if and only if
either $x_{1}=x_{1}^{\prime}$ and $x_{2}$ is adjacent to $x_{2}^{\prime}$ in
$Y$, or $x_{2}=x_{2}^{\prime}$ and $x_{1}$ is adjacent to $x_{1}^{\prime}$ in
$X.$

$v$$v_{1}$$v_{k}$$v_{2}$$\dots$$\dots$$\dots$$\dots$$x_{1}$$x_{2}$$x_{k}$ Figure 4:  | 174562389 |  |
---|---|---|---
Figure 5: $W(2,3),W^{\prime}(3,3),W(2,3)\times K_{2}$ and
$W^{\prime}(3,3)\times K_{2}$

######  Theorem 11.

The eigenvalues of the Laplacian matrix of $W({\eta},{\mu})\times K_{m}$ are

$0,m-1,{\mu}(m-1),(m-1)({\mu}{\eta}-{\eta}+1),(m-1)({\mu}-1)-1,(m-1)({\mu}-1)+{\mu}-2,\lambda_{1},\lambda_{2}\,$

where $\lambda_{1},\lambda_{2}$ are the roots of
$\lambda^{2}-((m-1)({\mu}-1)({\eta}+1)+{\mu}-2)\lambda+{\eta}({\mu}-1)((m-1)((m-1)({\mu}-1)+{\mu}-2)-1)$.

###### Proof.

The spectrum of $\mathfrak{L}(W({\eta},{\mu})\times K_{m})$ is obtained by the
union of spectra of $(m-1)\mathfrak{L}(W({\eta},{\mu}))$ and
$Q_{m-1}(W({\eta},{\mu}))$. From the structure of $W({\eta},{\mu})$, we have

$\mathfrak{L}(W({\eta},{\mu}))=\begin{bmatrix}{\eta}({\mu}-1)&-\mathbb{1_{1\times{\eta}({\mu}-1)}}\\\
-\mathbb{1_{{\eta}({\mu}-1)\times 1}}&\mathbb{I}_{{\eta}}\otimes
P\end{bmatrix},$ where $P=-\mathbb{J}_{{\mu}-1}+{\mu}\mathbb{I}_{{\mu}-1}$.
For $\lambda=1$, the corresponding linearly independent eigenvectors are as
follows

$\begin{bmatrix}0\\\ \mathbb{1_{({\mu}-1)\times 1}}\\\
-\mathbb{1_{({\mu}-1)\times 1}}\\\ \mathbb{0_{({\mu}-1)\times 1}}\\\ \vdots\\\
\mathbb{0_{({\mu}-1)\times 1}}\end{bmatrix},\begin{bmatrix}0\\\
\mathbb{1_{({\mu}-1)\times 1}}\\\ \mathbb{0_{({\mu}-1)\times 1}}\\\
-\mathbb{1_{({\mu}-1)\times 1}}\\\ \vdots\\\ \mathbb{0_{({\mu}-1)\times
1}}\end{bmatrix},\ldots,\begin{bmatrix}0\\\ \mathbb{1_{({\mu}-1)\times 1}}\\\
\mathbb{0_{({\mu}-1)\times 1}}\\\ \mathbb{0_{({\mu}-1)\times 1}}\\\ \vdots\\\
-\mathbb{1_{({\mu}-1)\times 1}}\\\ \end{bmatrix}.$

Clearly, ${\mu}$ is an eigenvalue of $P,$ let $v_{1}$ be the corresponding
eigenvector. Consider
$V_{1}=(0,v_{1},\mathbb{0_{({\mu}-1)\times
1}},\ldots,\mathbb{0_{({\mu}-1)\times 1}})^{T},$ then
$\mathfrak{L}(W({\eta},{\mu}))V_{1}={\mu}V_{1}$ and it has algebraic
multiplicity ${\eta}({\mu}-2).$ Let $\lambda$ be an eigenvalue of
$\mathfrak{L}(W({\eta},{\mu}))$ with the corresponding eigenvector

$V_{2}=(y,\mathbb{1_{({\mu}-1)\times 1}},\mathbb{1_{({\mu}-1)\times
1}},\ldots,\mathbb{1_{({\mu}-1)\times 1}})^{T}.$

Hence, we obtain equations $({\eta}({\mu}-1)-\lambda)y={\eta}({\mu}-1)$ and
$y=1-\lambda$ from $\mathfrak{L}(W({\eta},{\mu}))V_{2}=\lambda V_{2}.$ Solving
these equations, we get $\lambda^{2}-({\eta}{\mu}-{\eta}+1)\lambda=0.$ The
eigenvalues of $(m-1)\mathfrak{L}(W({\eta},{\mu}))$ are
$0,m-1,{\mu}(m-1),(m-1)({\eta}{\mu}-{\eta}+1)$ with multiplicity
$1,{\eta}-1,{\eta}({\mu}-2),1$ respectively.

The matrix $Q_{m-1}(W({\eta},{\mu}))$ has the following structure

$\begin{bmatrix}{\eta}({\mu}-1)(m-1)&\mathbb{1_{1\times{\eta}({\mu}-1)}}\\\
\mathbb{1_{{\eta}({\mu}-1)\times 1}}&\mathbb{I}_{{\eta}}\otimes
F\end{bmatrix},$

where $F=\mathbb{J}_{{\mu}-1}+((m-1)({\mu}-1)-1)\mathbb{I}_{{\mu}-1}$. The
eigenvalues of $Q_{m-1}(W({\eta},{\mu}))$ can be obtained in a way similar to
$\mathfrak{L}(W({\eta},{\mu})).$ The eigenvalues of $Q_{m-1}(W({\eta},{\mu}))$
are $(m-1)({\mu}-1)-1,(m-1)({\mu}-1)+{\mu}-2,\lambda_{1},\lambda_{2}$ with
multiplicity ${\eta}({\mu}-2),{\eta}-1,1,1$ respectively, where
$\lambda_{1},\lambda_{2}$ are the roots of
$\lambda^{2}-((m-1)({\mu}-1)({\eta}+1)+{\mu}-2)\lambda+{\eta}({\mu}-1)((m-1)((m-1)({\mu}-1)+{\mu}-2)-1).$
∎

From Theorem 10, we can conclude that $a(W({\eta},{\mu})\times K_{m})=m-1$. In
the next result, we compute $a(W^{\prime}({\eta},{\mu})\times K_{m}).$

######  Theorem 12.

The algebraic connectivity of $W^{\prime}({\eta},{\mu})\times K_{m}$, where
${\eta},{\mu}\geq 3$ is equal to

$(m-1)\left(\frac{{\mu}+{\eta}-\sqrt{({\mu}+{\eta})^{2}-4{\eta}}}{2}\right).$

###### Proof.

We first explain the spectrum of $\mathfrak{L}(W^{\prime}({\eta},{\mu}))$ and
$Q_{m-1}(W^{\prime}({\eta},{\mu})).$ By the labelling defined in Figure 5,
$\mathfrak{L}(W^{\prime}({\eta},{\mu}))=\mathbb{J}_{{\eta}}\otimes
G+\mathbb{I}_{{\eta}}\otimes(H-G),$ where $G$ is a ${\mu}\times{\mu}$ matrix
with $-1$ in $(1,1)$ position and zero elsewhere, and
$H=-\mathbb{J}_{\mu}+{\mu}\mathbb{I}_{{\mu}}+(-{\eta}+1)G.$ The spectrum of
$\mathfrak{L}(W^{\prime}({\eta},{\mu}))$ is given by the spectrum of
$H-G=-\mathbb{J}_{{\mu}}+{\mu}\mathbb{I}_{{\mu}}-{\eta}G$ and
$H+({\eta}-1)G=-\mathbb{J}_{{\mu}}+{\mu}\mathbb{I}_{{\mu}}$ with multiplicity
${\eta}-1$ and 1 respectively. It is easy to see that ${\mu}$ is an eigenvalue
of $H-G$ and its linearly independent eigenvectors are
$\\{(0,1,-1,0,\ldots,0)^{T},(0,1,0,-1,\ldots,0)^{T},\ldots,(0,1,0,0,\ldots,-1)^{T}\\}$.
Let $\lambda$ be an eigenvalue of $H-G$ with corresponding eigenvector
$v_{1}=(x,1,1,\ldots,1)^{T}$ such that $(H-G)v_{1}=\lambda v_{1}$, and compare
to obtain equations $({\eta}+{\mu}-\lambda-1)x={\mu}-1$ and $x=1-\lambda$.
Solving these equations, we get Equation 7

$\lambda^{2}-({\mu}+{\eta})\lambda+{\eta}=0$ (7)

The eigenvalues of $H+({\eta}-1)G$ are ${\mu}$ and 0 with multiplicity
${\mu}-1$ and 1, respectively.

Note that
$Q_{m-1}(W^{\prime}({\eta},{\mu}))=\mathbb{J}_{{\eta}}\otimes(-G)+\mathbb{I}_{{\eta}}\otimes(W+G),$
where
$W=\mathbb{J}_{{\mu}}+((m-1)({\mu}-1)-1)\mathbb{I}_{{\mu}}-(m-1)({\eta}-1)G$.
The spectrum of $Q_{m-1}(W^{\prime}({\eta},{\mu}))$ is given by the spectrum
of $W+G$ and $W-({\eta}-1)G$ with multiplicity ${\eta}-1$ and 1, respectively.
We see that $(m-1)({\mu}-1)-1$ is an eigenvalue of $W+G$ and $W-({\eta}-1)G$
with ${\mu}-2$ dimensional linearly independent eigenvectors

$\\{(0,1,-1,0,\dots,0)^{T},(0,1,0,-1,\ldots,0)^{T},\ldots,(0,1,0,0,\ldots,-1)^{T}\\}.$

Consider matrix equations $(W+G)v_{2}=\lambda^{\prime}v_{2}$ and
$(W-({\eta}-1)G)v_{3}=\lambda^{\prime\prime}v_{3}$, where
$v_{2}=(y,1,1,\ldots,1)^{T}$ and $v_{3}=(z,1,1,\ldots,1)^{T}.$ On comparing
$(W+G)v_{2}=\lambda^{\prime}v_{2}$, we obtain equations
$((m-1)({\mu}+{\eta}-2)-1-\lambda^{\prime})y=-({\mu}-1)$ and
$y+(m-1)({\mu}-1)+{\mu}-2=\lambda^{\prime}.$ Solving these equations, we get
Equation 8

$(\lambda^{\prime})^{2}-(m{\mu}-m-2+(m-1)({\mu}+{\eta}-2))\lambda^{\prime}+((m-1)({\mu}+{\eta}-2)-1)(m{\mu}-m-1)-{\mu}+1=0.$
(8)

Similarly, we can solve $(W-({\eta}-1)G)v_{3}=\lambda^{\prime\prime}v_{3}$ and
obtain Equation 9

$(\lambda^{\prime\prime})^{2}-(m{\mu}-m-2+(m-1)({\mu}+{\eta}-2)+{\eta})\lambda^{\prime\prime}+(({\eta}-1+(m-1)({\mu}+{\eta}-2))(m{\mu}-m-1)+1-{\mu}=0.$
(9)

As $a(W^{\prime}({\eta},{\mu}))\leq m-1$, it can be seen that $(m-1){\mu}$ and
$(m-1)({\mu}-1)-1$ are greater than or equal to $m-1$. Let
$\lambda_{1}\leq\lambda_{2}$, $\lambda_{3}\leq\lambda_{4}$ and
$\lambda_{5}\leq\lambda_{6}$, where
$\\{\lambda_{1},\lambda_{2}\\},\\{\lambda_{3},\lambda_{4}\\}$ and
$\\{\lambda_{5},\lambda_{6}\\}$ are the roots of Equation 7, 8 and 9,
respectively. We first show that $(m-1)\lambda_{1}<m-1$. In contrast, if
$\lambda_{1}\geq 1$, then ${\mu}\leq 1$, which is a contradiction. Suppose
that $\lambda_{3}<m-1$ and $\lambda_{5}<m-1$, after simplification we obtain
Equations 10 and 11, respectively

$({\mu}-2)(m(({\mu}+{\eta}-3)(m-1)-1)-1)-1<0$ (10)
$(1-{\mu})(1-4m)+m^{2}(2-{\mu})(3-{\eta})+{\mu}m((m-1)({\mu}-2)-2)<0.$ (11)

As $m\geq 2,{\mu}\geq 3$ and ${\eta}\geq 3$, the left-hand sides of Equations
10 and 11 are greater than or equal to zero, which is a contradiction. ∎

######  Remark 13.

Note that $a(W^{\prime}({\eta},2)\times K_{2})=\lambda_{3}$, where
$\lambda_{1},\lambda_{3}$ and $\lambda_{5}$ are defined in Theorem 12.
Clearly, $\lambda_{3}\leq\lambda_{5}$ as
$\lambda_{5}-\lambda_{3}=\frac{{\eta}+\sqrt{{\eta}^{2}-4{\eta}+8}-\sqrt{4{\eta}^{2}-8{\eta}+8}}{2}\geq\frac{{\eta}+{\eta}-2-2{\eta}+4}{2}\geq
1.$ If $\lambda_{1}-\lambda_{3}\leq 0$, then $4\leq 0$ which is a
contradiction.

As a consequence of Theorem 12, we obtain Corollary 14. In this regard, we
define some terminology. A rooted tree is a tree in which one vertex has been
designated as the root. The first vertex from which the tree originates is
called a root vertex. For example, in Figure 4 vertex $v$ is the root vertex.
The height of a vertex in a rooted tree is the length of the longest downward
path to a pendant vertex from that vertex. The vertex that has a branch from
it to any other vertex is called a parent vertex. If vertex $u$ is the parent
of vertex $v$, then $v$ is called a child of $u$.

|  | 17114914562315161213810
---|---
|  | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ | $15$ | $16$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$1$ | 4 | 0 | 0 | 0 | -1 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | -1 | 0 | 0
$2$ | 0 | 2 | 0 | -1 | 0 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$3$ | 0 | 0 | 2 | -1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$4$ | 0 | -1 | -1 | 4 | 0 | 0 | -1 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 0
$5$ | -1 | 0 | -1 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$6$ | -1 | -1 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$7$ | 0 | 0 | 0 | -1 | 0 | 0 | 3 | -1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0
$8$ | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$9$ | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | -1 | -1 | 0 | 0 | 0 | 0 | 0
$10$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0
$11$ | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | -1 | 0 | 4 | 0 | 0 | 0 | -1 | -1
$12$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 0 | -1 | 0 | -1
$13$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | -1 | -1 | 0
$14$ | -1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | -1 | -1 | 4 | 0 | 0
$15$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | -1 | 0 | 2 | 0
$16$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | 0 | 0 | 0 | 2
Table 1: $X,\beta_{2}(X)$ and $\mathfrak{L}(\beta_{2}(X))$

######  Corollary 14.

  1. 1.

Let $T=T(n,{\eta};x_{1},x_{2},x_{3},\ldots,x_{{\eta}})$ such that if there
exist atleast two $x_{i}$ that are equal (say ${\mu}\geq 2$), where $1\leq
i\leq{\eta}.$ Then $a({\beta_{m}}(T))\leq a(W^{\prime}({\eta},{\mu}+1)).$

  2. 2.

Let $T$ be a rooted tree and, at some height $h\geq 2$ $\exists$ atleast two
vertices $v_{i},v_{j}$ of the same parent vertex that has ${\eta}\geq 3$
children, such that $|C(v_{i})|=|C(v_{j})|={\mu}$, where $|C(v_{i})|$ denotes
the number of children of parent vertex $v_{i}$, $C(v_{i})$ and $C(v_{j})$ are
pendant vertices of $T$. Then $a({\beta_{m}}(T))\leq
a(W^{\prime}({\eta},{\mu}+1)).$

###### Proof.

Proof of part 1. The structure of $L(T)$ is obtained by attaching $K_{x_{i}}$,
where $1\leq i\leq{\eta}$ at exactly one vertex of $K_{{\eta}}.$ By
hypothesis, it can be seen that there are at least two vertices in
$K_{{\eta}}$ to which $K_{{\mu}}$ is attached. Label the vertices of one copy
of $K_{u}$ by $\\{1,2,\ldots,{\mu}\\}$ and another by
$\\{{\mu}+1,{\mu}+2,\ldots,2{\mu}\\}$, where $1$ and ${\mu}+1$ are the
vertices of $K_{{\eta}}.$ Then observe that
$\mathfrak{L}(L(T))=\begin{bmatrix}H&G&C\\\ G&H&C\\\
C^{T}&C^{T}&D\end{bmatrix},$ where $G$ is a $({\mu}+1)\times({\mu}+1)$ matrix
with $-1$ in $(1,1)$ position and zero elsewhere, and
$H=-\mathbb{J}_{{\mu}+1}+({\mu}+1)\mathbb{I}_{{\mu}+1}+(-{\eta}+1)G.$ Let
$\lambda$ be an eigenvalue of $H-G$ afforded by the eigenvector $v.$ Consider
$V=(v,-v,0)^{T}$, then $\mathfrak{L}(L(T))V=\lambda V.$ Now the result follows
by Theorem 12,.

Proof of part 2. It is immediate from Part 1. ∎

Next, we provide a bound for the algebraic connectivity of
$L(\mathbb{B}_{k})\times K_{m}.$ Let $H$ be a $n\times n$ matrix partitioned
as $H=\begin{bmatrix}A_{11}&A_{12}\\\ A_{21}&A_{22}\end{bmatrix},$ where
$A_{11}$ and $A_{22}$ are square matrices. If $A_{11}$ is non-singular, then
the Schur complement of $A_{11}$ in $H$ is defined to be the matrix
$A_{22}-A_{21}A_{11}^{-1}A_{12}.$ For Schur complement, we have
$det(H)=det(A_{11})det(A_{22}-A_{21}A_{11}^{-1}A_{12}).$ Similarly, if
$A_{22}$ is non-singular, then the Schur complement of $A_{22}$ in $H$ is
defined as the matrix $A_{11}-A_{12}A_{22}^{-1}A_{21}$, and we can obtain
$det(H)=det(A_{22})det(A_{11}-A_{12}A_{22}^{-1}A_{21}).$

######  Example 15.

In Figure 6, we demonstrate the edge labeling process used in Theorem 16.

$e_{3}$$e_{6}$$e_{9}$$e_{1}$$e_{4}$$e_{7}$$e_{10}$$e_{2}$$e_{5}$$e_{8}$ Figure
6: $\mathbb{B}_{3}$

######  Theorem 16.

Let $X=\mathbb{B}_{k}$, where $k\geq 3$. Then
$a(L(X))=\frac{4+k-\sqrt{k^{2}+8}}{2}.$

###### Proof.

From the labeling defined in Example 15,

$\mathfrak{L}(L(X))=\begin{bmatrix}2k&-\mathbb{1_{1\times
2k}}&\mathbb{0_{1\times k}}\\\ -\mathbb{1_{2k\times 1}}&S&Z\\\
\mathbb{0_{k\times 1}}&Z^{T}&2\mathbb{I}_{k}\end{bmatrix},$

where $S=\mathbb{I}_{2}\otimes(-\mathbb{J}_{k}+(k+2)\mathbb{I}_{k})$ and
$Z^{T}=\begin{bmatrix}-\mathbb{I}_{k}&-\mathbb{I}_{k}\end{bmatrix}.$ The
characterstic polynomial of $\mathfrak{L}(L(X))$ is

$det(\mathfrak{L}(L(X))-\lambda\mathbb{I}_{3k+1})=det\left(\left[\begin{array}[]{cc|c}2k-\lambda&-\mathbb{1_{1\times
2k}}&\mathbb{0_{1\times k}}\\\ -\mathbb{1_{2k\times
1}}&S-\lambda\mathbb{I}_{2k}&Z\\\ \hline\cr\mathbb{0_{k\times
1}}&Z^{T}&(2-\lambda)\mathbb{I}_{k}\end{array}\right]\right).$

By the Schur complement formula,

$\displaystyle det(\mathfrak{L}(L(X))-\lambda\mathbb{I}_{3k+1})$
$\displaystyle=(2-\lambda)^{k}det\left(\begin{bmatrix}2k-\lambda&-\mathbb{1_{1\times
2k}}\\\ -\mathbb{1_{2k\times
1}}&S-\lambda\mathbb{I}_{2k}\end{bmatrix}-\begin{bmatrix}0\\\
Z\end{bmatrix}((2-\lambda)\mathbb{I}_{k})^{-1}\begin{bmatrix}0&Z^{T}\\\
\end{bmatrix}\right)$
$\displaystyle=(2-\lambda)^{k}det\left(\begin{bmatrix}2k-\lambda&-\mathbb{1_{1\times
2k}}\\\ -\mathbb{1_{2k\times
1}}&S-\lambda\mathbb{I}_{2k}\end{bmatrix}-\frac{1}{2-\lambda}\begin{bmatrix}0&0\\\
0&\mathbb{J}_{2}\otimes\mathbb{I}_{k}\end{bmatrix}\right)$ $\displaystyle=$
$\displaystyle(2-\lambda)^{k}det\left(\begin{bmatrix}2k-\lambda&-\mathbb{1_{1\times
2k}}\\\ -\mathbb{1_{2k\times
1}}&S-\lambda\mathbb{I}_{2k}-\frac{1}{2-\lambda}(\mathbb{J}_{2}\otimes\mathbb{I}_{k})\end{bmatrix}\right).$

We again apply the Schur complement formula to the last expression,

$det(\mathfrak{L}(L(X))-\lambda\mathbb{I}_{3k+1})=(2-\lambda)^{k}(2k-\lambda)det\left(S-\lambda\mathbb{I}_{2k}-\frac{1}{2-\lambda}(\mathbb{J}_{2}\otimes\mathbb{I}_{k})-\frac{1}{2k-\lambda}\mathbb{J}_{2k}\right).$

It can be verified that
$S-\lambda\mathbb{I}_{2k}-\frac{1}{2-\lambda}(\mathbb{J}_{2}\otimes\mathbb{I}_{k})-\frac{1}{2k-\lambda}\mathbb{J}_{2k}=\begin{bmatrix}A&B\\\
B&A\end{bmatrix}$, where

$A=-\left(\frac{1}{2k-\lambda}+1\right)\mathbb{J}_{k}+\left(k+2-\lambda-\frac{1}{2-\lambda}\right)\mathbb{I}_{k},B=-\frac{1}{2k-\lambda}\mathbb{J}_{k}-\frac{1}{2-\lambda}\mathbb{I}_{k}.$

The spectrum of $\begin{bmatrix}A&B\\\ B&A\end{bmatrix}$ is given by the union
of spectra of $A+B$ and $A-B$ (See [6]). We have
$A+B=-(\frac{2}{2k-\lambda}+1)\mathbb{J}_{k}+(k+2-\lambda-\frac{2}{2-\lambda})\mathbb{I}_{k}$
and $A-B=-\mathbb{J}_{k}+(k+2-\lambda)\mathbb{I}_{k}.$ Therefore,

$det(\mathfrak{L}(L(X))-\lambda\mathbb{I}_{3k+1})=(k+2-\lambda)^{k-1}(\lambda-2)\lambda(-\lambda^{2}+2(k+2)\lambda-(6k+2))(\lambda^{2}-(4+k)\lambda+2(k+1))^{k-1}.$

Thus, the eigenvalues of $\mathfrak{L}(L(X))$ are
$0,k+2,2,\frac{4+k\pm\sqrt{k^{2}+8}}{2}$ and $k+2\pm\sqrt{k^{2}-2k+2}$ with
multiplicity $1,k-1,1,k-1$ and 1, respectively.

Now, we show that $a(L(X))=\frac{4+k-\sqrt{k^{2}+8}}{2}.$ If
$\frac{4+k-\sqrt{k^{2}+8}}{2}\geq 2$ and $\frac{4+k-\sqrt{k^{2}+8}}{2}\geq
k+2-\sqrt{k^{2}-2k+2}$, then $0\geq 8$ and $2k^{2}(k-1)\leq 0$ respectively,
which is a contradiction. The result holds. ∎

From the above theorem, we can conclude that $a(L(X)\times
K_{m})\leq(m-1)\frac{4+k-\sqrt{k^{2}+8}}{2}$.

##  4 Acknowledgement

The authors thank the handling editor and the anonymous reviewers for their
valuable comments and suggestions.

n | $X$ | $a(X)$ | $\beta_{2}(X)$ | $\beta_{3}(X)$ | $\beta_{4}(X)$ | $\beta_{5}(X)$ | $\beta_{6}(X)$ | $\beta_{7}(X)$
---|---|---|---|---|---|---|---|---
$5$ |  | 0.519 | 0.43 | 1.72 | 2.82 | 3.87 | 4.89 | 5.91
$6$ |  | $0.325$ | 0.224 | 1.037 | 1.556 | 2.075 | 2.59 | 3.112
6 |  | 0.381 | 0.381 | 1.39 | 2.09 | 2.78 | 3.486 | 4.18
$6$ |  | $0.486$ | $0.627$ | 1.824 | 2.88 | 3.91 | 4.93 | 5.94
6 |  | 0.438 | 1 | 2 | 3 | 4 | 5 | 6
$7$ |  | 0.225 | $0.13$ | 0.649 | 0.974 | 1.299 | 1.62 | 1.944
$7$ |  | 0.260 | 0.220 | 0.826 | 1.23 | 1.652 | 2.065 | 2.478
$7$ |  | 0.296 | 0.28 | 0.9717 | 1.45 | 1.943 | 2.42 | 2.91
7 |  | 0.381 | 0.381 | 1.39 | 2.09 | 2.075 | 2.59 | 3.112
7 |  | 0.267 | 0.43 | 0.876 | 1.31 | 1.72 | 2.15 | 2.58
7 |  | 0.322 | 0.45 | 1.26 | 1.89 | 2.52 | 2.95 | 3.38
$7$ |  | 0.381 | 0.581 | 1.52 | 2.29 | 3.055 | 3.81 | 4.58
$7$ |  | 0.466 | 0.72 | 1.86 | 2.91 | 3.93 | 4.94 | 5.95
7 |  | 0.398 | 1 | 2 | 3 | 4 | 5 | 6
Table 2: Caption

## References

  * [1] R. Bapat, A. Lal, and S. Pati.  On algebraic connectivity of graphs with at most two points of articulation in each block.  Linear and Multilinear Algebra, 60(4):415–432, 2012.
  * [2] D. Cvetković and S. K. Simić.  Towards a spectral theory of graphs based on the signless laplacian, i.  Publications de l’Institut Mathematique, 85(105):19–33, 2009.
  * [3] D. Cvetković and S. K. Simić.  Towards a spectral theory of graphs based on the signless laplacian, ii.  Linear Algebra and its Applications, 432(9):2257–2272, 2010.
  * [4] D. Cvetković and S. K. Simić.  Towards a spectral theory of graphs based on the signless laplacian, iii.  Applicable Analysis and Discrete Mathematics, pages 156–166, 2010\.
  * [5] K. C. Das.  The laplacian spectrum of a graph.  Computers & Mathematics with Applications, 48(5-6):715–724, 2004\.
  * [6] P. J. Davis.  Circulant matrices.  American Mathematical Soc., 2013.
  * [7] N. M. M. De Abreu.  Old and new results on algebraic connectivity of graphs.  Linear algebra and its applications, 423(1):53–73, 2007.
  * [8] L. S. de Lima, C. S. Oliveira, N. M. M. de Abreu, and V. Nikiforov.  The smallest eigenvalue of the signless laplacian.  Linear algebra and its applications, 435(10):2570–2584, 2011.
  * [9] S. M. Fallat, S. J. Kirkland, J. J. Molitierno, and M. Neumann.  On graphs whose laplacian matrices have distinct integer eigenvalues.  Journal of Graph Theory, 50(2):162–174, 2005.
  * [10] M. Fiedler.  Algebraic connectivity of graphs.  Czechoslovak mathematical journal, 23(2):298–305, 1973.
  * [11] R. Grone, R. Merris, and V. Sunder.  The laplacian spectrum of a graph.  SIAM Journal on matrix analysis and applications, 11(2):218–238, 1990.
  * [12] R. A. Horn and C. R. Johnson.  Matrix analysis.  Cambridge university press, 2012.
  * [13] W. Imrich.  S. klavžar, product graphs, 2000.
  * [14] S. Kirkland.  A bound on the algebraic connectivity of a graph in terms of the number of cutpoints.  Linear and Multilinear Algebra, 47(1):93–103, 2000.
  * [15] S. Kirkland.  Completion of laplacian integral graphs via edge addition.  Discrete mathematics, 295(1-3):75–90, 2005.
  * [16] M. Liu and B. Liu.  Some results on the laplacian spectrum.  Computers & Mathematics with Applications, 59(11):3612–3616, 2010\.
  * [17] R. Merris.  Degree maximal graphs are laplacian integral.  Linear algebra and its Applications, 199:381–389, 1994.
  * [18] R. Merris.  Laplacian matrices of graphs: a survey.  Linear algebra and its applications, 197:143–176, 1994.