# New constructions of non-regular cospectral graphs

Suliman Hamud and Abraham Berman

<EMAIL_ADDRESS><EMAIL_ADDRESS>
Deticated to Prof. Frank J. Hall, in celebration of his many contributions to
matrix theory.

##  1 Abstract

We consider two types of joins of graphs $G_{1}$ and $G_{2}$, $G_{1}\veebar
G_{2}$ \- the Neighbors Splitting Join and $G_{1}\underset{=}{\lor}G_{2}$ \-
the Non Neighbors Splitting Join, and compute the adjacency characteristic
polynomial, the Laplacian characteristic polynomial and the signless Laplacian
characteristic polynomial of these joins. When $G_{1}$ and $G_{2}$ are
regular, we compute the adjacency spectrum, the Laplacian spectrum, the
signless Laplacian spectrum of $G_{1}\underset{=}{\lor}G_{2}$ and the
normalized Laplacian spectrum of $G_{1}\veebar G_{2}$ and
$G_{1}\underset{=}{\lor}G_{2}$. We use these results to construct non regular,
non isomorphic graphs that are cospectral with respect to the four matrices:
adjacency, Laplacian , signless Laplacian and normalized Laplacian.

.

##  2 Introduction

Spectral graph theory is the study of graphs via the spectrum of matrices
associated with them [3, 6, 8, 22, 27]. The graphs in this paper are
undirected and simple. There are several matrices associated with a graph and
we consider four of them; the adjacency matrix, the Laplacian matrix, the
signless Laplacian matrix and the normalized Laplacian matrix.

Let $G=\left(V\left(G\right),E\left(G\right)\right)$ be a graph with vertex
set $V\left(G\right)=\left\\{v_{1},v_{2},...,v_{n}\right\\}$ and edge set
$E\left(G\right)$.

######  Definition 2.1.

The adjacency matrix of $G$, $A\left(G\right),\textrm{is}$ defined by;

$\left(A(G)\right)_{ij}=\begin{cases}1,&\textrm{if $v_{i}$ and $v_{j}$ are
adjacent};\\\ 0,&\textrm{otherwise.}\end{cases}$

Let $d_{i}=d_{G}\left(v_{i}\right)$ be the degree of vertex $v_{i}$ in $G$,
and let $D\left(G\right)$ be the diagonal matrix with diagonal entries
$d_{1},d_{2},...,d_{n}.$

######  Definition 2.2.

The Laplacian matrix, $L\left(G\right),$ and the signless Laplacian matrix,
$Q\left(G\right),$ of $G$ are defined as
$L\left(G\right)=D\left(G\right)-A\left(G\right)$ and
$Q\left(G\right)=D\left(G\right)+A\left(G\right)$.

######  Definition 2.3.

([6]) The normalized Laplacian matrix, $\mathcal{L}\left(G\right),$is defined
to be
$\mathcal{L}\left(G\right)=I_{n}-D\left(G\right)^{-\frac{1}{2}}A\left(G\right)D\left(G\right)^{-\frac{1}{2}}$
(with the convention that if the degree of vertex $v_{i}$ in $G$ is $0$, then
$(d_{i})^{-\frac{1}{2}}=0$). In other words,

$\left(\mathcal{L}(G)\right)_{ij}=\begin{cases}1,&if\text{ i=j and $d_{i}\neq
0;$}\\\ -\frac{1}{\sqrt{d_{i}d_{j}}},&\textrm{if $i\neq j$ and $v_{i}$ is
adjacent to $v_{j};$ }\\\ 0,&\textrm{otherwise}.\end{cases}$

######  Notation 2.4.

For an $n\times n$ matrix $M$, we denote the characteristic polynomial
$det\left(xI_{n}-M\right)$ of $M$ by $f_{M}\left(x\right)$, where $I_{n}$ is
the identity matrix of order $n$. In particular, for a graph $G$,
$f_{X\left(G\right)}\left(x\right)$ is the $X\textrm{-characteristic}$
polynomial of $G$, for $X\in\left\\{A,L,Q,\mathcal{L}\right\\}$. The roots of
the $X\textrm{-characteristic}$ polynomial of $G$ are the
$X\textrm{-eigenvalues}$ of $G$ and the collection of the
$X\textrm{-eigenvalues,}$ including multiplicities, is called the
$X\textrm{-spectrum of $G.$}$

######  Notation 2.5.

The multiplicity of an eigenvalue $\lambda$ is denoted by a superscript above
$\lambda$.

######  Example 2.6.

The $A$-spectrum of the complete graph $K_{n}$ is
$\left\\{n-1,(-1)^{[n-1]}\right\\}$.

######  Remark 2.7.

If

$\lambda_{1}\left(G\right)\geq\lambda_{2}\left(G\right)\geq\cdot\cdot\cdot\geq\lambda_{n}\left(G\right),$
$\mu_{1}\left(G\right)\leq\mu_{2}\left(G\right)\leq\cdot\cdot\cdot\leq\mu_{n}\left(G\right),$
$\nu_{1}\left(G\right)\geq\nu_{2}\left(G\right)\geq\cdot\cdot\cdot\geq\nu_{n}\left(G\right),$
$\delta_{1}\left(G\right)\leq\delta_{2}\left(G\right)\leq\cdot\cdot\cdot\leq\delta_{n}\left(G\right),$

are the eigenvalues of $A\left(G\right)$, $L\left(G\right)$, $Q\left(G\right)$
and $\mathcal{L}\left(G\right)$, respectively. Then
$\stackrel{{\scriptstyle[}}{{i}}=1]{n}{\sum\lambda_{i}}=0$,
$\mu_{1}\left(G\right)=0,$ $\nu_{n}\left(G\right)\geq 0$ and
$\delta_{1}\left(G\right)=0,$ $\delta_{n}\left(G\right)\leq 2$ (equality iff
$G$ is bipartite).

######  Remark 2.8.

If $G$ is a r-regular graph, then
$\mu_{i}\left(G\right)=r-\lambda_{i}\left(G\right)$,
$\nu_{i}\left(G\right)=r+\lambda_{i}\left(G\right)$ and
$\delta_{i}\left(G\right)=1-\frac{1}{r}\lambda\left(G\right)$.

######  Definition 2.9.

Two graphs $G$ and $H$ are $X\textrm{-cospectral }$if they have the same
$X\textrm{-spectrum}$. If $X$-cospectral graphs are not isomorphic we say that
they are XNICS.

######  Definition 2.10.

Let $S$ be a subset of $\left\\{A,L,Q,\mathcal{L}\right\\}.$ The graphs $G$
and $H$ are SNICS if they are XNICS for all $X\in S.$

######  Definition 2.11.

A graph $G$ is determined by its $X\textrm{-spectrum}$ if every graph $H$ that
is $X\textrm{-cospectral}$ with $G$ is isomorphic to $G.$

A basic probem in spectral graph theory, [28, 29], is determining which graphs
are determined by their spectrum or finding non isomorphic $X$-cospectral
graphs.

######  Theorem 2.12.

([28])___If $G$ is regular , then the following are equivalent;_

  * •

_$G$ is determined by its $A$-spectrum,_

  * •

_$G$ is determined by its $L$-spectrum,_

  * •

_$G$ is determined by its $Q$-spectrum,_

  * •

_$G$ is determined by its $\mathcal{L}$-spectrum._

Thus, for regular graphs $G$ and $H$, we say that $G$ and $H$ are cospectral
if they are $X$-cospectral with respect to any
$X\in\left\\{A,L,Q,\mathcal{L}\right\\}.$

######  Proposition 2.13.

([28]) _Every regular graph with less than ten vertices is determined by its
spectrum._

######  Example 2.14.

The following graphs are regular and cospectral. They are non isomorphic since
in $G$ there is an edge that lies in three triangles but there is no such edge
in $H$.

(a) $\left(G\right)$

(b) $\left(H\right)$

Figure 2.1: Two regular non isomorphic cospectral graphs.

In recent years, several researchers studied the spectral properties of graphs
which are constructed by graph operations. These operations include disjoint
union, the Cartesian product, the Kronocker product, the strong product, the
lexicographic product, the rooted product, the corona, the edge corona, the
neighbourhood corona etc. We refer the reader to [1, 2, 8, 13, 16, 21, 9, 12,
24, 23, 25, 26] and the references therein for more graph operations and the
results on the spectra of these graphs.

Many operations are based on the join of graphs.

######  Definition 2.15.

([14]) The join of two graphs is their disjoint union together with all the
edges that connect all the vertices of the first graph with all the vertices
of the second graph.

Recently, many researchers provided several variants of join operations of
graphs and investigated their spectral properties. Some examples are Cardoso
[5], Indulal [17], Liu and Zhang [18], Varghese and Susha [30] and Das and
Panigrahi [11].

Butler [4] constructed non regular bipartite graphs which are cospectral with
respect to both the adjacency and the normalized Laplacian matrices. He asked
for examples of non-regular $\left\\{A,L,\mathcal{L}\right\\}$NICS graphs. A
slightly more general question is

######  Question 2.16.

Construct non regular $\left\\{A,L,Q,\mathcal{L}\right\\}$NICS graphs.

Such examples can be constructed using special join operation defined by Lu,
Ma and Zhang [19] and a variant of this operation, suggested in this paper.

######  Definition 2.17.

([19]) Let $G_{1}$ and $G_{2}$ be two vertex disjoint graphs with
$V(G_{1})=\\{u_{1},u_{2},...,u_{n}\\}.$The splitting $V$-vertex join of
$G_{1}$ and $G_{2}$, denoted by $G_{1}\veebar G$, is obtained by adding
vertices $u^{\prime}_{1},u^{\prime}_{2},...,u^{\prime}_{n}$ to $G_{1}\vee
G_{2}$ and connecting $u_{i}^{\prime}$ to $u_{j}$ if and only if
$\left(u_{i},u_{j}\right)\in E\left(G_{1}\right)$.

We refer to the splitting $V$-vertex join as NS (Neighbors Splitting) join and
define a new type of join, NNS (Non Neighbors Splitting) join.

######  Definition 2.18.

Let $G_{1}$ and $G_{2}$ be two vertex disjoint graphs with
$V\left(G_{1}\right)=\left\\{u_{1},u_{2},...,u_{n}\right\\}.$ The NNS join of
$G_{1}$ and $G_{2}$, denoted by $G_{1}\underset{=}{\vee}G_{2}$, is obtained by
adding vertices $u^{\prime}_{1},u^{\prime}_{2},...,u^{\prime}_{n}$ to $G\vee
G_{2}$ and connecting $u_{i}^{\prime}$ to $u_{j}$ iff
$\left(u_{i},u_{j}\right)\cancel{\in}E\left(G_{1}\right).$

######  Example 2.19.

Let G1 and $G_{2}$ be the path $P_{4}$ and the path $P_{2}$, respectively. The
graphs $P_{4}\underset{=}{\vee}P_{2}$ and $P_{4}\veebar P_{2}$ are given in
Figure 2.2.

(a) $P_{4}\veebar P_{2}$ (b) $P_{4}\underset{=}{\vee}P_{2}$

Figure 2.2: The graphs $P_{4}\veebar P_{2}$ and
$P_{4}\underset{=}{\vee}P_{2}$.

The structure of the paper is as follows; After preliminaries, we compute the
adjacency characteristic polynomial, the Laplacian characteristic polynomial
and the signless Laplacian characteristic polynomial of
$G_{1}\underset{=}{\vee}G_{2}$ and $G_{1}\veebar G_{2}$, and use the results
to construct $\left\\{A,L,Q\right\\}$NICS graphs, and finally, under
regularity assumptions we compute the $A$-spectrum, the $L$-spectrum, the
$Q$-spectrum and the $\mathcal{L}$-spectrum of NS and NNS joins and use the
results to construct $\left\\{A,L,Q,\mathcal{L}\right\\}$NICS graphs.

##  3 Preliminaries

######  Notation 3.1.

  * •

_$\mathbf{1}_{n}$ denotes $n$$\times 1$ column whose all entries are $1$, _

  * •

_$J_{s\times t}$ $=\mathbf{1}_{s}\mathbf{1}_{t}^{T}$, $J_{s}=J_{s\times s},$_

  * •

_$O_{s\times t}$ denotes the zero matrix of order $s\times t$,_

  * •

_$adj\left(A\right)$ denotes the adjugate of $A.$_

  * •

$\overline{G}$ _denotes the complement of graph $G$._

######  Definition 3.2.

([7, 20]) The coronal $\Gamma_{M}(x)$ of an n$\times$n matrix $M$ is the sum
of the entries of the inverse of the characteristic matrix of $M$ , that is,

$\Gamma_{M}(x)=\mathbf{1}_{n}^{T}(xI_{n}-M)^{-1}\mathbf{1}_{n}.$ (3.1)

######  Lemma 3.3.

([7, 20]) Let $M$ be an n$\times$n matrix with all row sums equal to r ( for
example, the adjacency matrix of a $r$-regular graph). Then

$\Gamma_{M}(x)=\frac{n}{x-r}.$

######  Definition 3.4.

Let $M$ be a block matrix

$M=\left(\begin{array}[]{cc}A&\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B\\\ \\\
C&\,\,\,\,\,\,\,\,\,\,\,\,\,\,D\end{array}\right)$

such that its blocks $A$ and $D$ are square. If $A$ is invertible, the Schur
complement of $A$ in $M$ is

$M/A=D-CA^{-1}B$

and if $D$ is invertible, the Schur complement of $D$ in $M$ is

$M/D=A-BD^{-1}C.$

Issai Schur proved the following lemma.

######  Lemma 3.5.

_(__[15])__.__If $D$ is invertible then, _

__

$\displaystyle detM$ $\displaystyle=det(M/D)detD$

_and if $A$ is invertible then,_

$detM=det(M/A)detA.$

######  Lemma 3.6.

_Let_ ___$M$ be a block matrix_ __

$M=\left(\begin{array}[]{ccc}A&\,\,\,\,\,\,\,\,\,\,\,\,\,\,B&\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,J_{n_{1}\times
n_{2}}\\\ \\\
B&\,\,\,\,\,\,\,\,\,\,\,\,\,\,C&\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,O_{n_{1}\times
n_{2}}\\\ \\\ J_{n_{2}\times
n_{1}}&\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,O_{n_{2}\times
n_{1}}&\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,D\end{array}\right)$

_where $A$, $B$, and $C$ are square matrices of order $n_{1}$ and $D$ is a
square matrix of order $n_{2}.$ Then the Schur complement of $xI_{n_{2}}-D$ in
the _charactristic matrix of $M$ is

__

$\left(\begin{array}[]{cc}xI_{n_{1}}-A-\Gamma_{D}(x)J_{n_{1}}&-B\\\ \\\
-B&xI_{n_{1}}-C\end{array}\right).$

###### Proof.

The charactristic matrix of $M$ is

$xI_{2n_{1}+n_{2}}-M=\left(\begin{array}[]{ccc}xI_{n_{1}}-A&-B&-J_{n_{1}\times
n_{2}}\\\ \\\ -B&\,\,\,\,\,xI_{n_{1}}-C&O_{n_{1}\times n_{2}}\\\ \\\
-J_{n_{2}\times n_{1}}&O_{n_{2}\times n_{1}}&xI_{n_{2}}-D\end{array}\right).$

The Schur complement of $\left(xI_{n_{2}}-D\right)$ is

$\displaystyle\left(xI_{2n_{1}+n_{2}}-M\right)\left/\left(xI_{n_{2}}-D\right)\right.$
$\displaystyle=\left(\begin{array}[]{cc}xI_{n_{1}}-A&\,-B\\\ \\\
-B&xI_{n_{1}}-C\end{array}\right)-\left(\begin{array}[]{c}-J_{n_{1}\times
n_{2}}\\\ \\\ O_{n_{1}\times
n_{2}}\end{array}\right)\left(xI_{n_{2}}-D\right)^{-1}\left(\begin{array}[]{cc}-J_{n_{2}\times
n_{1}}&O_{n_{2}\times n_{1}}\end{array}\right)$
$\displaystyle=\left(\begin{array}[]{cc}xI_{n_{1}}-A&-B\\\ \\\
-B&xI_{n_{1}}-C\end{array}\right)-\left(\begin{array}[]{c}\mathbf{1}_{n_{1}}\mathbf{1}_{n_{2}}^{T}\\\
\\\ O_{n_{1}\times
n_{1}}\end{array}\right)\left((xI_{n_{2}}-D)^{-1}\right)\left(\begin{array}[]{cc}\text{$\mathbf{1}_{n_{2}}$$\mathbf{1}_{n_{1}}^{T}$}&O_{n_{1}\times
n_{1}}\end{array}\right)$
$\displaystyle=\left(\begin{array}[]{cc}xI_{n_{1}}-A-\Gamma_{D}(x)J_{n_{1}}&-B\\\
\\\ -B&xI_{n_{1}}-C\end{array}\right).$

∎

######  Lemma 3.7.

_([8])_. If A is an n$\times n$ real matrix and α is an real number, then

$det(A+\alpha J_{n})=det(A)+\alpha\mathbf{1}_{n}^{T}adj(A)\mathbf{1}_{n}.$
(3.2)

##  4 The characteristic polynomials of the NNS join and the NS join

In [19] the authers compute the adjacency, Laplacian and signless Laplacian
characteristic polynomial of $G_{1}\veebar G_{2}$ where $G_{1}$ and $G_{2}$
are regular.
Here we compute the characteristic polynomials of
$G_{1}\underset{=}{\lor}G_{2}$ and $G_{1}\veebar G_{2}$ where $G_{1}$ and
$G_{2}$ are arbitrary graphs. The proofs for the two joins (NS and NNS) are
quite similar and use Lemma 3.5 (twice), Lemma 3.6 and Lemma 3.7. The results
are used to construct non regular $\left\\{A,L,Q\right\\}$NICS graphs.

###  4.1 Adjacency characteristic polynomial

######  Theorem 4.1.

_Let $G_{i}$ be a graph on $n_{i}$ vertices for $i=1,2$. Then_

  * _(a)_

_$f_{A(G_{1}\underset{=}{\vee}G_{2})}(x)=x^{n_{1}}f_{{}_{A\left(G_{2}\right)}}(x)det\left(xI_{n_{1}}-A(G_{1})-\frac{1}{x}A^{2}(\overline{G_{1}})\right)\left[1-\varGamma_{A(G_{2})}(x)\varGamma_{A(G_{1})+\frac{1}{x}A^{2}(\overline{G_{1}})}(x)\right].$_

  * _(b)_

_$f_{A(G_{1}\veebar
G_{2})}(x)=x^{n_{1}}f_{{}_{A\left(G_{2}\right)}}(x)det\left(xI_{n_{1}}-A(G_{1})-\frac{1}{x}A^{2}(G_{1})\right)\left[1-\varGamma_{A(G_{2})}(x)\varGamma_{A(G_{1})+\frac{1}{x}A^{2}(G_{1})}(x)\right]$_.

###### Proof.

We prove (a). The proof of (b) is similar.

With a suitable ordering of the vertices of $G_{1}\underset{=}{\lor}G_{2}$, we
get

$\displaystyle A\left(G_{1}\underset{=}{\vee}G_{2}\right)=$
$\displaystyle\left(\begin{array}[]{ccc}A\left(G_{1}\right)&\,\,\,\,A\left(\overline{G_{1}}\right)&\,\,\,\,\,J_{n_{1}\times
n_{2}}\\\ \\\
A\left(\stackrel{{\scriptstyle\text{\\_\\_\\_}}}{{G_{1}}}\right)&\,\,\,\,\,\,O_{n_{1}\times
n_{1}}&\,\,\,\,\,\,O_{n_{1}\times n_{2}}\\\ \\\ J_{n_{2}\times
n_{1}}&\,\,\,\,\,\,O_{n_{2}\times
n_{1}}&\,\,\,\,A\left(G_{2}\right)\end{array}\right).$

Thus

$\displaystyle f_{A(G_{1}\underset{=}{\vee}G_{2})}(x)=$ $\displaystyle
det\left(xI_{2n_{1}+n_{2}}-A\left(G_{1}\underset{=}{\vee}G_{2}\right)\right)$
$\displaystyle=$ $\displaystyle
det\left(\begin{array}[]{cc|c}xI_{n_{1}}-A(G_{1})&-A(\overline{G_{1}})&-J_{n_{1}\times
n_{2}}\\\ &\\\ -A(\overline{G_{1}})&xI_{n_{1}}&O_{n_{1}\times n_{2}}\\\ &\\\
\hline\cr-J_{n_{2}\times n_{1}}&O_{n_{2}\times
n_{1}}&xI_{n_{2}}-A(G_{2})\end{array}\right)$
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=det\left(xI_{n_{2}}-A(G_{2})\right)det\left(\left(xI_{2n_{1}+n_{2}}-A\left(G_{1}\underset{=}{\vee}G_{2}\right)\right)\left/\left(xI_{n_{2}}-A(G_{2})\right)\right.\right),$

by the Lemma of Schur (Lemma 3.5).

By Lemma 3.6,

$\left(xI_{2n_{1}+n_{2}}-A\left(G_{1}\underset{=}{\vee}G_{2}\right)\right)\left/\left(xI_{n_{2}}-A(G_{2})\right)\right.=\begin{pmatrix}xI_{n_{1}}-A(G_{1})-\varGamma_{A(G_{2})}(x)\,J_{n_{1}\times
n_{1}}\,\,\,\,\,\,\,\,\,\,\,&-A(\overline{G_{1}})\\\ \\\ \\\
-A(\overline{G_{1}})&xI_{n_{1}}\end{pmatrix}.$

Using again Lemma 3.5, we get

$det\left(\left(xI_{2n_{1}+n_{2}}-A\left(G_{1}\underset{=}{\vee}G_{2}\right)\right)\left/\left(xI_{n_{2}}-A(G_{2})\right)\right.\right)=det\left(xI_{n_{1}}\right)det\left(xI_{n_{1}}-A(G_{1})-\varGamma_{A(G_{2})}(x)\,J_{n_{1}\times
n_{1}}-\frac{1}{x}A^{2}(\overline{G_{1}})\right).$

By Lemma 3.7, we get

$\displaystyle
det\left(\left(xI_{2n_{1}+n_{2}}-A\left(G_{1}\underset{=}{\vee}G_{2}\right)\right)\left/\left(xI_{n_{2}}-A(G_{2})\right)\right.\right)=\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$
$\displaystyle=x^{n_{1}}\left(det(xI_{n_{1}}-A(G_{1})-\frac{1}{x}A^{2}(\overline{G_{1}}))-\varGamma_{A(G_{2})}(x)1_{n_{1}}^{T}adj\left(xI_{n_{1}}-A(G_{1})-\frac{1}{x}A^{2}(\overline{G_{1}})\right)1_{n_{1}}\right)$
$\displaystyle=x^{n_{1}}det\left(xI_{n_{1}}-A(G_{1})-\frac{1}{x}A^{2}(\overline{G_{1}})\right)\left[1-\varGamma_{A(G_{2})}(x)1_{n_{1}}^{T}(xI_{n_{1}}-A(G_{1})-\frac{1}{x}A^{2}(\overline{G_{1}}))^{-1}1_{n_{1}}\right]$
$\displaystyle\,\,\,=x^{n_{1}}det\left(xI_{n_{1}}-A(G_{1})-\frac{1}{x}A^{2}(\overline{G_{1}})\right)\left[1-\varGamma_{A(G_{2})}(x)\varGamma_{A(G_{1})+\frac{1}{x}A^{2}(\overline{G_{1}})}(x)\right].\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$

Thus

$f_{A(G_{1}\underset{=}{\vee}G_{2})}(x)=x^{n_{1}}f_{{}_{A\left(G_{2}\right)}}(x)det\left(xI_{n_{1}}-A(G_{1})-\frac{1}{x}A^{2}(\overline{G_{1}})\right)\left[1-\varGamma_{A(G_{2})}(x)\varGamma_{A(G_{1})+\frac{1}{x}A^{2}(\overline{G_{1}})}(x)\right].$

∎

###  4.2 Laplacian characteristic polynomial

In this section, we derive the Laplacian characteristic polynomials of
$G_{1}\veebar G_{2}$ and $G_{1}\underset{=}{\lor}G_{2}$ when $G_{1}$and
$G_{2}$ are arbitrary graphs.

######  Theorem 4.2.

_Let $G_{i}$ be a graph on $n_{i}$ vertices for $i=1,2$. Then_

  * _(a)_

__

$\displaystyle
f_{{}_{L\left(G_{1}\underset{=}{\vee}G_{2}\right)}}\left(x\right)$
$\displaystyle=det\left(\left(x-n_{1}\right)I_{n_{2}}-L\left(G_{2}\right)\right)det\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)$
$\displaystyle\cdot
det\left(\left(x-n_{1}-n_{2}+1\right)I_{n_{1}}-L\left(G_{1}\right)+D\left(G_{1}\right)-A\left(\overline{G_{1}}\right)\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)^{-1}A\left(\overline{G_{1}}\right)\right)$
$\displaystyle\cdot\left[1-\varGamma_{{}_{L\left(G_{2}\right)}}\left(x-n_{1}\right)\varGamma_{{}_{L\left(G_{1}\right)-D\left(G_{1}\right)+A\left(\overline{G_{1}}\right)\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)^{-1}A\left(\overline{G_{1}}\right)}}\left(x-n_{1}-n_{2}+1\right)\right].$

  * _(b)_

__

$\displaystyle f_{{}_{L\left(G_{1}\veebar G_{2}\right)}}$
$\displaystyle=det\left(\left(x-n_{1}\right)I_{n_{2}}-L\left(G_{2}\right)\right)det\left(xI_{n_{1}}-D\left(G_{1}\right)\right)$
$\displaystyle\cdot
det\left(\left(x-n_{2}\right)I_{n_{1}}-L\left(G_{1}\right)-D\left(G_{1}\right)-A\left(G_{1}\right)\left(xI_{n_{1}}-D\left(G_{1}\right)\right)^{-1}A\left(G_{1}\right)\right)$
$\displaystyle\cdot\left[1-\varGamma_{{}_{L\left(G_{2}\right)}}\left(x-n_{1}\right)\varGamma_{{}_{L\left(G_{1}\right)+D\left(G_{1}\right)+A\left(G_{1}\right)\left(xI_{n_{1}}-D\left(G_{1}\right)\right)^{-1}A\left(G_{1}\right)}}\left(x-n_{2}\right)\right].$

###### Proof.

(a) With a suitable ordering of the vertices of
$G_{1}\underset{=}{\lor}G_{2}$, we get

$\displaystyle L\left(G_{1}\underset{=}{\vee}G_{2}\right)=$
$\displaystyle\left(\begin{array}[]{ccc}\left(n_{1}+n_{2}-1\right)I_{n_{1}}-A\left(G_{1}\right)&-A\left(\overline{G_{1}}\right)&-J_{n_{1}\times\,n_{2}}\\\
\\\
-A\left(\overline{G_{1}}\right)&\left(n_{1}-1\right)I_{n_{1}}-D\left(G_{1}\right)&O_{n_{1}\times\,n_{2}}\\\
\\\
-J_{n_{2}\times\,n_{1}}&O_{n_{2}\times\,n_{1}}&D\left(G_{2}\right)+n_{1}I_{n_{2}}-A\left(G_{2}\right)\end{array}\right)$
$\displaystyle=$
$\displaystyle\left(\begin{array}[]{ccc}\left(n_{1}+n_{2}-1\right)I_{n_{1}}+L\left(G_{1}\right)-D\left(G_{1}\right)&-A\left(\overline{G_{1}}\right)&-J_{n_{1}\times\,n_{2}}\\\
\\\
-A\left(\overline{G_{1}}\right)&\left(n_{1}-1\right)I_{n_{1}}-D\left(G_{1}\right)&O_{n_{1}\times\,n_{2}}\\\
\\\
-J_{n_{2}\times\,n_{1}}&O_{n_{2}\times\,n_{1}}&n_{1}I_{n_{2}}+L\left(G_{2}\right)\end{array}\right).$

The Laplacian characteristic polynomial is

$\displaystyle
f_{{}_{L\left(G_{1}\underset{=}{\vee}G_{2}\right)}}\left(x\right)=$
$\displaystyle
det\left(xI_{2n_{1}+n_{2}}-L\left(G_{1}\underset{=}{\vee}G_{2}\right)\right)$
$\displaystyle=$ $\displaystyle
det\left(\begin{array}[]{cc|c}\left(x-n_{1}-n_{2}+1\right)I_{n_{1}}-L\left(G_{1}\right)+D\left(G_{1}\right)&A\left(\overline{G_{1}}\right)&\,\,\,\,\,\,\,\,\,\,J_{n_{1}\times\,n_{2}}\\\
&\\\
\,\,A\left(\overline{G_{1}}\right)&\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)&\,\,\,\,\,\,\,\,\,\,O_{n_{1}\times\,n_{2}}\\\
\hline\cr&\\\
\text{\emph{J}}_{n_{2}\times\,n_{1}}&O_{n_{2}\times\,n_{1}}&\left(x-n_{1}\right)I_{n_{2}}-L\left(G_{2}\right)\end{array}\right)$
$\displaystyle=$ $\displaystyle
det\left(\left(x-n_{1}\right)I_{n_{2}}-L\left(G_{2}\right)\right)det\left(\left(xI_{2n_{1}+n_{2}}-L\left(G_{1}\underset{=}{\vee}G_{2}\right)\right)\left/\left((x-n_{1})I_{n_{2}}-L(G_{2})\right)\right.\right),$

by the Lemma of Schur (Lemma 3.5).

By Lemma 3.6,

$\displaystyle\left(xI_{2n_{1}+n_{2}}-L\left(G_{1}\underset{=}{\vee}G_{2}\right)\right)\left/\left((x-n_{1})I_{n_{2}}-L(G_{2})\right)=\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\right.$
$\displaystyle=\left(\begin{array}[]{cc}\left(x-n_{1}-n_{2}+1\right)I_{n_{1}}-L\left(G_{1}\right)+D\left(G_{1}\right)-\Gamma_{L\left(G_{2}\right)}\left(x-n_{1}\right)J_{n_{1}\times\,n_{1}}&A\left(\overline{G_{1}}\right)\\\
\\\
A\left(\overline{G_{1}}\right)&\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\end{array}\right).$

Using again Lemma 3.5 , we get

$det\left(\left(xI_{2n_{1}+n_{2}}-L\left(G_{1}\underset{=}{\vee}G_{2}\right)\right)\left/\left((x-n_{1})I_{n_{2}}-L(G_{2})\right)\right.\right)=det\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)det\left(B-\Gamma_{L\left(G_{2}\right)}\left(x-n_{1}\right)J_{n_{1}\times\,n_{1}}\right)$

where

$B=\left(x-n_{1}-n_{2}+1\right)I_{n_{1}}-L\left(G_{1}\right)+D\left(G_{1}\right)-A\left(\overline{G_{1}}\right)\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)^{-1}A\left(\overline{G_{1}}\right).$

By Lemma 3.7 we get

$\displaystyle
det\left(\left(xI_{2n_{1}+n_{2}}-L\left(G_{1}\underset{=}{\vee}G_{2}\right)\right)\left/\left((x-n_{1})I_{n_{2}}-L(G_{2})\right)\right.\right)=\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$
$\displaystyle=det\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)\left(det\left(B\right)-\varGamma_{L\left(G_{2}\right)}\left(x-n_{1}\right)\mathbf{1}_{n_{1}}^{T}adj\left(B\right)\mathbf{1}_{n_{1}}\right)\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$
$\displaystyle=det\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)det\left(B\right)\left[1-\varGamma_{L\left(G_{2}\right)}\left(x-n_{1}\right)\mathbf{1}_{n_{1}}^{T}B^{-1}\mathbf{1}_{n_{1}}\right]\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$
$\displaystyle\,\,=det\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$
$\displaystyle\cdot
det\left(\left(x-n_{1}-n_{2}+1\right)I_{n_{1}}-L\left(G_{1}\right)+D\left(G_{1}\right)-A\left(\overline{G_{1}}\right)\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)^{-1}A\left(\overline{G_{1}}\right)\right)\,\,\,\,\,\,$
$\displaystyle\cdot\left[1-\varGamma_{{}_{L\left(G_{2}\right)}}\left(x-n_{1}\right)\varGamma_{{}_{L\left(G_{1}\right)-D\left(G_{1}\right)+A\left(\overline{G_{1}}\right)\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)^{-1}A\left(\overline{G_{1}}\right)}}\left(x-n_{1}-n_{2}+1\right)\right].\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$

Thus

$\displaystyle
f_{{}_{L\left(G_{1}\underset{=}{\vee}G_{2}\right)}}\left(x\right)$
$\displaystyle=det\left(\left(x-n_{1}\right)I_{n_{2}}-L\left(G_{2}\right)\right)det\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)$
$\displaystyle\cdot
det\left(\left(x-n_{1}-n_{2}+1\right)I_{n_{1}}-L\left(G_{1}\right)+D\left(G_{1}\right)-A\left(\overline{G_{1}}\right)\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)^{-1}A\left(\overline{G_{1}}\right)\right)$
$\displaystyle\cdot\left[1-\varGamma_{{}_{L\left(G_{2}\right)}}\left(x-n_{1}\right)\varGamma_{{}_{L\left(G_{1}\right)-D\left(G_{1}\right)+A\left(\overline{G_{1}}\right)\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)^{-1}A\left(\overline{G_{1}}\right)}}\left(x-n_{1}-n_{2}+1\right)\right].$

The proof of (b) is similar. ∎

###  4.3 Signless Laplacian characteristic polynomial

######  Theorem 4.3.

_Let $G_{i}$ be a graph on $n_{i}$ vertices for $i=1,2$. Then_

  * _(a)_

__

$\displaystyle
f_{{}_{Q\left(G_{1}\underset{=}{\vee}G_{2}\right)}}\left(x\right)$
$\displaystyle=det\left(\left(x-n_{1}\right)I_{n_{2}}-Q\left(G_{2}\right)\right)det\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)$
$\displaystyle\cdot
det\left(\left(x-n_{1}-n_{2}+1\right)I_{n_{1}}-Q\left(G_{1}\right)+D\left(G_{1}\right)-A\left(\overline{G_{1}}\right)\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)^{-1}A\left(\overline{G_{1}}\right)\right)$
$\displaystyle\cdot\left[1-\varGamma_{{}_{Q\left(G_{2}\right)}}\left(x-n_{1}\right)\varGamma_{{}_{Q\left(G_{1}\right)-D\left(G_{1}\right)+A\left(\overline{G_{1}}\right)\left(\left(x-n_{1}+1\right)I_{n_{1}}+D\left(G_{1}\right)\right)^{-1}A\left(\overline{G_{1}}\right)}}\left(x-n_{1}-n_{2}+1\right)\right].$

  * _(b)_

__

$\displaystyle f_{{}_{Q\left(G_{1}\veebar G_{2}\right)}}$
$\displaystyle=det\left(\left(x-n_{1}\right)I_{n_{2}}-Q\left(G_{2}\right)\right)det\left(xI_{n_{1}}-D\left(G_{1}\right)\right)$
$\displaystyle\cdot
det\left(\left(x-n_{2}\right)I_{n_{1}}-Q\left(G_{1}\right)-D\left(G_{1}\right)-A\left(G_{1}\right)\left(xI_{n_{1}}-D\left(G_{1}\right)\right)^{-1}A\left(G_{1}\right)\right)$
$\displaystyle\cdot\left[1-\varGamma_{{}_{Q\left(G_{2}\right)}}\left(x-n_{1}\right)\varGamma_{{}_{Q\left(G_{1}\right)+D\left(G_{1}\right)+A\left(G_{1}\right)\left(xI_{n_{1}}-D\left(G_{1}\right)\right)^{-1}A\left(G_{1}\right)}}\left(x-n_{2}\right)\right].$

###### Proof.

The proof is similar to the proof of Theorem 4.2. ∎

######  Corollary 4.4.

_Let $F$ and $H$ be r-regular non isomorphic cospectral graphs. Then for every
$G$,_

  * _a)_

_$G\veebar F$ and $G\veebar H$ are $\left\\{A,Q,L\right\\}$NICS._

  * _b)_

_$G\underset{=}{\lor}F$ and $G\underset{=}{\lor}H$ are
$\left\\{A,Q,L\right\\}$NICS._

###### Proof.

(a)_ $G\veebar F$ _and _ $G\veebar H$ _are non isomorphic since $F$ and $H$
are non isomorphic. By Theorems 4.1, 4.2 and 4.3, $f_{A(G\veebar
F)}\left(x\right)=f_{A(G\veebar H)}\left(x\right)$, $f_{{}_{L\left(G\veebar
F\right)}}\left(x\right)=f_{{}_{L\left(G\veebar H\right)}}\left(x\right)$ and
$f_{{}_{Q\left(G\veebar F\right)}}\left(x\right)=f_{{}_{Q\left(G\veebar
H\right)}}\left(x\right)$ since the matrices $A(F)$ and $A(H)$ have the same
coronal (Lemma 3.3) and the same characteristic polynomial. This completes the
proof of (a).

The proof of (b) is similar.
∎

######  Corollary 4.5.

_Let $F$and $H$ be r-regular non isomorphic cospectral graphs. Then for every
$G$,_

  * _a)_

_$F\veebar G$ and $H\veebar G$ are $\left\\{A,Q,L\right\\}$NICS._

  * _b)_

_$F\underset{=}{\lor}G$ and $H\underset{=}{\lor}G$ are
$\left\\{A,Q,L\right\\}$NICS._

###### Proof.

The proof is similar to the proof of Corollary 4.4. ∎

######  Remark 4.6.

_The following examples demonstrate the importance of the regularity of the
graphs $F$ and $H$._

######  Example 4.7.

The graphs $F$ and $H$ in Figure 4.1 are non regular and $A$-cospectral[10].
The joins $K_{2}\veebar F$ and $K_{2}\veebar H$ in Figure 4.2 are not
$A$-cospectral since the $A$-spectrum of $K_{2}\veebar F$ is {$-2.2332$, $-2$,
$-1.618$, $0^{[3]}$, $0.577$, $0.618$, $4.6562$} and the $A$-spectrum of
$K_{2}\veebar H$ is $\\{-2.7039,-1.618,-1.2467,0^{[3]},0.2526,0.618,4.698\\}$.
The joins $K_{2}\underset{=}{\vee}F$ and $K_{2}\underset{=}{\vee}H$ in Figure
4.3 are not $A$-cospectral since the $A$-spectrum of
$K_{2}\underset{=}{\vee}F$ is {$(-2)^{[2]}$, $-1$, $0^{[4]}$, $0.4384$,
$4.5616$} and the $A$-spectrum of $K_{2}\underset{=}{\vee}H$ is
$\\{-2.6056,(-1)^{[2[},0^{[5]},4.6056\\}$. The joins $F\veebar K_{2}$ and
$H\veebar K_{2}$ in Figure 4.4 are not $A$-cospectral since the $A$-spectrum
of $F\veebar K_{2}$ is {$-3.2361$, $-2.5205$, $-1$, $-0.5812$, $0^{[5]}$,
$1.0895$, $1.2361$, $5.0122$} and the $A$-spectrum of $H\veebar K_{2}$ is
{$-3.5337$, $-2.1915$, $-1$, $0^{[6]}$, $0.3034$, $1.3403$, $5.0815\\}$ and
the joins $F\underset{=}{\lor}K_{2}$ and $H\underset{=}{\lor}K_{2}$ in Figure
4.5 are not $A$-cospectral since the $A$-spectrum of
$F\underset{=}{\lor}K_{2}$ is {$-3.1903$, $-2.4142$, $-1.2946$, $(-1)^{[3]}$,
$0.4046$, $0.4142$, $1^{[2]}$, $1.8201$, $5.2602\\}$ and the $A$-spectrum of
$H\underset{=}{\lor}K_{2}$ is
$\\{-4.1337,(-1)^{[5]},0,0.8194,1^{[3]},5.3143\\}$.

(a) $F$

(b) $H$

Figure 4.1: Two non regular $A$-cospectral graphs $F$ and $H$ .

(a) $K_{2}\veebar F$ (b) $K_{2}\veebar H$

Figure 4.2: Two non A-cospectral graphs $K_{2}\veebar F$ and $K_{2}\veebar H.$

(a) $K_{2}\underset{=}{\lor}$F (b) $K_{2}\underset{=}{\lor}$H

Figure 4.3: Two non A-cospectral graphs $K_{2}\underset{=}{\lor}$F and
$K_{2}\underset{=}{\lor}$H.

(a) F$\veebar K_{2}$

(b) H$\veebar K_{2}$

Figure 4.4: Two non A-cospectral graphs F$\veebar K_{2}$ and $\text{H$\veebar
K_{2}$}.$

(a) F$\underset{=}{\lor}K_{2}$ (b) H$\underset{=}{\lor}K_{2}$

Figure 4.5: Two non A-cospectral graphs F$\underset{=}{\lor}K_{2}$ and
$\text{H$\underset{=}{\lor}K_{2}$}.$

######  Remark 4.8.

_Numerical computations suggest that in the corollaries_ _4.4_ _and_ _4.5_ _,
$\left\\{A,Q,L\right\\}$ can be replaced by
$\left\\{A,Q,L,\mathcal{L}\right\\}$. _

######  Conjecture 4.9.

  * _a)_

_Let $H_{1}$ and $H_{2}$ be regular non isomorphic cospectral graphs. Then for
every $G$, $G\veebar H_{1}$ and $G\veebar H_{2}$ are
$\left\\{A,Q,L,\mathcal{L}\right\\}$NICS and $G\underset{=}{\lor}H_{1}$ and
$G\underset{=}{\lor}H_{2}$ are $\left\\{A,Q,L,\mathcal{L}\right\\}$NICS._

  * _b)_

_Let $G_{1}$ and $G_{2}$ be regular non isomorphic cospectral graphs. Then for
every $H$, $G_{1}\veebar H$ and $G_{2}\veebar H$ are
$\left\\{A,Q,L,\mathcal{L}\right\\}$NICS and $G_{1}\underset{=}{\lor}H$ and
$G_{2}\underset{=}{\lor}H$ are $\left\\{A,Q,L,\mathcal{L}\right\\}$NICS._

##  5 $\mathcal{L}-Spectra$ of NS Joins

Let $G_{i},H_{i}$ be $r_{i}$-regular graphs, i = 1, 2. Lu, Ma and Zhang showed
that if $G_{1}$ and $H_{1}$ are cospectral and $G_{2}$ and $H_{2}$ are
cospectral and non isomorphic, then $G_{1}\veebar G_{2}$ and $H_{1}\veebar
H_{2}$ are $\left\\{A,L,Q\right\\}$NICS. In this section,we extend this result
by showing that $G_{1}\veebar G_{2}$ and $H_{1}\veebar H_{2}$ are
$\left\\{A,L,Q,\mathcal{L}\right\\}$NICS. To do it we determine the spectrum
of the normalized Laplacian of the graph $G_{1}\veebar G_{2}.$

######  Theorem 5.1.

_Let G 1 be a r1-regular graph with n1 vertices and $G_{2}$ be a
$r_{2}$-regular graph with $n_{2}$vertices. Then the normalized Laplacian
spectrum of $G_{1}\veebar G_{2}$ consists of:_

  * •

_$1+\frac{r_{2}\left(\delta_{i}\left(G_{2}\right)-1\right)}{n_{1}+r_{2}}$ for
$i=2,3,...,n_{2};$_

  * •

_$1+\frac{\left(\delta_{i}\left(G_{1}\right)-1\right)\left(\sqrt{9r_{1}^{2}+4r_{1}n_{2}}+r_{1}\right)}{2\left(2r_{1}+n_{2}\right)}$
for $i=2,3,...,n_{1};$_

  * •

_$1+\frac{\left(1-\delta_{i}\left(G_{1}\right)\right)\left(\sqrt{9r_{1}^{2}+4r_{1}n_{2}}-r_{1}\right)}{2\left(2r_{1}+n_{2}\right)}$
for $i=2,3,...,n_{1};$_

  * •

_the three roots of the equation_

$\left(2r_{1}r_{2}+2r_{1}n_{1}+n_{2}r_{2}+n_{1}n_{2}\right)x^{3}-\left(3r_{1}r_{2}+5r_{1}n_{1}+2r_{2}n_{2}+3n_{1}n_{2}\right)x^{2}+\left(3r_{1}n_{1}+n_{2}r_{2}+2n_{1}n_{2}\right)x=0.$

###### Proof.

Let $u_{1},u_{2},\ldots,u_{n_{1}}$be the vertices of $G_{1}$,
$u^{\prime}_{1},u^{\prime}_{2},\ldots,u^{\prime}_{n_{1}}be$ the vertices added
by the splitting and $v_{1},v_{2},...,v_{n_{2}}$ be the vertices of $G_{2}$.
Under this vertex partitioning the adjacency matrix of $G_{1}\veebar G_{2}$
is,

$A\left(G_{1}\veebar
G_{2}\right)=\left(\begin{array}[]{ccc}A\left(G_{1}\right)&\,\,\,A\left(G_{1}\right)&J_{n_{1}\times
n_{2}}\\\ A\left(G_{1}\right)&O_{n_{1}\times n_{1}}&O_{n_{1}\times n_{2}}\\\
J_{n_{2}\times n_{1}}&O_{n_{2}\times
n_{1}}&A\left(G_{2}\right)\end{array}\right)$

The corresponding degrees matrix of $G_{1}\veebar G_{2}$ is,

$D\left(G_{1}\veebar
G_{2}\right)=\left(\begin{array}[]{ccc}\left(2r_{1}+n_{2}\right)I_{n_{1}}&O_{n_{1}\times
n_{1}}&O_{n_{1}\times n_{2}}\\\ O_{n_{1}\times
n_{1}}&r_{1}I_{n_{1}}&O_{n_{1}\times n_{2}}\\\ O_{n_{2}\times
n_{1}}&O_{n_{2}\times
n_{1}}&\,\,\,\,\,\,\,\,\,\left(r_{2}+n_{1}\right)I_{n_{2}}\end{array}\right).$

By simple calculation we get

$\mathcal{L}\left(G_{1}\veebar
G_{2}\right)=\left(\begin{array}[]{ccc}I_{n_{1}}-\frac{A\left(G_{1}\right)}{2r_{1}+n_{2}}&\frac{-A\left(G_{1}\right)}{\sqrt{r_{1}\left(2r_{1}+n_{2}\right)}}&\frac{-J_{n_{1}\times
n_{2}}}{\sqrt{\left(2r_{1}+n_{2}\right)\left(r_{2}+n_{1}\right)}}\\\ \\\
\frac{-A\left(G_{1}\right)}{\sqrt{r_{1}\left(2r_{1}+n_{2}\right)}}&I_{n_{1}}&O_{n_{1}\times
n_{2}}\\\ \\\ \frac{-J_{n_{2}\times
n_{1}}}{\sqrt{\left(2r_{1}+n_{2}\right)\left(r_{2}+n_{1}\right)}}&O_{n_{2}\times
n_{1}}&I_{n_{2}}-\frac{A\left(G_{2}\right)}{r_{2}+n_{1}}\end{array}\right).$

We prove the theorem by constructing an orthogonal basis of eigenvectors of
$\mathcal{L}\left(G_{1}\veebar G_{2}\right)$. Since $G_{2}$ is
$r_{2}$-regular, the vector $\mathbf{1}_{n_{2}}$is an eigenvector of
$A(G_{2})$ that corresponds to $\lambda_{1}\left(G_{2}\right)=r_{2}$. For
$i=2,3,\ldots,n_{2}$ let $Z_{i}$ be an eigenvector of $A\left(G_{2}\right)$
that corresponds to $\lambda_{i}\left(G_{2}\right)$. Then
$\mathbf{1}_{n_{2}}^{T}Z_{i}=0$ and $\left(0_{1\times n_{1}},0_{1\times
n_{1}},Z_{i}^{T}\right)^{T}$ is an eigenvector of
$\mathcal{L}\left(G_{1}\veebar G_{2}\right)$ corresponding to the eigenvalue
$1-\frac{\lambda_{i}\left(G_{2}\right)}{r_{2}+n_{1}}$ .

By Remark 2.8,
$1+\frac{r_{2}\left(\delta_{i}\left(G_{2}\right)-1\right)}{n_{1}+r_{2}}$ are
eigenvalues of $\mathcal{L}\left(G_{1}\veebar G_{2}\right)$ for
$i=2,...,n_{2}.$

For $i=2,...,n_{1}$, let $X_{i}$ be an eigenvector of $A(G_{1})$ corresponding
to the eigenvalue $\lambda_{i}\left(G_{1}\right)$. We now look for a non zero
real number $\alpha$ such that $\left(\begin{array}[]{ccc}X_{i}^{T}&\alpha
X_{i}^{T}&0_{1\times n_{2}}\end{array}\right)^{T}$is an eigenvector of
$\mathcal{L}(G_{1}\veebar G_{2})$.

$\mathcal{L}\left(\begin{array}[]{c}X_{i}\\\ \alpha X_{i}\\\ 0_{n_{2}\times
1}\end{array}\right)=\left(\begin{array}[]{c}X_{i}-\frac{\lambda_{i}\left(G_{1}\right)}{2r_{1}+n_{2}}X_{i}-\frac{\lambda_{i}\left(G_{1}\right)\alpha}{\sqrt{r_{1}\left(2r_{1}+n_{2}\right)}}X_{i}\\\
-\frac{\lambda_{i}\left(G_{1}\right)}{\sqrt{r_{1}\left(2r_{1}+n_{2}\right)}}X_{i}+\alpha
X_{i}\\\ 0_{n_{2}\times
1}\end{array}\right)=\left(\begin{array}[]{c}1-\frac{\lambda_{i}\left(G_{1}\right)}{2r_{1}+n_{2}}-\frac{\lambda_{i}\left(G_{1}\right)\alpha}{\sqrt{r_{1}\left(2r_{1}+n_{2}\right)}}\\\
-\frac{\lambda_{i}\left(G_{1}\right)}{\alpha\sqrt{r_{1}\left(2r_{1}+n_{2}\right)}}+1\\\
0_{n_{2}\times 1}\end{array}\right)\left(\begin{array}[]{c}X_{i}\\\ \alpha
X_{i}\\\ 0_{n_{2}\times 1}\end{array}\right),$

so, $\alpha$ must be a root of the equation

$1-\frac{\lambda_{i}\left(G_{1}\right)}{2r_{1}+n_{2}}-\frac{\lambda_{i}\left(G_{1}\right)\alpha}{\sqrt{r_{1}\left(2r_{1}+n_{2}\right)}}=-\frac{\lambda_{i}\left(G_{1}\right)}{\alpha\sqrt{r_{1}\left(2r_{1}+n_{2}\right)}}+1,$
(5.1)
$\sqrt{2r_{1}+n_{2}}\alpha^{2}+\sqrt{r_{1}}\alpha-\sqrt{2r_{1}+n_{2}}=0.$

Thus, $\alpha=\frac{2\sqrt{2r_{1}+n_{2}}}{\sqrt{9r_{1}+4n_{2}}+\sqrt{r_{1}}}$
or $\alpha=\frac{-2\sqrt{2r_{1}+n_{2}}}{\sqrt{9r_{1}+4n_{2}}-\sqrt{r_{1}}}$.
Substituting the values of $\alpha$ in the right side of

(5.1), we get by Remark 2.8 that

$1+\frac{\left(\delta_{i}\left(G_{1}\right)-1\right)\left(\sqrt{9r_{1}^{2}+4r_{1}n_{2}}+r_{1}\right)}{n_{1}+r_{2}}$
,
$1+\frac{\left(1-\delta_{i}\left(G_{1}\right)\right)\left(\sqrt{9r_{1}^{2}+4r_{1}n_{2}}-r_{1}\right)}{2\left(2r_{1}+n_{2}\right)}$
are eigenvalues of $\mathcal{L}\left(G_{1}\veebar G_{2}\right)$ for
$i=2,3,...,n_{1}.$

So far, we obtained $n_{2}-1+2\left(n_{1}-1\right)=2n_{1}+n_{2}-3$ eigenvalues
of $\mathcal{L}\left(G_{1}\veebar G_{2}\right)$. Their eigenvectors are
orthogonal to $\left(\mathbf{1}_{n_{1}}^{T},0_{1\times n_{1}},0_{1\times
n_{2}}\right)^{T},$$\left(0_{1\times n_{1}},1_{n_{1}}^{T},0_{1\times
n_{2}}\right)^{T}$ and $\left(0_{1\times n_{1}},0_{1\times
n_{1}},1_{n_{2}}^{T}\right)^{T}.$

To find three additional eigenvalues, we look for eigenvectors of
$\mathcal{L}\left(G_{1}\veebar G_{2}\right)$ of the form
$Y=\left(\alpha\mathbf{1}_{n_{1}}^{T},\beta\mathbf{1}_{n_{1}}^{T},\gamma\mathbf{1}_{n_{2}}^{T}\right)^{T}$
for $\left(\alpha,\beta,\gamma\right)\neq\left(0,0,0\right)$. Let $x$ be an
eigenvalue of $\mathcal{L}\left(G\veebar G_{2}\right)$ corresponding to the
eigenvector $Y$ . From $\mathcal{L}Y=xY$ we get

$\begin{cases}\alpha-\frac{r_{1}}{2r_{1}+n_{2}}\alpha\,-\frac{r_{1}}{\sqrt{r_{1}\left(2r_{1}+n_{2}\right)}}\beta\,-\,\frac{n_{2}}{\sqrt{\left(2r_{1}+n_{2}\right)\left(r_{2}+n_{1}\right)}}\gamma=\alpha
x\\\ \frac{-r_{1}}{\sqrt{r_{1}\left(2r_{1}+n_{2}\right)}}\alpha+\beta=\beta
x\\\
\frac{-n_{1}}{\sqrt{\left(2r_{1}+n_{2}\right)\left(r_{2}+n_{1}\right)}}\alpha+\gamma-\frac{r_{2}}{r_{2}+n_{1}}\gamma=\gamma
x.\end{cases}$

Thus

$\alpha-\frac{r_{1}}{2r_{1}+n_{2}}\alpha+\frac{r_{1}^{2}\alpha}{r_{1}(2r_{1}+n_{2})(x-1)}+\frac{n_{1}n_{2}(r_{2}+n_{1})\alpha}{(2r_{1}+n_{2})(r_{2}+n_{1})\left((x-1)(r_{2}+n_{1})+r_{2}\right)}=\alpha
x.$

Notice that $\alpha\neq 0$, since if $\alpha=0$ then $\alpha=\beta=\gamma=0$
and also $x\neq 1$ since $x=1$ implies that $\alpha=0$.

Dividing by $\alpha$, we get the following cubic equation

$\left(2r_{1}r_{2}+2r_{1}n_{1}+n_{2}r_{2}+n_{1}n_{2}\right)x^{3}-\left(3r_{1}r_{2}+5r_{1}n_{1}+2r_{2}n_{2}+3n_{1}n_{2}\right)x^{2}+\left(3r_{1}n_{1}+n_{2}r_{2}+2n_{1}n_{2}\right)x=0$

and this completes the proof. ∎

Now we can answer Question 2.16 by constructing pairs of non regular
$\left\\{A,L,Q,\mathcal{L}\right\\}$NICS graphs.

######  Corollary 5.2.

_Let $G_{i},H_{i}$ be $r_{i}$-regular graphs, i = 1, 2. If $G_{1}$ and $H_{1}$
are cospectral and $G_{2}$ and $H_{2}$ are cospectral and non isomorphic then
$G_{1}\veebar G_{2}$ and $H_{1}\veebar H_{2}$ are
$\left\\{A,L,Q,\mathcal{L}\right\\}$NICS. _

###### Proof.

_$G_{1}\veebar G_{2}$ _and _ $H_{1}\veebar H_{2}$ _are non isomorphic since
$G_{2}$ and $H_{2}$ are non isomorphic. By Theorem 5.1 and Theorems 3.1, 3.2
and 3.3 in [19], the __ graphs _ $H_{1}\veebar H_{2}$ _are _
$\left\\{A,L,Q,\mathcal{L}\right\\}$_NICS _._ ∎

######  Example 5.3.

Let $G_{1}=H_{1}=C_{4}$, and choose $G_{2}=G$ and $H_{2}=H$ where $G$ and $H$
are graphs in Figure 2.1, then the graphs in Figure 2.1 are
$\left\\{A,L,Q,\mathcal{L}\right\\}$NICS.

(a) $C_{4}\veebar G_{2}$ (b) $C_{4}\veebar H_{2}$

Figure 5.1: Non regular $\left\\{A,L,Q,\mathcal{L}\right\\}$NICS graphs.

##  6 Spectra of NNS Joins

In this section we compute the $A$-spectrum, $L$-spectrum, $Q$-spectrum and
$\mathcal{L}$-spectrum of G1$\underset{=}{\vee}$G2 where $G_{1}$ and $G_{2}$
are regular.

We use it to answer Question 2.16 by constructing pairs of non regular
$\left\\{A,L,Q,\mathcal{L}\right\\}$NICS graphs.

###  6.1 A-spectra of NNS join

The adjacency matrix of G1$\underset{=}{\vee}$ G2 can be written in a block
form

$A\left(G_{1}\underset{=}{\vee}G_{2}\right)=\left(\begin{array}[]{ccc}A\left(G_{1}\right)&\,\,\,\,A\left(\overline{G_{1}}\right)&\,\,\,\,\,J_{n_{1}\times
n_{2}}\\\ \\\
A\left(\stackrel{{\scriptstyle\text{\\_\\_\\_}}}{{G_{1}}}\right)&\,\,\,\,\,\,O_{n_{1}\times
n_{1}}&\,\,\,\,\,\,O_{n_{1}\times n_{2}}\\\ \\\ J_{n_{2}\times
n_{1}}&\,\,\,\,\,\,O_{n_{2}\times
n_{1}}&\,\,\,\,A\left(G_{2}\right)\end{array}\right)$ (6.1)

######  Theorem 6.1.

_Let G 1 be a r1-regular graph with n1 vertices and $G_{2}$ be a
$r_{2}$-regular graph with $n_{2}$vertices. Then the adjacency spectrum of
$G_{1}\underset{=}{\vee}G_{2}$ consists of:_

  * •

_(i) $\lambda_{j}\left(G_{2}\right)$ for each j = 2, 3, . . . , n2;_

  * •

_(ii) two roots of the equation_
__
_
$x^{2}-\left(\lambda_{i}\left(G_{1}\right)\right)x-\left(\lambda_{i}^{2}\left(G_{1}\right)+2\lambda_{i}\left(G_{1}\right)+1\right)=0$
for each i = 2, 3, . . . , n1;_

  * •

_(iii) the three roots of the equation_
__
_
$x^{3}-(r_{1}+r_{2})x^{2}+\left(r_{1}r_{2}-(n_{1}-r_{1}-1)^{2}-n_{1}n_{2}\right)x+r_{2}(n_{1}-r_{1}-1)^{2}=0$_

###### Proof.

By Theorem 4.1, the adjacency characteristic polynomial of
$G_{1}\underset{=}{\lor}G_{2}$ is

$\displaystyle f_{A(G_{1}\underset{=}{\vee}G_{2})}(x)$
$\displaystyle=x^{n_{1}}f_{{}_{A\left(G_{2}\right)}}(x)det\left(xI_{n_{1}}-A(G_{1})-\frac{1}{x}A^{2}(\overline{G_{1}})\right)\left[1-\varGamma_{A(G_{2})}(x)\varGamma_{A(G_{1})+\frac{1}{x}A^{2}(\overline{G_{1}})}(x)\right]$
$\displaystyle=x^{n_{1}}\stackrel{{\scriptstyle[}}{{j}}=1]{n_{2}}{\prod}\left(x-\lambda_{j}(G_{2})\right)det\left(xI_{n_{1}}-A(G_{1})-\frac{1}{x}A^{2}(\overline{G_{1}})\right)\left[1-\varGamma_{A(G_{2})}(x)\varGamma_{A(G_{1})+\frac{1}{x}A^{2}(\overline{G_{1}})}(x)\right]$

Since $G_{1}$ and $G_{2}$ are regular, we can use Lemma 3.3 to get

$\displaystyle f_{A(G_{1}\underset{=}{\vee}G_{2})}(x)$
$\displaystyle=x^{n_{1}}\stackrel{{\scriptstyle[}}{{j}}=1]{n_{2}}{\prod}\left(x-\lambda_{j}(G_{2})\right)det\left(xI_{n_{1}}-A(G_{1})-\frac{1}{x}A^{2}(\overline{G_{1}})\right)\left[1-\frac{n_{2}}{x-r_{2}}\,\frac{n_{1}}{x-r_{1}-\frac{1}{x}(n_{1}-r_{1}-1)^{2}}\right]$
$\displaystyle=x^{n_{1}}\stackrel{{\scriptstyle[}}{{j}}=1]{n_{2}}{\prod}\left(x-\lambda_{j}(G_{2})\right)det\left(xI_{n_{1}}-A(G_{1})-\frac{1}{x}(J-I-A(G_{1}))^{2}\right)\left[1-\frac{n_{1}n_{2}}{(x-r_{2})(x-r_{1}-\frac{1}{x}(n_{1}-r_{1}-1)^{2})}\right]$
$\displaystyle=x^{n_{1}}\stackrel{{\scriptstyle[}}{{j}}=1]{n_{2}}{\prod}\left(x-\lambda_{j}(G_{2})\right)det\left(xI_{n_{1}}-A(G_{1})-\frac{1}{x}(J^{2}-2J+I-2r_{1}J+2A(G_{1})+A^{2}(G_{1}))\right)$
$\displaystyle\cdot\left[1-\frac{n_{1}n_{2}}{(x-r_{2})(x-r_{1}-\frac{1}{x}(n_{1}-r_{1}-1)^{2})}\right]$
$\displaystyle=x^{n_{1}}\stackrel{{\scriptstyle[}}{{j}}=1]{n_{2}}{\prod}\left(x-\lambda_{j}(G_{2})\right)\left[det\left(B\right)-\frac{1}{x}(n_{1}-2-2r_{1})1_{n_{1}}^{T}adj\left(B\right)1_{n_{1}}\right]\left[1-\frac{n_{1}n_{2}}{(x-r_{2})(x-r_{1}-\frac{1}{x}(n_{1}-r_{1}-1)^{2})}\right],$

where
$B=(x-\frac{1}{x})I_{n_{1}}-(1+\frac{2}{x})A(G_{1})-\frac{1}{x}A^{2}(G_{1}).$
Thus, based on Definition 3.2 and Lemma 3.3, we have

$\displaystyle f_{A(G_{1}\underset{=}{\vee}G_{2})}(x)=$ $\displaystyle
x^{n_{1}}\stackrel{{\scriptstyle[}}{{j}}=1]{n_{2}}{\prod}\left(x-\lambda_{j}(G_{2})\right)\stackrel{{\scriptstyle[}}{{i}}=1]{n_{1}}{\prod}\left[\left(x-\frac{1}{x}\right)-\left(1+\frac{2}{x}\right)\lambda_{i}(G_{1})-\frac{1}{x}\lambda_{i}^{2}(G_{1})\right]$
$\displaystyle\cdot$
$\displaystyle\left[1-\frac{1}{x}(n_{1}-2-2r_{1})\varGamma_{\frac{1}{x}I_{n_{1}}+(1+\frac{2}{x})A(G_{1})+\frac{1}{x}A^{2}(G_{1})}(x)\right]\left[1-\frac{n_{1}n_{2}}{(x-r_{2})(x-r_{1}-\frac{1}{x}(n_{1}-r_{1}-1)^{2})}\right]$
$\displaystyle=$ $\displaystyle
x^{n_{1}}\stackrel{{\scriptstyle[}}{{j}}=1]{n_{2}}{\prod}\left(x-\lambda_{j}(G_{2})\right)\stackrel{{\scriptstyle[}}{{i}}=1]{n_{1}}{\prod}\left[\left(x-\frac{1}{x}\right)-\left(1+\frac{2}{x}\right)\lambda_{i}(G_{1})-\frac{1}{x}\lambda_{i}^{2}(G_{1})\right]\left[1-\frac{n_{1}-2-2r_{1}}{x}\cdot\frac{n_{1}}{x-\frac{1}{x}-r_{1}-\frac{2r_{1}}{x}-\frac{r_{1}^{2}}{x}}\right]$
$\displaystyle\cdot$
$\displaystyle\left[1-\frac{n_{1}n_{2}}{(x-r_{2})(x-r_{1}-\frac{1}{x}(n_{1}-r_{1}-1)^{2})}\right]$
$\displaystyle=\stackrel{{\scriptstyle[}}{{j}}=1]{n_{2}}{\prod}\left(x-\lambda_{j}(G_{2})\right)x^{n_{1}}\stackrel{{\scriptstyle[}}{{i}}=1]{n_{1}}{\prod}\left(\left(x-\frac{1}{x}\right)-\left(1+\frac{2}{x}\right)\lambda_{i}(G_{1})-\frac{1}{x}\lambda_{i}^{2}(G_{1})\right)$
$\displaystyle\cdot\left(1-\frac{n_{1}(n_{1}-2-2r_{1})}{x^{2}-r_{1}x-r_{1}^{2}-2r_{1}-1}\right)\left(\frac{(x-r_{2})\left(x(x-r_{1})-(n_{1}-r_{1}-1)^{2}\right)-n_{1}n_{2}x}{(x-r_{2})\left(x(x-r_{1})-(n_{1}-r_{1}-1)^{2}\right)}\right)$
$\displaystyle=\stackrel{{\scriptstyle[}}{{j}}=2]{n_{2}}{\prod}\left(x-\lambda_{j}(G_{2})\right)\stackrel{{\scriptstyle[}}{{i}}=2]{n_{1}}{\prod}\left(x^{2}-1-(x+2)\lambda_{i}(G_{1})-\lambda_{i}^{2}(G_{1})\right)$
$\displaystyle\cdot\left(x(x-r_{1})-(n_{1}-r_{1}-1)^{2}\right)\left(\frac{(x-r_{2})\left(x(x-r_{1})-(n_{1}-r_{1}-1)^{2}\right)-n_{1}n_{2}x}{(x-r_{2})\left(x(x-r_{1})-(n_{1}-r_{1}-1)^{2}\right)-n_{1}n_{2}x}\right)$
$\displaystyle=\stackrel{{\scriptstyle[}}{{j}}=2]{n_{2}}{\prod}\left(x-\lambda_{j}(G_{2})\right)\stackrel{{\scriptstyle[}}{{i}}=2]{n_{1}}{\prod}\left(x^{2}-1-(x+2)\lambda_{i}(G_{1})-\lambda_{i}^{2}(G_{1})\right)$
$\displaystyle\cdot\left((x-r_{2})\left(x(x-r_{1})-(n_{1}-r_{1}-1)^{2}\right)-n_{1}n_{2}x\right)$
$\displaystyle=\stackrel{{\scriptstyle[}}{{j}}=2]{n_{2}}{\prod}\left(x-\lambda_{j}(G_{2})\right)\stackrel{{\scriptstyle[}}{{i}}=2]{n_{1}}{\prod}\left(x^{2}-(\lambda_{i}(G_{1}))x-\left(\lambda_{i}^{2}(G_{1})+2\lambda_{i}(G_{1})+1\right)\right)$
$\displaystyle\cdot\left(x^{3}-(r_{1}+r_{2})x^{2}+(r_{1}r_{2}-(n_{1}-r_{1}-1)^{2}-n_{1}n_{2})x+r_{2}(n_{1}-r_{1}-1)^{2}\right).$

∎

###  6.2 L-spectra of NNS join

The degrees of the vertices of $G_{1}\underset{=}{\vee}G_{2}$ are:

d${}_{G_{1}\underset{=}{\vee}G_{2}}$ ($u_{i}$) = n${}_{1}+n_{2}$$-1$, i = 1, .
. . , n1,

d${}_{G_{1}\underset{=}{\vee}G_{2}}$($u$${}_{i}^{\prime}$) =
n${}_{1}-r_{1}$$-1$, i = 1, . . . , n1,

d${}_{G_{1}\underset{=}{\vee}G_{2}}$ ($v_{j}$) = r2 \+ n1, j = 1, . . . , n2,

so the degrees matrix of $G_{1}\underset{=}{\vee}G_{2}$, that corresponds to
(6.1) is

$D\left(G_{1}\underset{=}{\vee}G_{2}\right)=\left(\begin{array}[]{ccc}(n_{1}+n_{2}-1)I_{n_{1}}&O_{n_{1}\times
n_{1}}&\,O_{n_{1}\times n_{2}}\\\ \\\ O_{n_{1}\times
n_{1}}&(n_{1}-r_{1}-1)I_{n_{1}}&\,O\\\ \\\ O_{n_{2}\times
n_{1}}&O_{n_{2}\times n_{1}}&\,\,(r_{2}+n_{1})I_{n_{2}}\end{array}\right)$
(6.2)

######  Theorem 6.2.

_Let G 1 be a r1-regular graph with n1 vertices and $G_{2}$ be a
$r_{2}$-regular graph with $n_{2}$vertices. Then the Laplacian spectrum of
$G_{1}\underset{=}{\lor}G_{2}$ consists of:_

  * •

_$n_{1}+\mu_{j}(G_{2})$ for each $j=2,3,...,n_{2}$; _

  * •

_two roots of the equation_

$x^{2}+(2r_{1}-2n_{1}-n_{2}-\mu_{i}(G_{1})+2)x+n_{1}^{2}-2r_{1}n_{1}-2n_{1}+n_{1}n_{2}-r_{1}n_{2}-n_{2}+\mu_{i}(G_{1})(n_{1}+r_{1}+1-\mu_{i}(G_{1}))=0$

_for each $i=2,3,...,n_{1}$; _

  * •

_the three roots of the equation_

$x^{3}+\left(2r_{1}-3n_{1}-n_{2}+2\right)x^{2}+\left(n_{1}n_{2}-n_{2}r_{1}-n_{2}+2n_{1}^{2}-2r_{1}n_{1}-2n_{1}\right)x=0.$

###### Proof.

By substituting $D\left(G_{1}\right)=r_{1}I_{n_{1}}$ in Theorem 4.2, the
Laplacian characteristic polynomial of $G_{1}\underset{=}{\lor}G_{2}$ is

$\displaystyle
f_{{}_{L\left(G_{1}\underset{=}{\vee}G_{2}\right)}}\left(x\right)$
$\displaystyle=det\left(\left(x-n_{1}\right)I_{n_{2}}-L\left(G_{2}\right)\right)det\left(x-n_{1}+1+r_{1}\right)I_{n_{1}}$
$\displaystyle\cdot
det\left(\left(x-n_{1}-n_{2}+r_{1}+1\right)I_{n_{1}}-L\left(G_{1}\right)-\frac{1}{x-n_{1}+r_{1}+1}A^{2}\left(\overline{G_{1}}\right)\right)$
$\displaystyle\cdot\left[1-\varGamma_{{}_{L\left(G_{2}\right)}}\left(x-n_{1}\right)\varGamma_{{}_{L\left(G_{1}\right)+\frac{1}{x-n_{1}+1+r_{1}}A^{2}\left(\overline{G_{1}}\right)}}\left(x-n_{1}-n_{2}+1+r_{1}\right)\right].$

Using Lemma 3.3, we obtain

$\displaystyle
f_{{}_{L\left(G_{1}\underset{=}{\vee}G_{2}\right)}}\left(x\right)$
$\displaystyle=det\left(\left(x-n_{1}\right)I_{n_{2}}-L\left(G_{2}\right)\right)\left(x-n_{1}+r_{1}+1\right)^{n_{1}}$
$\displaystyle\cdot
det\left(\left(x-n_{1}-n_{2}+r_{1}+1\right)I_{n_{1}}-L\left(G_{1}\right)-\frac{1}{x-n_{1}+r_{1}+1}A^{2}\left(\overline{G_{1}}\right)\right)$
$\displaystyle\cdot\left[1-\frac{n_{2}n_{1}}{\left(x-n_{1}\right)\left(x-n_{1}-n_{2}+1+r_{1}-\frac{\left(n_{1}-r_{1}-1\right)^{2}}{x-n_{1}+r_{1}+1}\right)}\right]$
$\displaystyle=\stackrel{{\scriptstyle[}}{{j}}=1]{n_{2}}{\prod}\left(x-n_{1}-\mu_{j}\left(G_{2}\right)\right)\left(x-n_{1}+r_{1}+1\right)^{n_{1}}\left(\left(x-n_{1}-n_{2}+1+r_{1}\right)-\frac{\left(n_{1}-r_{1}-1\right)^{2}}{x-n_{1}+r_{1}+1}\right)$
$\displaystyle\cdot\stackrel{{\scriptstyle[}}{{i}}=2]{n_{1}}{\prod}\left(x-n_{1}-n_{2}+1+r_{1}-\mu_{i}\left(G_{1}\right)-\frac{\left(\mu_{i}\left(G_{1}\right)-r_{1}-1\right)^{2}}{x-n_{1}+r_{1}+1}\right)$
$\displaystyle\cdot\left[1-\frac{n_{2}n_{1}}{\left(x-n_{1}\right)\left(x-n_{1}-n_{2}+1+r_{1}-\frac{\left(n_{1}-r_{1}-1\right)^{2}}{x-n_{1}+r_{1}+1}\right)}\right]$
$\displaystyle=\stackrel{{\scriptstyle[}}{{j}}=2]{n_{2}}{\prod}\left(x-n_{1}-\mu_{j}\left(G_{2}\right)\right)\stackrel{{\scriptstyle[}}{{i}}=2]{n_{1}}{\prod}\left(\right.x^{2}+\left(2r_{1}-2n_{1}-n_{2}-\mu_{i}\left(G_{1}\right)+2\right)x+n_{1}^{2}-2r_{1}n_{1}$
$\displaystyle-2n_{1}+n_{1}n_{2}-r_{1}n_{2}-n_{2}+\mu_{i}\left(G_{1}\right)\left(n_{1}+r_{1}+1-\mu_{i}\left(G_{1}\right)\right)\left.\right)$
$\displaystyle\cdot\left[x^{3}+\left(2r_{1}-3n_{1}-n_{2}+2\right)x^{2}+\left(n_{1}n_{2}-n_{2}r_{1}-n_{2}+2n_{1}^{2}-2r_{1}n_{1}-2n_{1}\right)x\right].$

This completes the proof. ∎

###  6.3 Q-spectra of NNS join

######  Theorem 6.3.

_Let G 1 be a r1-regular graph with n1 vertices and $G_{2}$ be a
$r_{2}$-regular graph with $n_{2}$vertices.Then the signless Laplacian
spectrum of G1$\underset{=}{\vee}$ G2 consists of:_

  * •

_$n_{1}+\nu_{j}(G_{2})$ for each $j=2,3,...,n_{2};$_

  * •

_two roots of the equation_ _
$x^{2}+(2r_{1}-2n_{1}-n_{2}-\nu_{i}(G_{1})+2)x+n_{1}^{2}-2r_{1}n_{1}-2n_{1}+n_{1}n_{2}-r_{1}n_{2}-n_{2}+4r_{1}+\nu_{i}(G_{1})(n_{1}+r_{1}-3-\nu_{i}(G_{1}))$=0
for each $i=2,3,...,n_{1};$ _

  * •

_the three roots of the equation_ __

$x^{3}+\left(2-3n_{1}-n_{2}-2r_{2}\right)x^{2}+\left(n_{1}n_{2}-n_{2}r_{1}-n_{2}+2n_{1}^{2}+2r_{1}n_{1}-2n_{1}-2r_{1}-2r_{1}^{2}+4r_{2}n_{1}-4r_{2}+2r_{2}n_{2}\right)x\\\
+2n_{1}r_{1}^{2}+2r_{1}n_{1}-2r_{1}n_{1}^{2}-2r_{2}n_{1}n_{2}+2r_{1}r_{2}n_{2}+2r_{2}n_{2}+4r_{2}r_{1}^{2}+4r_{1}r_{2}-4r_{1}r_{2}n_{1}=0$

###### Proof.

The proof is similar to the proof of Theorem 6.2. ∎

###  6.4 $\mathcal{L}$-spectra of NNS join

Let $G_{1}$ be a $r_{1}$-regular graph on order $n_{1}$. Let $S$ be a subset
of $\left\\{2,3,\ldots,n_{1}\right\\}$ such that
$\delta_{i}\left(G_{1}\right)=1+\frac{1}{r_{1}}$ for $i\in S$, and denote the
cardinality of $S$ by $n(S)$. Let $G_{2}$ be a $r_{2}$-regular graph on order
$n_{2}$. In the following theorem we determine the normalized Laplacian
spectrum of $G_{1}\underset{=}{\vee}G_{2}$ in terms of the normalized
Laplacian eigenvalues of $G_{1}$ and $G_{2}.$ The proof is slightly more
complicated than the proof of Theorem 5.1 and we consider three cases.

######  Theorem 6.4.

__

  * _a)_

_If $S=\varPhi$, then the normalized Laplacian spectrum of
$G_{1}\underset{=}{\vee}G_{2}$ consists of:_
__
_i) $1+\frac{r_{2}\left(\delta_{i}\left(G_{2}\right)-1\right)}{n_{1}+r_{2}}$,
for each $i=2,3,...,n_{2}$;_
__
_ii)
$1+\frac{2\left(1+r_{1}-r_{1}\delta_{i}\left(G_{1}\right)\right)^{2}}{r_{1}\left(1-\delta_{i}\left(G_{1}\right)\right)\left(n_{1}-r_{1}-1\right)\mp\sqrt{\left(n_{1}-r_{1}-1\right)\left[r_{1}^{2}\left(1-\delta_{i}\left(G_{1}\right)\right)^{2}\left(n_{1}-r_{1}-1\right)+4\left(1+r_{1}-r_{1}\delta_{i}\left(G_{1}\right)\right)^{2}\left(n_{1}+n_{2}-1\right)\right]}}$
, for each i=2,3,…,$n_{1}$;_
__
_iii) the three roots of the equation_

$\displaystyle\left(n_{1}^{2}+n_{1}n_{2}-n_{1}+r_{2}n_{1}+r_{2}n_{2}-r_{2}\right)x^{3}-\left(3n_{1}^{2}+3n_{1}n_{2}-3n_{1}-r_{1}n_{1}+2r_{2}n_{1}+2r_{2}n_{2}-2r_{2}-r_{1}r_{2}\right)x^{2}$
$\displaystyle+\left(2n_{1}^{2}+2n_{1}n_{2}-2n_{1}-r_{1}n_{1}+r_{2}n_{2}\right)x=0.$

  * _b)_

_If $S=\left\\{2,3,\ldots,n_{1}\right\\}$, then the normalized Laplacian
spectrum of $G_{1}\underset{=}{\vee}G_{2}$ consists of:_
__
_i) $1+\frac{r_{2}\left(\delta_{i}\left(G_{2}\right)-1\right)}{n_{1}+r_{2}}$
for each $i=2,3,...,n_{2};$_
__
_ii) $(1+\frac{1}{n_{1}+n_{2}-1})^{[n_{1}-1]}$ , $0^{[n_{1}+1]}$ and
$\frac{n_{1}^{2}+2n_{1}n_{2}+r_{2}n_{2}-n_{1}}{(r_{2}+n_{1})(n_{1}+n_{2}-1)}$
._

  * _c)_

_If $S$$\neq\varPhi$ and $S\neq\left\\{2,3,\ldots,n_{1}\right\\}$, then the
normalized Laplacian spectrum of $G_{1}\underset{=}{\vee}G_{2}$ consists of: _
__
_i) $1+\frac{r_{2}\left(\delta_{i}\left(G_{2}\right)-1\right)}{n_{1}+r_{2}}$
for each $i=2,3,...,n_{2};$_
__
_ii)
$1+\frac{2\left(1+r_{1}-r_{1}\delta_{i}\left(G_{1}\right)\right)^{2}}{r_{1}\left(1-\delta_{i}\left(G_{1}\right)\right)\left(n_{1}-r_{1}-1\right)\mp\sqrt{\left(n_{1}-r_{1}-1\right)\left[r_{1}^{2}\left(1-\delta_{i}\left(G_{1}\right)\right)^{2}\left(n_{1}-r_{1}-1\right)+4\left(1+r_{1}-r_{1}\delta_{i}\left(G_{1}\right)\right)^{2}\left(n_{1}+n_{2}-1\right)\right]}}$
for each_
__
_ $\,\,\,\,\,\,\,\,i\in\left\\{2,3,\ldots,n_{1}\right\\}\setminus S$;_
__
_iii) $1^{[n(S)]}$ and $(1+\frac{1}{n_{1}+n_{2}-1})^{[n(S)]}$._
__
_iv) the three roots of the equation_

$\displaystyle\left(n_{1}^{2}+n_{1}n_{2}-n_{1}+r_{2}n_{1}+r_{2}n_{2}-r_{2}\right)x^{3}-\left(3n_{1}^{2}+3n_{1}n_{2}-3n_{1}-r_{1}n_{1}+2r_{2}n_{1}+2r_{2}n_{2}-2r_{2}-r_{1}r_{2}\right)x^{2}$
$\displaystyle+\left(2n_{1}^{2}+2n_{1}n_{2}-2n_{1}-r_{1}n_{1}+r_{2}n_{2}\right)x=0.$

###### Proof.

(a) If $S=\varPhi$, then $\delta_{i}\left(G_{1}\right)\neq 1+\frac{1}{r_{1}}$
for each $i=2,3,\ldots,n_{1}$, so $\lambda_{i}\left(G_{1}\right)\neq-1$ for
each $i=2,3,\ldots,n_{1}$. The normalized Laplacian matrix of
$G_{1}\underset{=}{\vee}G_{2}$ is:

$\mathcal{L}\left(G_{1}\underset{=}{\vee}G_{2}\right)=\left(\begin{array}[]{ccc}I_{n_{1}}-\frac{A\left(G_{1}\right)}{n_{1}+n_{2}-1}&\frac{-A\left(\textrm{$\overline{G_{1}}$}\right)}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(n_{1}-r_{1}-1\right)}}&\frac{-J_{n_{1}\times
n_{2}}}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(r_{2}+n_{1}\right)}}\\\ \\\
\frac{-A\left(\overline{G_{1}}\right)}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(n_{1}-r_{1}-1\right)}}&I_{n_{1}}&O_{n_{1}\times
n_{2}}\\\ \\\ \frac{-J_{n_{2}\times
n_{1}}}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(r_{2}+n_{1}\right)}}&O_{n_{2}\times
n_{1}}&I_{n_{2}}-\frac{A\left(G_{2}\right)}{r_{2}+n_{1}}\end{array}\right).$

Since $G_{2}$ is $r_{2}$-regular, the vector $\mathbf{1}_{n_{2}}$is an
eigenvector of $A(G_{2})$ that corresponds to
$\lambda_{1}\left(G_{2}\right)=r_{2}$. For $i=2,3,\ldots,n_{2}$ let $Z_{i}$ be
an eigenvector of $A\left(G_{2}\right)$ that corresponds to
$\lambda_{i}\left(G_{2}\right)$. Then $\mathbf{1}_{n_{2}}^{T}Z_{i}=0$ and
$\left(0_{1\times n_{1}},0_{1\times n_{1}},Z_{i}^{T}\right)^{T}$ is an
eigenvector of $\mathcal{L}\left(G_{1}\underset{=}{\vee}G_{2}\right)$
corresponding to the eigenvalue
$1-\frac{\lambda_{i}\left(G_{2}\right)}{r_{2}+n_{1}}$ . By Remark 2.8,
$1+\frac{r_{2}\left(\delta_{i}\left(G_{2}\right)-1\right)}{n_{1}+r_{2}}$ are
an eigenvalues of
$\landupintop\landupintop$$\mathcal{L}\left(G_{1}\underset{=}{\lor}G_{2}\right)$
for $i=2,...,n_{2}.$

For $i=2,...,n_{1}$, let $X_{i}$ be an eigenvector of $A(G_{1})$ corresponding
to the eigenvalue $\lambda_{i}\left(G_{1}\right)$. We now look for a non zero
real number $\alpha$ such that $\left(\begin{array}[]{ccc}X_{i}^{T}&\alpha
X_{i}^{T}&0_{1\times n_{2}}\end{array}\right)^{T}$is an eigenvector of
$\mathcal{L}(G_{1}\underset{=}{\vee}G_{2})$. Notice that $\alpha\neq 0$, since
if $\alpha=0$ then $\lambda_{i}\left(G_{1}\right)=-1$.

$\displaystyle\mathcal{L}\left(\begin{array}[]{c}X_{i}\\\ \alpha X_{i}\\\
0_{n_{1}\times 1}\end{array}\right)$
$\displaystyle=\left(\begin{array}[]{c}X_{i}-\frac{\lambda_{i}\left(G_{1}\right)}{n_{1}+n_{2}-1}X_{i}+\frac{1+\lambda_{i}\left(G_{1}\right)}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(n_{1}-r_{1}-1\right)}}\alpha
X_{i}\\\ \\\
\frac{1+\lambda_{i}\left(G_{1}\right)}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(n_{1}-r_{1}-1\right)}}X_{i}+\alpha
X_{i}\\\ \\\ 0_{n_{1}\times 1}\end{array}\right)$
$\displaystyle=\left(\begin{array}[]{c}1-\frac{\lambda_{i}\left(G_{1}\right)}{n_{1}+n_{2}-1}+\frac{1+\lambda_{i}\left(G_{1}\right)}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(n_{1}-r_{1}-1\right)}}\alpha\\\
\\\
\frac{1+\lambda_{i}\left(G_{1}\right)}{\alpha\sqrt{\left(n_{1}+n_{2}-1\right)\left(n_{1}-r_{1}-1\right)}}+1\\\
\\\ 0_{n_{1}\times 1}\end{array}\right)\left(\begin{array}[]{c}X_{i}\\\ \alpha
X_{i}\\\ 0_{n_{1}\times 1}\end{array}\right).$

Thus

$1-\frac{\lambda_{i}\left(G_{1}\right)}{n_{1}+n_{2}-1}+\frac{1+\lambda_{i}\left(G_{1}\right)}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(n_{1}-r_{1}-1\right)}}\alpha=\frac{1+\lambda_{i}\left(G_{1}\right)}{\alpha\sqrt{\left(n_{1}+n_{2}-1\right)\left(n_{1}-r_{1}-1\right)}}+1$
(6.3)

$-\frac{\lambda_{i}\left(G_{1}\right)}{n_{1}+n_{2}-1}+\frac{1+\lambda_{i}\left(G_{1}\right)}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(n_{1}-r_{1}-1\right)}}\alpha=\frac{1+\lambda_{i}\left(G_{1}\right)}{\alpha\sqrt{\left(n_{1}+n_{2}-1\right)\left(n_{1}-r_{1}-1\right)}}$

$\frac{\alpha^{2}\left(1+\lambda_{i}\left(G_{1}\right)\right)-\left(1+\lambda_{i}\left(G_{1}\right)\right)}{\alpha\sqrt{\left(n_{1}+n_{2}-1\right)\left(n_{1}-r_{1}-1\right)}}=\frac{\lambda_{i}\left(G_{1}\right)}{n_{1}+n_{2}-1}$

$\left(1+\lambda_{i}\left(G_{1}\right)\right)\sqrt{n_{1}+n_{2}-1}\alpha^{2}-\lambda_{i}\left(G_{1}\right)\sqrt{n_{1}-r_{1}-1}\alpha-\left(1+\lambda_{i}\left(G_{1}\right)\right)\sqrt{n_{1}+n_{2}-1}=0,$

so

$\alpha_{1,2}=\frac{\lambda_{i}\left(G_{1}\right)\sqrt{n_{1}-r_{1}-1}}{2\left(1+\lambda_{i}\left(G_{1}\right)\right)\sqrt{n_{1}+n_{2}-1}}\mp\sqrt{\frac{\lambda_{i}\left(G_{1}\right)^{2}\left(n_{1}-r_{1}-1\right)}{4\left(1+\lambda_{i}\left(G_{1}\right)\right)^{2}\left(n_{1}+n_{2}-1\right)}+1.}$

Substituting the values of $\alpha$ in the right side of (6.3), we get by
Remark 2.8 that

$1+\frac{2\left(1+r_{1}-r_{1}\delta_{i}\left(G_{1}\right)\right)^{2}}{r_{1}\left(1-\delta_{i}\left(G_{1}\right)\right)\left(n_{1}-r_{1}-1\right)\mp\sqrt{\left(n_{1}-r_{1}-1\right)\left[r_{1}^{2}\left(1-\delta_{i}\left(G_{1}\right)\right)^{2}\left(n_{1}-r_{1}-1\right)+4\left(1+r_{1}-r_{1}\delta_{i}\left(G_{1}\right)\right)^{2}\left(n_{1}+n_{2}-1\right)\right]}}$
are eigenvalues of $\mathcal{L}\left(G_{1}\underset{=}{\vee}G_{2}\right)$ for
each $i=2,3,...,n_{1}.$

So far we obtain $n_{2}-1+2\left(n_{1}-1\right)=2n_{1}+n_{2}-3$ eigenvalues of
$\mathcal{L}\left(G_{1}\underset{=}{\vee}G_{2}\right)$. The corresponding
eigenvectors are orthogonal to $\left(\mathbf{1}_{n_{i}}^{T},0_{1\times
n_{1}},0_{1\times n_{2}}\right)^{T},$$\left(0_{1\times
n_{1}},\mathbf{1}_{n_{i}}^{T},0_{1\times n_{2}}\right)^{T}$ and
$\left(0_{1\times n_{1}},0_{1\times n_{1}},\mathbf{1}_{n_{2}}^{T}\right)^{T}.$
To find three additional eigenvalues, we look for eigenvectors of
$\mathcal{L}\left(G_{1}\underset{=}{\vee}G_{2}\right)$ of the form
$Y=\left(\alpha\mathbf{1}_{n_{1}}^{T},\beta\mathbf{1}_{n_{1}}^{T},\gamma\mathbf{1}_{n_{2}}^{T}\right)^{T}$
for $\left(\alpha,\beta,\gamma\right)\neq\left(0,0,0\right)$. Let $x$ be an
eigenvalue of $\mathcal{L}\left(G\underset{=}{\vee}G_{2}\right)$ corresponding
to the eigenvector $Y$ . From $\mathcal{L}Y=xY$ we get,

$\alpha-\frac{\alpha
r_{1}}{n_{1}+n_{2}-1}+\frac{\left(1+r_{1}-n_{1}\right)\beta}{\sqrt{n_{1}+n_{2}-1}\sqrt{n_{1}-r_{1}-1}}-\frac{n_{2}\gamma}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(r_{2}+n_{1}\right)}}=\alpha
x$ (6.4)

$\frac{\left(1+r_{1}-n_{1}\right)\alpha}{\sqrt{n_{1}-r_{1}-1}\sqrt{n_{1}+n_{2}-1}}+\beta=\beta
x$ (6.5)

$\frac{-n_{1}\alpha}{\sqrt{r_{2}+n_{1}}\sqrt{n_{1}+n_{2}-1}}+\gamma-\frac{r_{2}\gamma}{r_{2}+n_{1}}\gamma
x$ (6.6)

Thus

$\alpha-\frac{\alpha
r_{1}}{n_{1}+n_{2}-1}+\frac{\alpha(n_{1}-1-r_{1})}{\left(n_{1}+n_{2}-1\right)\left(x-1\right)}+\frac{\alpha(n_{1}n_{2})}{\left(n_{1}+n_{2}-1\right)\left(xr_{2}+n_{1}(x-1)\right)}=\alpha
x.$

Notice that $\alpha\neq 0$, since if $\alpha=0$ then $\alpha=\beta=\gamma=0$
and also $x\neq 1$ since $x=1$ implies that $\alpha=0$.

Dividing by $\alpha$, we get

$1-\frac{r_{1}}{n_{1}+n_{2}-1}+\frac{n_{1}-1-r_{1}}{\left(n_{1}+n_{2}-1\right)\left(x-1\right)}+\frac{n_{1}n_{2}}{\left(n_{1}+n_{2}-1\right)\left(xr_{2}+n_{1}(x-1)\right)}=x.$

Then,

$\displaystyle(n_{1}^{2}+n_{1}n_{2}-n_{1})(x-1)^{3}+(r_{2}n_{1}x+r_{2}n_{2}x-r_{2}x+r_{1}n_{1})(x-1)^{2}$
$\displaystyle+(r_{1}r_{2}x-n_{1}^{2}+n_{1}+r_{1}n_{1}-n_{1}n_{2})(x-1)-r_{2}(n_{1}-1-r_{1})x=0,$

so, by simple calculation we see that x is a root of the cubic equation

$\displaystyle\left(n_{1}^{2}+n_{1}n_{2}-n_{1}+r_{2}n_{1}+r_{2}n_{2}-r_{2}\right)x^{3}-\left(3n_{1}^{2}+3n_{1}n_{2}-3n_{1}-r_{1}n_{1}+2r_{2}n_{1}+2r_{2}n_{2}-2r_{2}-r_{1}r_{2}\right)x^{2}$
$\displaystyle+\left(2n_{1}^{2}+2n_{1}n_{2}-2n_{1}-r_{1}n_{1}+r_{2}n_{2}\right)x=0$

and this completes the proof of (a).

(b) The proof of (i) is similar to the proof of (i) in (a). Now we prove (ii),
If $S=\left\\{2,3,\ldots,n_{1}\right\\}$, then
$\delta_{j}\left(G_{1}\right)=1+\frac{1}{r_{1}}$ for each
$i=2,3,\ldots,n_{1}$, so $\lambda_{i}\left(G_{1}\right)=-1$ for each
$i=2,3,\ldots,n_{1}$, i.e. $G_{1}=K_{n_{1}}$and $r_{1}=n_{1}-1$. So the
normalized Laplacian matrix of $G_{1}\underset{=}{\vee}G_{1}$ as follows:

$\mathcal{L}\left(G_{1}\underset{=}{\vee}G_{2}\right)=\left(\begin{array}[]{ccc}I_{n_{1}}-\frac{A\left(G_{1}\right)}{n_{1}+n_{2}-1}&O_{n_{1}\times
n_{1}}&\frac{-J_{n_{1}\times
n_{2}}}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(r_{2}+n_{1}\right)}}\\\ \\\
O_{n_{1}\times n_{1}}&O_{n_{1}\times n_{1}}&O_{n_{1}\times n_{2}}\\\ \\\
\frac{-J_{n_{2}\times
n_{1}}}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(r_{2}+n_{1}\right)}}&O_{n_{2}\times
n_{1}}&I_{n_{2}}-\frac{A\left(G_{2}\right)}{r_{2}+n_{1}}\end{array}\right).$

For $i=2,...,n_{1}$, let $X_{i}$ be an eigenvector of $A(G_{1})$ corresponding
to the eigenvalue $\lambda_{i}\left(G_{1}\right)=-1$. So
$\left(\begin{array}[]{ccc}X_{i}^{T}&0_{1\times n_{1}}&0_{1\times
n_{2}}\end{array}\right)^{T}$ is an eigenvector of
$\mathcal{L}(G_{1}\underset{=}{\vee}G_{2})$ corresponding to the eigenvalue
$1+\frac{1}{n_{1}+n_{2}-1}$ and $\left(\begin{array}[]{ccc}0_{1\times
n_{1}}&X_{i}^{T}&0_{1\times n_{2}}\end{array}\right)^{T}$ is an eigenvector of
$\mathcal{L}(G_{1}\underset{=}{\vee}G_{2})$ corresponding to the eigenvalue
$0$ because,

$\mathcal{L}\left(\begin{array}[]{c}X_{i}\\\ 0_{n_{1}\times 1}\\\
0_{n_{2}\times
1}\end{array}\right)=\left(\begin{array}[]{c}X_{i}-\frac{\lambda_{i}\left(G_{1}\right)X_{i}}{n_{1}+n_{2}-1}\\\
0_{n_{1}\times 1}\\\ 0_{n_{2}\times
1}\end{array}\right)=\left(1+\frac{1}{n_{1}+n_{2}-1}\right)\left(\begin{array}[]{c}X_{i}\\\
0_{n_{1}\times 1}\\\ 0_{n_{2}\times 1}\end{array}\right)$ and
$\mathcal{L}\left(\begin{array}[]{c}0_{n_{1}\times 1}\\\ X_{i}\\\
0_{n_{2}\times 1}\end{array}\right)=\left(\begin{array}[]{c}0_{n_{1}\times
1}\\\ 0_{n_{1}\times 1}\\\ 0_{n_{2}\times 1}\end{array}\right)$.

Therefore, $(1+\frac{1}{n_{1}+n_{2}-1})^{[n_{1}-1]}$ and $0^{[n_{1}-1]}$ are
eigenvalues of $\mathcal{L}(G_{1}\underset{=}{\vee}G_{2})$.

So far, we obtained $n_{2}-1+2\left(n_{1}-1\right)=2n_{1}+n_{2}-3$ eigenvalues
of $\mathcal{L}\left(G_{1}\underset{=}{\vee}G_{2}\right)$. Their eigenvectors
are orthogonal to $\left(\mathbf{1}_{n_{1}}^{T},0_{1\times n_{1}},0_{1\times
n_{2}}\right)^{T},$$\left(0_{1\times n_{1}},1_{n_{1}}^{T},0_{1\times
n_{2}}\right)^{T}$ and $\left(0_{1\times n_{1}},0_{1\times
n_{1}},1_{n_{2}}^{T}\right)^{T}.$ To find three additional eigenvalues, we
look for eigenvectors of $\mathcal{L}\left(G\underset{=}{\vee}G_{2}\right)$ of
the form
$Y=\left(\alpha\mathbf{1}_{n_{1}}^{T},\beta\mathbf{1}_{n_{1}}^{T},\gamma\mathbf{1}_{n_{2}}^{T}\right)^{T}$for
$\left(\alpha,\beta,\gamma\right)\neq\left(0,0,0\right)$. Let $x$ be an
eigenvalue of $\mathcal{L}\left(G\underset{=}{\vee}G_{2}\right)$ corresponding
to the eigenvector $Y$ . Then from $\mathcal{L}Y=xY$ we get

$\alpha-\frac{r_{1}\alpha}{n_{1}+n_{2}-1}-\frac{\gamma
n_{2}}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(r_{2}+n_{1}\right)}}=\alpha x$
(6.7)

$\beta x=0$ (6.8)

$\frac{-\alpha
n_{1}}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(r_{2}+n_{1}\right)}}+\gamma-\frac{r_{2}\gamma}{r_{2}+n_{1}}=\gamma
x$ (6.9)

If $\beta\neq 0$, then $\left(0,\beta,0\right)$ is a one of the solutions of
the three above equations, so $\left(0_{1\times
n_{1}},\beta\mathbf{1}_{n_{1}}^{T},0_{1\times n_{2}}\right)^{T}$ is an
eigenvector corresponding to the eigenvalue $0$. On the other hand if
$\beta=0$ we get

$\alpha\left(1-x-\frac{r_{1}}{n_{1}+n_{2}-1}\right)=\frac{\gamma
n_{2}}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(r_{2}+n_{1}\right)}}$ (6.10)

$\gamma\left(1-x-\frac{r_{2}}{r_{2}+n_{1}}\right)=\frac{\alpha
n_{1}}{\sqrt{\left(n_{1}+n_{2}-1\right)\left(r_{2}+n_{1}\right)}}$ (6.11)

By solving above two equations we get the equation

$\left(r_{2}+n_{1}\right)\left(n_{1}+n_{2}-1\right)x^{2}+\left(n_{1}-r_{2}n_{2}-2n_{1}n_{2}-n_{1}^{2}\right)x=0,$

whose roots are $0$ and
$\frac{n_{1}^{2}+2n_{1}n_{2}+r_{2}n_{2}-n_{1}}{(r_{2}+n_{1})(n_{1}+n_{2}-1)}$.

This completes the proof of (b).

(c) The proofs of (i), (ii) and (iv) are similar to the proofs of (i), (ii)
and (iii) of (a), respectively. Now we prove (iii), Let $S$$\neq\varPhi$ and
$S\neq\left\\{2,3,\ldots,n_{1}\right\\}$. If $i\in S$, then
$1+\frac{1}{n_{1}+n_{2}-1}$ and $1$ are eigenvalues of
$\mathcal{L}\left(G\underset{=}{\vee}G_{2}\right)$ because if $X_{i}$ is an
eigenvector corresponding to the eigenvalue $\delta_{i}(G_{1})$, then

$\mathcal{L}\left(\begin{array}[]{c}X_{i}\\\ 0_{n_{1}\times 1}\\\
0_{n_{2}\times
1}\end{array}\right)=\left(\begin{array}[]{c}X_{i}+\frac{X_{i}}{n_{1}+n_{2}-1}\\\
0_{n_{1}\times 1}\\\ 0_{n_{2}\times
1}\end{array}\right)=\left(1+\frac{1}{n_{1}+n_{2}-1}\right)\left(\begin{array}[]{c}X_{i}\\\
0_{n_{1}\times 1}\\\ 0_{n_{2}\times 1}\end{array}\right)$ and
$\mathcal{L}\left(\begin{array}[]{c}0_{n_{1}\times 1}\\\ X_{i}\\\
0_{n_{2}\times 1}\end{array}\right)=\left(\begin{array}[]{c}0_{n_{1}\times
1}\\\ X_{i}\\\ 0_{n_{2}\times 1}\end{array}\right)$.

So, $1^{[n(S)]}$ and $(1+\frac{1}{n_{1}+n_{2}-1})^{[n(S)]}$ are eigenvalues of
$\mathcal{L}\left(G\underset{=}{\vee}G_{2}\right)$ and this completes the
proof of (c). ∎

Now we can give another answer to Question 2.16 by constructing several pairs
of non regular $\left\\{A,L,Q,\mathcal{L}\right\\}$NICS graphs.

######  Corollary 6.5.

_Let $G_{1}$, $H_{1}$ be cospectral regular graphs and $G_{2}$, $H_{2}$ be non
isomorphic, regular and cospectral graphs. Then $G_{1}\underset{=}{\lor}G_{2}$
and $H_{1}\underset{=}{\lor}H_{2}$ are non regular
$\left\\{A,L,Q,\mathcal{L}\right\\}$NICS._

###### Proof.

_$G_{1}\underset{=}{\lor}G_{2}$ _and _ $H_{1}\underset{=}{\lor}H_{2}$_ are non
isomorphic since $G_{2}$ and $H_{2}$ are non isomorphic. By Theorems 6.1, 6.2,
6.3 and 6.4 , we get that $G_{1}\underset{=}{\lor}G_{2}$ and
$H_{1}\underset{=}{\lor}H_{2}$ are non regular
$\left\\{A,L,Q,\mathcal{L}\right\\}$NICS. ∎

######  Example 6.6.

Let $G_{1}=H_{1}=C_{4}$, and choose $G_{2}=G$ and $H_{2}=H$ where $G$ and $H$
are graphs in Figure 2.1, then the graphs in Figure 6.1 are
$\left\\{A,L,Q,\mathcal{L}\right\\}$NICS.

(a) $C_{4}\underset{=}{\vee}G_{2}$ (b) $C_{4}\underset{=}{\vee}H_{2}$

Figure 6.1: Non regular $\left\\{A,L,Q,\mathcal{L}\right\\}$NICS graphs.

## References

  * [1] Sasmita Barik, Ravindra B Bapat, and Sukanta Pati.  On the laplacian spectra of product graphs.  Applicable Analysis and Discrete Mathematics, pages 39–58, 2015\.
  * [2] Sasmita Barik, Sukanta Pati, and BK Sarma.  The spectrum of the corona of two graphs.  SIAM Journal on Discrete Mathematics, 21(1):47–56, 2007.
  * [3] Andries E Brouwer and Willem H Haemers.  Spectra of graphs.  Springer Science & Business Media, 2011.
  * [4] Steve Butler.  A note about cospectral graphs for the adjacency and normalized laplacian matrices.  Linear and Multilinear Algebra, 58(3):387–390, 2010.
  * [5] Domingos M Cardoso, Maria Aguieiras A de Freitas, Enide Andrade Martins, and María Robbiano.  Spectra of graphs obtained by a generalization of the join graph operation.  Discrete Mathematics, 313(5):733–741, 2013.
  * [6] Fan RK Chung and Fan Chung Graham.  Spectral graph theory.  Number 92. American Mathematical Soc., 1997.
  * [7] Shu-Yu Cui and Gui-Xian Tian.  The spectrum and the signless laplacian spectrum of coronae.  Linear algebra and its applications, 437(7):1692–1703, 2012.
  * [8] D Cvetkovič, P Rowlinson, and S Simić.  An introduction to the theory of graph spectra london mathematical society student texts.  London: Cambridge University, 2010.
  * [9] Dragoš Cvetkovic.  Spectra of graphs formed by some unary operations.  Publ. Inst. Math.(Beograd), 19(33):37–41, 1975.
  * [10] Dragoš M Cvetković.  Graphs and their spectra.  Publikacije Elektrotehničkog fakulteta. Serija Matematika i fizika, (354/356):1–50, 1971.
  * [11] A Das and P Panigrahi.  New classes of simultaneous cospectral graphs for adjacency, laplacian and normalized laplacian matrices.  Kragujevac Journal of Mathematics, 43(2):303–323, 2019.
  * [12] CD Godsil and BD McKay.  A new graph product and its spectrum.  Bulletin of the Australian Mathematical Society, 18(1):21–28, 1978\.
  * [13] Indulal Gopalapillai.  The spectrum of neighborhood corona of graphs.  Kragujevac journal of mathematics, 35(3):493–500, 2011.
  * [14] F Harary.  Graph theory. addison wesley publishing company.  Reading, Massachusetts, 1969.
  * [15] Roger A Horn and Fuzhen Zhang.  Basic properties of the schur complement.  The Schur Complement and Its Applications, pages 17–46, 2005.
  * [16] Yaoping Hou and Wai-Chee Shiu.  The spectrum of the edge corona of two graphs.  The Electronic Journal of Linear Algebra, 20:586–594, 2010.
  * [17] Gopalapillai Indulal.  Spectrum of two new joins of graphs and infinite families of integral graphs.  Kragujevac journal of mathematics, 36(38):133–139, 2012.
  * [18] Xiaogang Liu and Zuhe Zhang.  Spectra of subdivision-vertex join and subdivision-edge join of two graphs.  Bulletin of the Malaysian Mathematical Sciences Society, 42(1):15–31, 2019.
  * [19] Zhiqin Lu, Xiaoling Ma, and Minshao Zhang.  Spectra of graph operations based on splitting graph.  Journal of Applied Analysis & Computation, 13(1):133–155, 2023\.
  * [20] Cam McLeman and Erin McNicholas.  Spectra of coronae.  Linear algebra and its applications, 435(5):998–1007, 2011.
  * [21] Bojan Mohar.  Laplace eigenvalues of graphs—a survey.  Discrete mathematics, 109(1-3):171–183, 1992.
  * [22] Bogdan Nica.  A brief introduction to spectral graph theory.  arXiv preprint arXiv:1609.08072, 2016.
  * [23] R Pavithra and R Rajkumar.  Spectra of m-edge rooted product of graphs.  Indian Journal of Pure and Applied Mathematics, 52(4):1235–1255, 2021.
  * [24] R Pavithra and R Rajkumar.  Spectra of bowtie product of graphs.  Discrete Mathematics, Algorithms and Applications, 14(02):2150114, 2022.
  * [25] R Rajkumar and M Gayathri.  Spectra of (h1, h2)-merged subdivision graph of a graph.  Indagationes Mathematicae, 30(6):1061–1076, 2019.
  * [26] R Rajkumar and R Pavithra.  Spectra of m-rooted product of graphs.  Linear and Multilinear Algebra, 70(1):1–26, 2022.
  * [27] Daniel A Spielman.  Spectral graph theory and its applications.  In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 29–38. IEEE, 2007.
  * [28] Edwin R Van Dam and Willem H Haemers.  Which graphs are determined by their spectrum?  Linear Algebra and its applications, 373:241–272, 2003.
  * [29] Edwin R Van Dam and Willem H Haemers.  Developments on spectral characterizations of graphs.  Discrete Mathematics, 309(3):576–586, 2009.
  * [30] Renny P Varghese and D Susha.  On the normalized laplacian spectrum of some graphs.  Kragujevac Journal of Mathematics, 44(3):431–442, 2020.