# On the spectrum and energy of Seidel matrix
for chain graphs

Santanu Mandal<EMAIL_ADDRESS>Department of Mathematics,  Ranjit
Mehatari<EMAIL_ADDRESS><EMAIL_ADDRESS>Department of
Mathematics,  Kinkar Chandra Das<EMAIL_ADDRESS>Department of
Mathematics,

###### Abstract

We study various spectral properties of the Seidel matrix $S$ of a connected
chain graph. We prove that $-1$ is always an eigenvalue of $S$ and all other
eigenvalues of $S$ can have multiplicity at most two. We obtain the
multiplicity of the Seidel eigenvalue $-1$, minimum number of distinct
eigenvalues, eigenvalue bounds, characteristic polynomial, lower and upper
bounds of Seidel energy of a chain graph. It is also shown that the energy
bounds obtained here work better than the bounds conjectured by Haemers. We
also obtain the minimal Seidel energy for some special chain graphs of order
$n$. We also give a number of open problems.

AMS Classification:  05C50.
Keywords:  Chain graph, Seidel matrix, Quotient matrix, Characteristic
polynomial, Seidel energy.

##  1 Introduction

A chain graph can be defined in terms of induced forbidden subgraphs. Let
$C_{n}$ and $K_{n}$ denote the cycle and the complete graph on $n$ vertices,
respectively. A graph with no induced subgraph isomorphic to $C_{3},$ $C_{5}$
or $2K_{2}$ is called a chain graph. Very interestingly a chain graph can be
represented by a unique binary string (sequence). Starting from a single
vertex, one can construct a chain graph by repeated applications of following
two operations:

  1. 1.

adding an isolated vertex.

  2. 2.

adding a vertex dominating to all previously added isolated vertices only.

We represent a chain graph $G$ on $n$ vertices using a binary string
$b=\alpha_{1}\alpha_{2}\alpha_{3}\cdots\alpha_{n}$ of length $n$, where
$\alpha_{i}=0$ if the vertex $v_{i}$ is added as an isolated vertex, and
$\alpha_{i}=1$ if the vertex $v_{i}$ is dominating to all the previously added
isolated vertices. As we start from a single vertex we always take
$\alpha_{1}=0$, and since we are considering connected graphs only so
$\alpha_{n}=1$. For any $n$ vertex chain graph, without loss of generality, we
represent it by the binary string $b=0^{s_{1}}1^{t_{1}}0^{s_{2}}\ldots
0^{s_{k}}1^{t_{k}}$, where $s_{i},~{}t_{i}\geq 1$ and
$\sum\limits^{k}_{i=1}\,(s_{i}+t_{i})=n$. A chain graph is a bipartite graph,
and it is complete bipartite if and only if $k=1$.

Let $G$ be a simple, connected, finite graph with vertex set
$V=\\{v_{1},v_{2},\ldots,v_{n}\\}$. Let $A$ be the $(0,1)$-adjacency matrix
[12, 17] of $G$. Then the Seidel matrix [1, 2, 6, 9, 19, 20, 22, 23, 25] is a
square matrix of order $n$ defined by

$S=J-I-2A,$

where $J$ is all $1$ matrix and $I$ is the identity matrix. In other words, if
$s_{ij}$ is the $(i,j)$-th entry of $S$, then

$s_{ij}=\begin{cases}-1&\text{if }v_{i}\sim v_{j},\\\ 1&\text{if }v_{i}\nsim
v_{j},\ i\neq j,\\\ 0&\text{if }i=j.\end{cases}$

Obviously all eigenvalues of $S$ are real. We use $\lambda_{1}$ to denote the
largest Seidel eigenvalue of graph $G$. The Seidel energy $SE(G)$ of a graph
$G$ is defined as the sum of absolute values of the eigenvalues of Seidel
matrix $S$. For several interesting properties of $SE(G)$, we refer [1, 16,
18, 22, 23].

The spectral properties of adjacency and Laplacian matrix of chain graphs is
well studied in literature [3, 4, 5, 7, 8, 10, 13, 14]. One of the most
interesting property of chain graphs is that, among all connected bipartite
graphs of prescribed order and size, the graph with minimal least eigenvalue
(equivalently, the maximal spectral radius) is a chain graph. Around the same
time but separately in $2008,$ Bhattacharya et al. [10] and Bell et al. [7, 8]
first noticed this significant property of the adjacency matrix of a chain
graph. After that chain graphs gained lot of focus for the past few years. The
spectral properties of a chain graph have been extensively studied earlier
with respect to adjacency matrix and Laplacian matrix. Anđelić et al. [4, 5,
13] published several papers related to spectra of chain graphs with key focus
on eigenvalue location, characteristic polynomial and energy. Very recently,
Mei et al. [21] give some bounds of the energy and Laplacian energy of chain
graphs.

In this paper we consider the Seidel matrix $S$ of a connected $n$-vertex
chain graph $G$. The study on Seidel matrix of a chain graph have never been
done before. Let $b=0^{s_{1}}1^{t_{1}}0^{s_{2}}\ldots 0^{s_{k}}1^{t_{k}}$ be
the binary representation of $G$. We produce a set of $n-2k+1$ orthogonal
Seidel eigenvectors corresponding to the eigenvalue $-1$. We derive a formula
for the Seidel characteristic polynomial of a chain graph in terms of its
binary string. We see that determinant of symmetric tridiagonal matrix plays
important role for evaluating the characteristic polynomial. As a consequence
we obtain a formula for the determinant of the Seidel matrix of a chain graph.
More importantly we provide some interesting properties of Seidel energy of a
chain graph. In [18], Haemers proposed a conjecture for any $n$ vertex graph
$G$:

######  Lemma 1.1.

[18] Let $G$ be a graph with $n$ vertices. Then $SE(G)\leq n\sqrt{n-1}$ with
equality if and only if $G$ is a conference graph.

######  Lemma 1.2 (Haemers’ Conjecture).

Let $G$ be a graph with $n$ vertices. Then $SE(G)\geq 2(n-1)$ with equality if
and only if $G$ is the complete graph $K_{n}$.

Ghorbani [16] proved this conjecture partially. Very recently Akbari et al.
[1] prove this conjecture. Thus for a graph with $n$ vertices the known Seidel
energy bound is given by

$2(n-1)\leq SE(G)\leq n\sqrt{n-1}.$ (1)

Here we provide some new bounds for the Seidel energy of a chain graph. We
also observe that the bounds obtained in this paper work better than the
bounds in the Haemers’ conjecture. We provide suitable examples to justify our
results.

The contents of the paper is as follows: In Section $2$, we study few spectral
properties of Seidel matrix and its quotient matrix. In particular, we prove
that $-1$ is always an eigenvalue of $S$ and all other eigenvalues of the
Seidel matrix can have multiplicity at most two. Moreover, we give a lower
bound on the largest Seidel eigenvalue of chain graph in terms of order $n$
and $k$. In Section $3$, we obtain a formula for finding the characteristic
polynomial and determinant of $S$. Section $4$ consists of Seidel energy of
the chain graph. Here we obtain a better bound than Haemers’ bound. Finally,
we obtain the minimal Seidel energy for some special chain graphs of order $n$
in this section.

##  2 Seidel eigenvalues of chain graphs

In this section, we discuss some properties on the eigenvalues of the quotient
matrix corresponding to an equitable partition of the Seidel matrix. Using
these properties we obtain the multiplicity of the Seidel eigenvalue $-1$.
Moreover, we prove that the spectrum (distinct eigenvalues) of the Seidel
matrix of a chain graph is equal to the spectrum of that quotient matrix. In
particular, if $\lambda$ is an eigenvalue which is not an eigenvalue of that
quotient matrix, then $\lambda=-1$.

###  2.1 Quotient Matrix

Let us consider a chain graph $G$ with the binary string
$b=0^{s_{1}}1^{t_{1}}0^{s_{2}}\ldots 0^{s_{k}}1^{t_{k}}$. Then the Seidel
matrix $S$ of $G$ is a square matrix of size $n$, given by

$S=\begin{bmatrix}(J-I)_{s_{1}}&-J_{s_{1}\times t_{1}}&J_{s_{1}\times
s_{2}}&-J_{s_{1}\times t_{2}}&J_{s_{1}\times s_{3}}&-J_{s_{1}\times
t_{3}}&\ldots&-J_{s_{1}\times t_{k}}\\\\[2.84526pt] -J_{t_{1}\times
s_{1}}&(J-I)_{t_{1}}&J_{t_{1}\times s_{2}}&J_{t_{1}\times
t_{2}}&J_{t_{1}\times s_{3}}&J_{t_{1}\times t_{3}}&\ldots&J_{t_{1}\times
t_{k}}\\\\[2.84526pt] J_{s_{2}\times s_{1}}&J_{s_{2}\times
t_{1}}&(J-I)_{s_{2}}&-J_{s_{2}\times t_{2}}&J_{s_{2}\times
s_{3}}&-J_{s_{2}\times t_{3}}&\ldots&-J_{s_{2}\times t_{k}}\\\\[2.84526pt]
-J_{t_{2}\times s_{1}}&J_{t_{2}\times t_{1}}&-J_{t_{2}\times
s_{2}}&(J-I)_{t_{2}}&J_{t_{2}\times s_{3}}&J_{t_{2}\times
t_{3}}&\ldots&J_{t_{2}\times t_{k}}\\\\[2.84526pt] &&&&&&\ddots\\\\[2.84526pt]
J_{s_{k}\times s_{1}}&J_{s_{k}\times t_{1}}&J_{s_{k}\times
s_{2}}&J_{s_{k}\times t_{2}}&J_{s_{k}\times s_{3}}&J_{s_{k}\times
t_{3}}&\ldots&-J_{s_{k}\times t_{k}}\\\\[2.84526pt] -J_{t_{k}\times
s_{1}}&J_{t_{k}\times t_{1}}&-J_{t_{k}\times s_{2}}&J_{t_{k}\times
t_{2}}&-J_{t_{k}\times s_{3}}&J_{t_{k}\times
t_{3}}&\ldots&(J-I)_{t_{k}}\end{bmatrix},$

where $J_{m\times n}$ is all 1 block matrix of size $m\times n$ and the
diagonal blocks of $S$ are the square matrices of size $s_{1}\times
s_{1},~{}t_{1}\times t_{1},~{}s_{2}\times s_{2},~{}t_{2}\times
t_{2},~{}\ldots,~{}t_{k}\times t_{k}$.

We now construct an equitable partition in the following way. For the
representation $b=0^{s_{1}}1^{t_{1}}0^{s_{2}}\ldots 0^{s_{k}}1^{t_{k}}$ of
$G$, let $V_{s_{1}}$ denote the set of vertices representing first $s_{1}$
added vertices, $V_{t_{1}}$ denote the set of vertices representing next
$t_{1}$ added vertices, $V_{s_{2}}$ denote the set of vertices representing
next $s_{2}$ added vertices and finally $V_{t_{k}}$ denote the set of vertices
representing last $t_{k}$ added vertices. Now we consider the vertex partition
of $\pi=\\{C_{1},C_{2},C_{3},\ldots,C_{2k}\\}$, where $C_{i}=V_{s_{j}}=s_{j}$,
if $i=2j-1$ $(j=1,\,2,\ldots,\,k)$, and $C_{i}=V_{t_{j}}=t_{j}$, if $i=2j$
$(j=1,\,2,\ldots,\,k)$. Then $\pi$ is an equitable partition of $G$ of size
$2k$. Throughout this paper we consider this equitable partition only, and by
writing “$G$ is a chain graph of order $n$ with $|\pi|=2k$” we mean that $G$
is a chain graph graph of order $n$ with the binary string
$b=0^{s_{1}}1^{t_{1}}0^{s_{2}}\ldots 0^{s_{k}}1^{t_{k}}$. Let $Q_{S}$ be the
corresponding quotient matrix. Then $Q_{S}$ is a square matrix of size $2k$,
given by

$Q_{S}=\begin{bmatrix}(s_{1}-1)&-t_{1}&s_{2}&-t_{2}&s_{3}&-t_{3}&\ldots&-t_{k}\\\\[2.84526pt]
-s_{1}&(t_{1}-1)&s_{2}&t_{2}&s_{3}&t_{3}&\ldots&t_{k}\\\\[2.84526pt]
s_{1}&t_{1}&(s_{2}-1)&-t_{2}&s_{3}&-t_{3}&\ldots&-t_{k}\\\\[2.84526pt]
-s_{1}&t_{1}&-s_{2}&(t_{2}-1)&s_{3}&t_{3}&\ldots&t_{k}\\\\[2.84526pt]
s_{1}&t_{1}&s_{2}&t_{2}&(s_{3}-1)&-t_{3}&\ldots&-t_{k}\\\\[2.84526pt]
-s_{1}&t_{1}&-s_{2}&t_{2}&-s_{3}&(t_{3}-1)&\ldots&t_{k}\\\\[2.84526pt]
&&&&&&\ddots\\\\[2.84526pt]
s_{1}&t_{1}&s_{2}&t_{2}&s_{3}&t_{3}&\ldots&-t_{k}\\\\[2.84526pt]
-s_{1}&t_{1}&-s_{2}&t_{2}&-s_{3}&t_{3}&\ldots&(t_{k}-1)\end{bmatrix}.$

Let $D=diag[s_{1},t_{1},s_{2},t_{2},\ldots,s_{k},t_{k}]$. Then $Q_{S}$ is
similar to the symmetric matrix $D^{\frac{1}{2}}Q_{S}D^{-\frac{1}{2}}$, thus
$Q_{S}$ is diagonalizable. Let $\lambda$ be an eigenvalue of $Q_{S}$ with
corresponding eigenvector $X\in\mathbb{R}^{2k}$. Let $P$ be the characteristic
matrix (of order $n\times 2k$) for the equitable partition
$\pi=\\{C_{1},C_{2},\ldots,C_{2k}\\}$, i.e., $(i,j)$-th entry of $P$ is 1 if
$i\in C_{j}$ and 0 otherwise. Then it is easy to verify that $SP=PQ_{S}$. Then
$S(PX)=\lambda(PX)$. Which implies that every eigenvalue of $Q_{S}$ is also an
eigenvalue of $S$. It is easy to verify that trace of the quotient matrix
$Q_{S}$ is $n-2k$. Then trace of $Q_{S}^{2}$ can be obtained by the formula

$trace\ Q_{S}^{2}=(trace\ Q_{S})^{2}-2\sum_{i<j}\lambda_{i}\lambda_{j},$

where $\lambda_{i}$’s are eigenvalues of $Q_{S}$. We obtain the following:

######  Lemma 2.1.

Let $G$ be an chain graph of order $n$ with $|\pi|=2k$. Then

$trace\ Q_{S}^{2}=n^{2}-2n+2k.$

###### Proof.

Let $\lambda_{1},\lambda_{2},\ldots,\lambda_{2k}$ be eigenvalues of $Q_{S}$.
Since $\sum\limits^{k}_{i=1}\,(s_{i}+t_{i})=n$, we obtain

$\displaystyle trace\ Q_{S}^{2}$
$\displaystyle=\sum_{i=1}^{2k}\lambda_{i}^{2}$
$\displaystyle=\sum\limits^{k}_{i=1}\,\Big{[}(s_{i}-1)^{2}+s_{i}\,\Big{(}\sum\limits^{k}_{j=1,j\neq
i}\,s_{j}+\sum\limits^{k}_{j=1}\,t_{j}\Big{)}\Big{]}+\sum\limits^{k}_{i=1}\,\Big{[}(t_{i}-1)^{2}+t_{i}\,\Big{(}\sum\limits^{k}_{j=1}\,s_{j}+\sum\limits^{k}_{j=1,j\neq
i}\,t_{j}\Big{)}\Big{]}$
$\displaystyle=\sum\limits^{k}_{i=1}\,\Big{[}(s_{i}-1)^{2}+s_{i}\,(n-s_{i})\Big{]}+\sum\limits^{k}_{i=1}\,\Big{[}(t_{i}-1)^{2}+t_{i}\,(n-t_{i})\Big{]}$
$\displaystyle=\sum\limits^{k}_{i=1}\,\Big{[}s_{i}\,(n-2)+t_{i}\,(n-2)+2\Big{]}=n^{2}-2n+2k.$

∎

######  Theorem 2.2.

Let $b=0^{s_{1}}1^{t_{1}}0^{s_{2}}\ldots 0^{s_{k}}1^{t_{k}}$ be the binary
string of a chain graph $G$. Then $-1$ is a simple eigenvalue of $Q_{S}$.

###### Proof.

The eigenvector corresponding to the eigenvalue $-1$ is
$X=\left[\begin{array}[]{ccccccc}t_{k}&0&0&0&\cdots&0&s_{1}\end{array}\right]^{T}$.
Clearly the geometric multiplicity of the eigenvalue $-1$ is one. $Q_{S}$
being diagonalizable, the algebraic multiplicity of the eigenvalue $-1$ is
also one. Hence the result follows. ∎

######  Theorem 2.3.

The eigenvalues of $Q_{S}$ can have multiplicity at most two.

###### Proof.

Suppose $\lambda$ is an eigenvalue of $Q_{S}$. Let
$X=\left[\begin{array}[]{ccccc}x_{1}&x_{2}&x_{3}&\cdots&x_{2k}\end{array}\right]^{T}$
be an eigenvector corresponding to $\lambda$. We already proved that
$\lambda=-1$ is a simple eigenvalue. Now we have to prove the theorem for
$\lambda\neq-1$. Then from the relation $Q_{S}X=\lambda X$, we have $2k$
linear equations given by

$\displaystyle(s_{1}-1)x_{1}-t_{1}x_{2}+s_{2}x_{3}-t_{2}x_{4}+\ldots-
t_{k}x_{2k}$ $\displaystyle=\lambda x_{1},$ (A) $\displaystyle-
s_{1}x_{1}+(t_{1}-1)x_{2}+s_{2}x_{3}+t_{2}x_{4}+\ldots t_{k}x_{2k}$
$\displaystyle=\lambda x_{2},$ $\displaystyle
s_{1}x_{1}+t_{1}x_{2}+(s_{2}-1)x_{3}-t_{2}x_{4}+\ldots-t_{k}x_{2k}$
$\displaystyle=\lambda x_{3},$ $\displaystyle-
s_{1}x_{1}+t_{1}x_{2}-s_{2}x_{3}+(t_{2}-1)x_{4}+\ldots+t_{k}x_{2k}$
$\displaystyle=\lambda x_{4},$ $\displaystyle
s_{1}x_{1}+t_{1}x_{2}+s_{2}x_{3}+t_{2}x_{4}+\ldots-t_{k}x_{2k}$
$\displaystyle=\lambda x_{5},$ $\displaystyle-
s_{1}x_{1}+t_{1}x_{2}-s_{2}x_{3}+t_{2}x_{4}+\ldots+t_{k}x_{2k}$
$\displaystyle=\lambda x_{6},$
$\displaystyle\ldots~{}~{}\ldots~{}~{}\ldots~{}~{}\ldots~{}~{}~{}\ldots~{}~{}\ldots~{}~{}\ldots$
$\displaystyle\vdots$ $\displaystyle
s_{1}x_{1}+t_{1}x_{2}+s_{2}x_{3}+t_{2}x_{4}+\ldots-t_{k}x_{2k}$
$\displaystyle=\lambda x_{2k-1},$ $\displaystyle-
s_{1}x_{1}+t_{1}x_{2}-s_{2}x_{3}+t_{2}x_{4}+\ldots+(t_{k}-1)x_{2k}$
$\displaystyle=\lambda x_{2k}.$

Now for odd $j\geq 3$, subtracting $j$-th equation from first equation, we
get,

$x_{j}=x_{1}+\frac{2t_{1}}{1+\lambda}x_{2}+\frac{2t_{2}}{1+\lambda}x_{4}+\cdots+\frac{2t_{\frac{j-1}{2}}}{1+\lambda}x_{j-1},$
(2)

and for even $i\geq 4$, subtracting $j$-th equation from first equation, we
get

$x_{i}=x_{2}-\frac{2s_{2}}{1+\lambda}x_{3}-\frac{2s_{3}}{1+\lambda}x_{5}-\cdots-\frac{2s_{\frac{i}{2}}}{1+\lambda}x_{i-1}.$
(3)

Putting $j=3$ in (2), we get

$x_{3}=x_{1}+\frac{2t_{1}}{1+\lambda}x_{2}=a_{3}x_{1}+b_{3}x_{2},\text{(say)}.$

Putting $i=4$ in (3) and using the expression of $x_{3}$, we get

$x_{4}=x_{2}-\frac{2s_{2}}{1+\lambda}x_{3}=x_{2}-\frac{2s_{2}}{1+\lambda}(a_{3}x_{1}+b_{3}x_{2})=a_{4}x_{1}+b_{4}x_{2},\text{(say)}.$

Putting $j=5$ in (2) and using the expression of $x_{4}$, we get

$x_{5}=x_{1}+\frac{2t_{1}}{1+\lambda}x_{2}+\frac{2t_{2}}{1+\lambda}x_{4}=a_{5}x_{1}+b_{5}x_{2},(say).$

Putting $i=6$ in (3) and using the expressions of $x_{3}$ and $x_{5}$, we get

$x_{6}=x_{2}-\frac{2s_{2}}{1+\lambda}x_{3}-\frac{2s_{3}}{1+\lambda}x_{5}=a_{6}x_{1}+b_{6}x_{2},(say).$

Proceeding in this way, iteratively, we can obtain real numbers
$a_{3},a_{4},\ldots a_{2k}$ and $b_{3},b_{4},\ldots b_{2k}$ such that

$x_{i}=a_{i}x_{1}+b_{i}x_{2}~{}~{}~{}\mbox{ for }3\leq i\leq 2k.$ (4)

Assume to the contrary that the multiplicity of the eigenvalue
$\lambda\,(\neq-1)$ of $Q_{S}$ is at least three. Then we can assume that
$Y=\left[\begin{array}[]{cccccc}0&0&y_{3}&y_{4}&\cdots&y_{2k}\end{array}\right]^{T}$
is an eigenvector corresponding to $\lambda$ of $Q_{S}$. By (4), we obtain
$y_{3}=y_{4}=\cdots=y_{2k}=0$, that is, $Y={\bf 0}$, a contradiction as $Y$ is
an eigenvector. This completes the proof of the theorem. ∎

Since $-1$ is a simple eigenvalue of $Q_{S}$, therefore among $(2k-1)$
remaining eigenvalues, the minimum number of distinct eigenvalues is
$(\frac{2k-2}{2}+1)$. As a consequence of this fact we obtain here a
straightforward result which counts the minimum number of distinct eigenvalues
of $Q_{S}$.

######  Theorem 2.4.

$Q_{S}$ has at least $(k+1)$ distinct eigenvalues.

The quotient matrix $Q_{S}$ has $2k$ eigenvalues and with at least $k+1$
distinct eigenvalues. We did not find any chain graph for which the number of
distinct positive and the distinct negative eigenvalues of $S$ are unequal.

######  Problem 2.5.

Is there exists a chain graph for which the number of positive eigenvalues of
$Q_{S}$ is not equal to the number of negative eigenvalues?

###  2.2 Eigenvalue bounds and multiplicity of the eigenvalue $-1$

Let us consider a chain graph $G$ with the binary string
$0^{s_{1}}1^{t_{1}}0^{s_{2}}\ldots 0^{s_{k}}1^{t_{k}}$. Let $n_{-1}(S)$ denote
the multiplicity of the eigenvalue $-1$ of the matrix $S$. We now derive a
formula for $n_{-1}(S)$. For this first we construct eigenvectors
corresponding to $-1$ which does not belong to spectrum of $Q_{S}$.

For $i>1$, we define a set $\\{E_{j}^{i}\\}$ of $i-1$ orthogonal row-vectors
in $\mathbb{R}^{i}$ by

$E_{j}^{i}=\textbf{\emph{e}}_{1}(i)+\textbf{\emph{e}}_{2}(i)+\cdots+\textbf{\emph{e}}_{j}(i)-j\textbf{\emph{e}}_{j+1}(i)\
\forall 1\leq j\leq i-1,$

where the row vector $\textbf{\emph{e}}_{j}(i)$ represents the $j$-th standard
basis element of $\mathbb{R}^{i}$.

Now for each $s_{i}\geq 2$, we define

$X_{s_{i}}(j)=[O_{s_{1}}\ O_{t_{1}}\ \cdots\ O_{t_{i-1}}\ E_{j}^{s_{i}}\
O_{t_{i}}\ \cdots\ O_{t_{k}}]^{T},\ \ 1\leq j\leq s_{i}-1,\,1\leq i\leq k,$

where row-vector $O_{r}$ denote the zero vector in $\mathbb{R}^{r}$. Then the
set $\\{X_{s_{i}}(1),X_{s_{i}}(2),\ldots,X_{s_{i}}(s_{i}-1)\\}$ is orthogonal
and $SX_{s_{i}}(j)=-X_{s_{i}}(j)$ for all $1\leq j\leq s_{i}-1$. There for
each $s_{i}>1$ $(1\leq i\leq k)$, the constructed set contains $s_{i}-1$
orthogonal eigenvectors corresponding to $-1$.

Again for each $t_{i}\geq 2$, define

$Y_{t_{i}}(j)=[O_{s_{1}}\ O_{t_{1}}\ \cdots\ O_{s_{i}}\ E_{j}^{t_{i}}\
O_{s_{i+1}}\ \cdots\ O_{t_{k}}]^{T},\ \ 1\leq j\leq t_{i}-1,\,1\leq i\leq k.$

As above, for each $t_{i}>1$ $(1\leq i\leq k)$, the set
$\\{Y_{t_{i}}(1),Y_{t_{i}}(2),\ldots,Y_{t_{i}}(t_{i}-1)\\}$ contains $t_{i}-1$
orthogonal eigenvectors corresponding to $-1$.

Each of $X_{s_{i}}(j)$’s and $Y_{t_{i}}(j)$’s has column sum zero in each of
the vertex partition. Now let $\lambda$ be an eigenvalue of $Q_{S}$ with
eigenvector
$X=\left[\begin{array}[]{ccccc}x_{1}&x_{2}&x_{3}&\cdots&x_{2k}\end{array}\right]^{T}\in\mathbb{R}^{2k}$.
Then $PX$ is an eigenvector corresponding to the eigenvalue $\lambda$ for the
Seidel matrix S and the $j$-th entry of the eigenvector is $x_{i}$ for every
$j\in C_{i}$, i.e., the eigenvector $PX$ corresponding to the eigenvalue
$\lambda$ is constant in each vertex set in $\pi$. Therefore $PX$ is
orthogonal to each of these $X_{s_{i}}(j)$’s and $Y_{t_{i}}(j)$’s. Using this
fact we now compute the multiplicity of the eigenvalue $-1$.

######  Theorem 2.6.

Let $G$ be a chain graph of order $n$ with $|\pi|=2k$. Then

$n_{-1}(S)=n-2k+1.$

###### Proof.

We already observed that, if $s_{i}\geq 2$ $(1\leq i\leq k)$, then the set
$\\{X_{s_{i}}(1),X_{s_{i}}(2),\ldots,X_{s_{i}}(s_{i}-1)\\}$ contains $s_{i}-1$
orthogonal eigenvectors corresponding to $-1$. Now for $s_{\ell},\ s_{m}\geq
2$, the vectors $X_{s_{\ell}}(j)$ and $X_{s_{m}}(k)$ are orthogonal for all
$1\leq j<s_{\ell}$ and $1\leq k<s_{m}$. Therefore the set

$\Big{\\{}X_{s_{i}}(j)\,|s_{i}>1,\,1\leq j\leq s_{i}-1,\,1\leq i\leq
k\Big{\\}}$

is a set of $\sum s_{i}-k$ orthogonal eigenvectors corresponding to $-1$.
By a similar argument, the set

$\Big{\\{}Y_{t_{i}}(j)\,|t_{i}>1,\,1\leq j\leq t_{i}-1,\,1\leq i\leq
k\Big{\\}}$

provides $\sum t_{i}-k$ orthogonal eigenvectors corresponding to $-1$. Again
any eigenvector of the form $X_{s_{i}}(\ell)$ is orthogonal to any eigenvector
of the form $Y_{t_{j}}(m)$. Since $Q_{S}$ has a simple eigenvalue $-1$,
therefore the multiplicity of the Seidel eigenvalue $-1$ is exactly $\sum
s_{i}-k+\sum t_{i}-k+1$. That means,

$n_{-1}(S)=n-2k+1.$

This completes the proof of the theorem. ∎

From Theorem 2.2 and Theorem 2.6, it is clear that if $\lambda\neq-1$ is an
eigenvalue of $S$ then it also an eigenvalue of $Q_{S}$. Since the eigenvalues
of $Q_{S}$ can have multiplicity at most two. Thus by Theorem 2.4 and Theorem
2.6 we have the following corollary.

######  Corollary 2.7.

Let $G$ be a chain graph with $|\pi|=2k$. If $m(G)$ denotes the number of
distinct Seidel eigenvalues, then $m(G)$ satisfies the following:

$k+1\leq m(G)\leq 2k.$

######  Remark 2.8.

Here both the bounds are tight. Let $G_{1}$ and $G_{2}$ be chain graphs with
binary strings $b_{1}=0^{1}1^{2}0^{2}1^{2}0^{2}1^{1}$ and
$b_{2}=0^{1}1^{1}0^{1}1^{1}0^{1}1^{1}$, respectively. Then $G_{1}$ has 4
distinct Seidel eigenvalues (i.e., $m(G_{1})=k+1$), on the other hand $G_{2}$
has $6$ distinct Seidel eigenvalues (i.e., $m(G_{2})=2k$).

We have checked several examples and we found that for any chain graph $G$,
either $m(G)=k+1$ or $m(G)=2k$.

######  Problem 2.9.

Is there exist a chain graph for which $k+1<m(G)<2k$?

We now give some upper and lower bounds on the largest Seidel eigenvalue of a
chain graph. Let
$X=\left[\begin{array}[]{ccccc}x_{1}&x_{2}&x_{3}&\cdots&x_{2k}\end{array}\right]^{T}$
be an eigenvector corresponding to the largest Seidel eigenvalue
$\lambda_{1}(G)$ of $Q_{S}$. Then $Q_{S}X=\lambda_{1}(G)X$, that is,

$\lambda_{1}(G)x_{i}=\sum\limits^{2k}_{j=1}\,(Q_{S})_{ij}x_{j},~{}~{}i=1,\,2,\ldots,\,2k.$

From the above, we obtain
$\lambda_{1}(G)\leq\sum\limits^{2k}_{j=1}\,|(Q_{S})_{ij}|=\sum\limits^{k}_{i=1}\,s_{i}+\sum\limits^{k}_{i=1}\,t_{i}-1=n-1$.
Moreover, one can easily see that the equality holds if and only if $k=1$,
that is, if and only if $G$ is isomorphic to a complete bipartite graph. We
now give a lower bound for the largest eigenvalue $\lambda_{1}(G)$ using the
Rayleigh quotient.

######  Theorem 2.10.

Let $G$ be a chain graph of order $n$ with $|\pi|=2k$. Then

$\lambda_{1}(G)\geq\frac{n}{2}+1-\frac{2k}{n}.$

###### Proof.

For any symmetric matrix $B$, we have

$\lambda_{1}(B)=\max_{X\neq 0}\frac{X^{T}BX}{X^{T}X}.$

The matrix $Q_{S}$ is similar to the symmetric matrix $Q_{S}^{{}^{\prime}}$
given by

$Q_{S}^{{}^{\prime}}=\left[\begin{array}[]{ccccc|ccccc}s_{1}-1&\sqrt{s_{1}s_{2}}&\sqrt{s_{1}s_{3}}&\cdots&\sqrt{s_{1}s_{k}}&-\sqrt{s_{1}t_{1}}&-\sqrt{s_{1}t_{2}}&-\sqrt{s_{1}t_{3}}&\cdots&-\sqrt{s_{1}t_{k}}\\\\[2.84526pt]
\sqrt{s_{2}s_{1}}&s_{2}-1&\sqrt{s_{2}s_{3}}&\cdots&\sqrt{s_{2}s_{k}}&\sqrt{s_{2}t_{1}}&-\sqrt{s_{2}t_{2}}&-\sqrt{s_{2}t_{3}}&\cdots&-\sqrt{s_{2}t_{k}}\\\\[2.84526pt]
\sqrt{s_{3}s_{1}}&\sqrt{s_{3}s_{2}}&s_{3}-1&\cdots&\sqrt{s_{3}s_{k}}&\sqrt{s_{3}t_{1}}&\sqrt{s_{3}t_{2}}&-\sqrt{s_{1}t_{3}}&\cdots&-\sqrt{s_{1}t_{k}}\\\\[2.84526pt]
\cdots&\cdots&\cdots&\ddots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\\\[2.84526pt]
\sqrt{s_{k}s_{1}}&\sqrt{s_{k}s_{2}}&\sqrt{s_{k}s_{2}}&\cdots&s_{k}-1&\sqrt{s_{k}t_{1}}&\sqrt{s_{k}t_{2}}&\sqrt{s_{k}t_{3}}&\cdots&-\sqrt{s_{k}t_{k}}\\\\[2.84526pt]
\hline\cr-\sqrt{s_{1}t_{1}}&\sqrt{s_{2}t_{1}}&\sqrt{s_{3}t_{1}}&\cdots&\sqrt{s_{k}t_{1}}&t_{1}-1&\sqrt{t_{1}t_{2}}&\sqrt{t_{1}t_{3}}&\cdots&\sqrt{t_{1}t_{k}}\\\\[2.84526pt]
-\sqrt{s_{1}t_{2}}&-\sqrt{s_{2}t_{2}}&\sqrt{s_{3}t_{2}}&\cdots&\sqrt{s_{k}t_{2}}&\sqrt{t_{1}t_{2}}&t_{2}-1&\sqrt{t_{2}t_{3}}&\cdots&\sqrt{t_{2}t_{k}}\\\\[2.84526pt]
-\sqrt{s_{1}t_{3}}&-\sqrt{s_{2}t_{3}}&-\sqrt{s_{3}t_{3}}&\cdots&\sqrt{s_{k}t_{3}}&\sqrt{t_{1}t_{3}}&\sqrt{t_{2}t_{3}}&t_{3}-1&\cdots&\sqrt{t_{3}t_{k}}\\\\[2.84526pt]
\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\ddots&\cdots\\\
-\sqrt{s_{1}t_{k}}&-\sqrt{s_{2}t_{k}}&-\sqrt{s_{3}t_{k}}&\cdots&-\sqrt{s_{k}t_{k}}&\sqrt{t_{1}t_{k}}&\sqrt{t_{2}t_{k}}&\sqrt{t_{3}t_{k}}&\cdots&t_{k}-1\\\
\end{array}\right].$

Let $X=[{\sqrt{s_{1}}}\ {\sqrt{s_{2}}}\ {\sqrt{s_{3}}}\ \cdots\
{\sqrt{s_{k}}}\ {-\sqrt{t_{1}}}\ {-\sqrt{t_{2}}}\ -\sqrt{t_{3}}\ \cdots\
-{\sqrt{t_{k}}}]^{T}$. Here $X^{T}X=n$ and

$\displaystyle X^{T}Q_{S}^{{}^{\prime}}X$
$\displaystyle=\sum_{i=1}^{k}s_{i}^{2}+2\sum_{\begin{subarray}{c}1\leq i<j\leq
k\end{subarray}}s_{i}s_{j}-\sum_{i=1}^{k}s_{i}+\sum_{i=1}^{k}t_{i}^{2}+2\sum_{\begin{subarray}{c}1\leq
i<j\leq
k\end{subarray}}\,t_{i}t_{j}-\sum_{i=1}^{k}t_{i}+2\sum_{i=1}^{k}s_{i}t_{i}$
$\displaystyle=\Big{(}\sum_{i=1}^{k}\,s_{i}\Big{)}^{2}+\Big{(}\sum_{i=1}^{k}\,t_{i}\Big{)}^{2}-\sum_{i=1}^{k}(s_{i}+t_{i})+2\sum_{i=1}^{k}s_{i}t_{i}.$
(5)

It is well known that $a^{2}+b^{2}\geq\dfrac{(a+b)^{2}}{2}$ for all $a,\,b\geq
0$. Thus we have

$\Big{(}\sum_{i=1}^{k}s_{i}\Big{)}^{2}+\Big{(}\sum_{i=1}^{k}t_{i}\Big{)}^{2}\geq\frac{1}{2}\,\Big{(}\sum_{i=1}^{k}\,s_{i}+\sum_{i=1}^{k}\,t_{i}\Big{)}^{2}=\frac{1}{2}\,n^{2}.$

Now since the chain graph has $n$ vertices and ${s_{i}}\geq 1$ and
${t_{i}}\geq 1$, we obtain

$\displaystyle 2\sum_{i=1}^{k}\,s_{i}t_{i}-\sum_{i=1}^{k}\,(s_{i}+t_{i})$
$\displaystyle=\sum_{i=1}^{k}\,\Big{[}s_{i}\,(t_{i}-1)+t_{i}\,(s_{i}-1)\Big{]}$
$\displaystyle\geq\sum_{i=1}^{k}\,(s_{i}+t_{i}-2)=n-2k.$

Using the above results, from (5), we obtain

$X^{T}Q_{S}^{{}^{\prime}}X\geq\frac{n^{2}}{2}+n-2k.$

Which gives,

$\lambda_{1}(G)=\lambda_{1}(Q_{S})=\lambda_{1}(Q^{{}^{\prime}}_{s})\geq\frac{X^{T}Q_{S}^{{}^{\prime}}X}{X^{T}X}\geq\frac{n}{2}+1-\frac{2k}{n}.$

This completes the proof of the theorem. ∎

##  3 Characteristic polynomial of chain graphs

In this section, we obtain a formula for finding the characteristic polynomial
of the Seidel matrix $S$ of a connected chain graph using its binary
representation. First we convert the quotient matrix $Q_{J-2A}$ into a sparse
matrix by using row and column operations. The characteristic polynomials of
$Q_{S}$ and $Q_{J-2A}$ satisfy the following relation:

$\psi_{Q_{S}}(x)=\det(Q_{S}-xI)=\det\Big{(}Q_{J-2A}-(x+1)I\Big{)}=\psi_{Q_{J-2A}}(x+1)$
(6)

where $\det B$ stands for determinant of a square matrix $B$.

######  Theorem 3.1.

The characteristic polynomial $\psi_{S}(x)$ of the chain graph $G$ with binary
string $b=0^{s_{1}}1^{t_{1}}0^{s_{2}}\ldots 0^{s_{k}}1^{t_{k}}$, $k\geq 2$, is
given by the following formula,

$\psi_{S}(x)=\frac{(x+1)}{2}^{n-2k+1}\Big{[}2(x+1)^{2k-1}+(-1)^{k-1}(x+1)^{2}\det
U_{x+1}+(-1)^{k}\det V_{x+1}\Big{]}$ (7)

where $U_{x+1}$ is a tridiagonal matrix of order $2k-3$ given by

$U_{x+1}=\begin{bmatrix}2s_{2}&x+1&0&0&0&\ldots&0&0\\\\[2.84526pt]
x+1&2t_{2}&x+1&0&0&\ldots&0&0\\\\[2.84526pt]
0&x+1&2s_{3}&x+1&0&\ldots&0&0\\\\[2.84526pt]
0&0&x+1&2t_{3}&x+1&\ldots&0&0\\\\[2.84526pt]
0&0&0&x+1&2s_{4}&\ldots&0&0\\\\[2.84526pt] &&&&&\ddots\\\\[2.84526pt]
0&0&0&0&0&\ldots&2t_{k-1}&x+1\\\\[2.84526pt]
0&0&0&0&0&\ldots&x+1&2s_{k}\end{bmatrix}$

and $V_{x+1}$ is another tridiagonal matrix of order $2k-1$ given by

$V_{x+1}=\begin{bmatrix}2t_{1}&x+1&0&0&0&\ldots&0&0\\\\[2.84526pt]
x+1&2s_{2}&x+1&0&0&\ldots&0&0\\\\[2.84526pt]
0&x+1&2t_{2}&x+1&0&\ldots&0&0\\\\[2.84526pt]
0&0&x+1&2s_{3}&x+1&\ldots&0&0\\\\[2.84526pt]
0&0&0&x+1&2t_{3}&\ldots&0&0\\\\[2.84526pt] &&&&&\ddots\\\\[2.84526pt]
0&0&0&0&0&\ldots&2s_{k}&x+1\\\\[2.84526pt]
0&0&0&0&0&\ldots&x+1&2(s_{1}+t_{k})\end{bmatrix}.$

###### Proof.

We have $\psi_{Q_{S}}(x)=\psi_{Q_{J-2A}}(x+1)$. We apply some elementary row
and column operations on the quotient matrix $Q_{J-2A}$ given by

$Q_{J-2A}=\begin{bmatrix}s_{1}&-t_{1}&s_{2}&-t_{2}&s_{3}&-t_{3}&\ldots&s_{k}&-t_{k}\\\\[2.84526pt]
-s_{1}&t_{1}&s_{2}&t_{2}&s_{3}&t_{3}&\ldots&s_{k}&t_{k}\\\\[2.84526pt]
s_{1}&t_{1}&s_{2}&-t_{2}&s_{3}&-t_{3}&\ldots&s_{k}&-t_{k}\\\\[2.84526pt]
-s_{1}&t_{1}&-s_{2}&t_{2}&s_{3}&t_{3}&\ldots&s_{k}&t_{k}\\\\[2.84526pt]
s_{1}&t_{1}&s_{2}&t_{2}&s_{3}&-t_{3}&\ldots&s_{k}&-t_{k}\\\\[2.84526pt]
-s_{1}&t_{1}&-s_{2}&t_{2}&-s_{3}&t_{3}&\ldots&s_{k}&t_{k}\\\\[2.84526pt]
&&&&&&\ddots\\\\[2.84526pt]
s_{1}&t_{1}&s_{2}&t_{2}&s_{3}&t_{3}&\ldots&s_{k}&-t_{k}\\\\[2.84526pt]
-s_{1}&t_{1}&-s_{2}&t_{2}&-s_{3}&t_{3}&\ldots&-s_{k}&t_{k}\end{bmatrix}.$

The characteristic polynomial of $Q_{J-2A}$ is given by

$\displaystyle\psi_{Q_{J-2A}}(x)$ $\displaystyle=$
$\displaystyle\det(Q_{J-2A}-xI)$ $\displaystyle=$
$\displaystyle\begin{vmatrix}s_{1}-x&-t_{1}&s_{2}&-t_{2}&s_{3}&-t_{3}&\ldots&s_{k}&-t_{k}\\\\[2.84526pt]
-s_{1}&t_{1}-x&s_{2}&t_{2}&s_{3}&t_{3}&\ldots&s_{k}&t_{k}\\\\[2.84526pt]
s_{1}&t_{1}&s_{2}-x&-t_{2}&s_{3}&-t_{3}&\ldots&s_{k}&-t_{k}\\\\[2.84526pt]
-s_{1}&t_{1}&-s_{2}&t_{2}-x&s_{3}&t_{3}&\ldots&s_{k}&t_{k}\\\\[2.84526pt]
s_{1}&t_{1}&s_{2}&t_{2}&s_{3}-x&-t_{3}&\ldots&s_{k}&-t_{k}\\\\[2.84526pt]
-s_{1}&t_{1}&-s_{2}&t_{2}&-s_{3}&t_{3}-x&\ldots&s_{k}&t_{k}\\\\[2.84526pt]
&&&&&&\ddots\\\\[2.84526pt]
s_{1}&t_{1}&s_{2}&t_{2}&s_{3}&t_{3}&\ldots&s_{k}-x&-t_{k}\\\\[2.84526pt]
-s_{1}&t_{1}&-s_{2}&t_{2}&-s_{3}&t_{3}&\ldots&-s_{k}&t_{k}-x\end{vmatrix}$

Applying the following operations respectively,

$R_{i}^{{}^{\prime}}\leftarrow R_{i}-R_{i-2}$, for $i=even\geq 4$;
$R_{j}^{{}^{\prime}}\leftarrow R_{j}-R_{j-2}$, for $j=odd\geq 3$;
$R_{1}\leftarrow R_{1}+R_{2}$. Then

$\psi_{Q_{J-2A}}(x)=\begin{vmatrix}-x&-x&2s_{2}&0&2s_{3}&0&\ldots&2s_{k}&0\\\\[2.84526pt]
-s_{1}&t_{1}-x&s_{2}&t_{2}&s_{3}&t_{3}&\ldots&s_{k}&t_{k}\\\\[2.84526pt]
x&2t_{1}&-x&0&0&0&\ldots&0&0\\\\[2.84526pt]
0&x&-2s_{2}&-x&0&0&\ldots&0&0\\\\[2.84526pt]
0&0&x&2t_{2}&-x&0&\ldots&0&0\\\\[2.84526pt]
0&0&0&x&-2s_{3}&-x&\ldots&0&0\\\\[2.84526pt] &&&&&&\ddots\\\\[2.84526pt]
0&0&0&0&0&0&\ldots&-x&0\\\\[2.84526pt]
0&0&0&0&0&0&\ldots&-2s_{k}&-x\end{vmatrix}.$

Again applying the following operations respectively,

$R_{1}^{{}^{\prime}}\leftarrow R_{1}+\sum R_{i}$, for $i=even\geq 4$;
$R_{2}^{{}^{\prime}}\leftarrow R_{2}-\frac{1}{2}\\{\sum R_{j}-\sum R_{p}\\}$,
for $j=odd\geq 3$, and $p=even\geq 4$, we obtain

$\psi_{Q_{J-2A}}(x)=\begin{vmatrix}-x&0&0&0&0&0&\ldots&0&-x\\\\[2.84526pt]
-(s_{1}+\frac{x}{2})&-\frac{x}{2}&0&0&0&0&\ldots&\frac{x}{2}&(t_{k}-\frac{x}{2})\\\\[2.84526pt]
x&2t_{1}&-x&0&0&0&\ldots&0&0\\\\[2.84526pt]
0&x&-2s_{2}&-x&0&0&\ldots&0&0\\\\[2.84526pt]
0&0&x&2t_{2}&-x&0&\ldots&0&0\\\\[2.84526pt]
0&0&0&x&-2s_{3}&-x&\ldots&0&0\\\\[2.84526pt] &&&&&&\ddots\\\\[2.84526pt]
0&0&0&0&0&0&\ldots&-x&0\\\\[2.84526pt]
0&0&0&0&0&0&\ldots&-2s_{k}&-x\end{vmatrix}.$

Performing $R_{2}^{{}^{\prime}}\leftarrow 2R_{2}$ and
$C_{2k}^{{}^{\prime}}\leftarrow C_{2k}-C_{1}$ respectively,

$\displaystyle\psi_{Q_{J-2A}}(x)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\begin{vmatrix}-x&0&0&0&0&0&\ldots&0&0\\\
-(2s_{1}+x)&-x&0&0&0&0&\ldots&x&2(s_{1}+t_{k})\\\\[2.84526pt]
x&2t_{1}&-x&0&0&0&\ldots&0&-x\\\\[2.84526pt]
0&x&-2s_{2}&-x&0&0&\ldots&0&0\\\\[2.84526pt]
0&0&x&2t_{2}&-x&0&\ldots&0&0\\\\[2.84526pt]
0&0&0&x&-2s_{3}&-x&\ldots&0&0\\\\[2.84526pt] &&&&&&\ddots\\\\[2.84526pt]
0&0&0&0&0&0&\ldots&-x&0\\\\[2.84526pt]
0&0&0&0&0&0&\ldots&-2s_{k}&-x\end{vmatrix}$ $\displaystyle=$
$\displaystyle-\frac{x}{2}\,\begin{vmatrix}-x&0&0&0&0&\ldots&x&2(s_{1}+t_{k})\\\\[2.84526pt]
2t_{1}&-x&0&0&0&\ldots&0&-x\\\\[2.84526pt]
x&-2s_{2}&-x&0&0&\ldots&0&0\\\\[2.84526pt]
0&x&2t_{2}&-x&0&\ldots&0&0\\\\[2.84526pt]
0&0&x&-2s_{3}&-x&\ldots&0&0\\\\[2.84526pt] &&&&&\ddots\\\\[2.84526pt]
0&0&0&0&0&\ldots&-x&0\\\\[2.84526pt] 0&0&0&0&0&\ldots&-2s_{k}&-x\end{vmatrix}$

After taking permutations on rows,

$\displaystyle\psi_{Q_{J-2A}}(x)$ $\displaystyle=$
$\displaystyle-\frac{x}{2}(-1)^{2k-2}\begin{vmatrix}2t_{1}&-x&0&0&0&\ldots&0&-x\\\\[2.84526pt]
x&-2s_{2}&-x&0&0&\ldots&0&0\\\\[2.84526pt]
0&x&2t_{2}&-x&0&\ldots&0&0\\\\[2.84526pt]
0&0&x&-2s_{3}&-x&\ldots&0&0\\\\[2.84526pt]
0&0&0&x&2t_{3}&\ldots&0&0\\\\[2.84526pt] &&&&&\ddots\\\\[2.84526pt]
0&0&0&0&0&\ldots&-2s_{k}&-x\\\\[2.84526pt]
-x&0&0&0&0&\ldots&x&2(s_{1}+t_{k})\end{vmatrix}$ $\displaystyle=$
$\displaystyle-\frac{x}{2}\begin{vmatrix}2t_{1}&-x&0&0&0&\ldots&0&-x\\\\[2.84526pt]
x&-2s_{2}&-x&0&0&\ldots&0&0\\\\[2.84526pt]
0&x&2t_{2}&-x&0&\ldots&0&0\\\\[2.84526pt]
0&0&x&-2s_{3}&-x&\ldots&0&0\\\\[2.84526pt]
0&0&0&x&2t_{3}&\ldots&0&0\\\\[2.84526pt] &&&&&\ddots\\\\[2.84526pt]
0&0&0&0&0&\ldots&-2s_{k}&-x\\\\[2.84526pt]
-x&0&0&0&0&\ldots&x&2(s_{1}+t_{k})\end{vmatrix}.$

Expanding we obtain

$\psi_{Q_{J-2A}}(x)=-\frac{x}{2}\,\Big{(}\det M_{1}-x\det M_{2}\Big{)},$ (8)

where $M_{1}$ is a square matrix of order $2k-1$ given by

$M_{1}=\begin{bmatrix}2t_{1}&-x&0&0&0&\ldots&0&0\\\\[2.84526pt]
x&-2s_{2}&-x&0&0&\ldots&0&0\\\\[2.84526pt]
0&x&2t_{2}&-x&0&\ldots&0&0\\\\[2.84526pt]
0&0&x&-2s_{3}&-x&\ldots&0&0\\\\[2.84526pt]
0&0&0&x&2t_{3}&\ldots&0&0\\\\[2.84526pt] &&&&&\ddots\\\\[2.84526pt]
0&0&0&0&0&\ldots&-2s_{k}&-x\\\\[2.84526pt]
-x&0&0&0&0&\ldots&x&2(s_{1}+t_{k})\end{bmatrix},$

and $M_{2}$ is another square matrix of order $2k-2$ given by

$M_{2}=\begin{bmatrix}x&-2s_{2}&-x&0&0&\ldots&0&0\\\\[2.84526pt]
0&x&2t_{2}&-x&0&\ldots&0&0\\\\[2.84526pt]
0&0&x&-2s_{3}&-x&\ldots&0&0\\\\[2.84526pt]
0&0&0&x&2t_{3}&\ldots&0&0\\\\[2.84526pt] 0&0&0&0&x&\ldots&0&0\\\\[2.84526pt]
&&&&&\ddots\\\\[2.84526pt] 0&0&0&0&0&\ldots&x&-2s_{k}\\\\[2.84526pt]
-x&0&0&0&0&\ldots&0&x\end{bmatrix}.$

Clearly,

$\det M_{1}=(-1)^{k}\det V_{x}-x^{2k-1}$

and

$\det M_{2}=x^{2k-2}+(-1)^{k-1}\,x\,\det U_{x}.$

From equation (8), we obtain

$\psi_{Q_{J-2A}}(x)=\frac{x}{2}\Big{[}2x^{2k-1}+(-1)^{k-1}x^{2}\det
U_{x}+(-1)^{k}\det V_{x}\Big{]}.$ (9)

Now by Corollary 2.1, any eigenvalue of $S$ which is not an eigenvalue of
$Q_{S}$ must be equal to $-1$. Therefore by (6), we obtain,

$\psi_{S}(x)=\frac{(x+1)}{2}^{n-2k+1}\Big{[}2(x+1)^{2k-1}+(-1)^{k-1}(x+1)^{2}\det
U_{x+1}+(-1)^{k}\det V_{x+1}\Big{]}.$

Which completes the proof. ∎

######  Example 3.2.

Let $G$ be the chain graph with binary string $b=0^{1}1^{2}0^{2}1^{3}$. Then

$\det U_{x+1}=4,$

and

$\det V_{x+1}=\begin{vmatrix}4&x+1&0\\\\[2.84526pt] x+1&4&x+1\\\\[2.84526pt]
0&x+1&8\end{vmatrix}=128-12(x+1)^{2}.$

Therefore, Seidel characteristic polynomial of $G$ is

$\displaystyle\begin{split}\psi_{S}(x)&=\dfrac{(x+1)^{5}}{2}\Big{[}2(x+1)^{3}-(x+1)^{2}\det
U_{x+1}+\det V_{x+1}\Big{]}\\\\[5.69054pt]
&=(x+1)^{8}-8(x+1)^{7}+64(x+1)^{5}\\\\[2.84526pt]
&=x^{8}-28x^{6}-48x^{5}+110x^{4}+416x^{3}+500x^{2}+272x+57.\end{split}$

In the Theorem 3.1, the expression of characteristic polynomial contains
determinant of two symmetric matrices. The determinant of a symmetric
tridiagonal matrix can be calculated iteratively. Let $B$ be a symmetric
tridiagonal matrix of the form

$B=\begin{bmatrix}a_{1}&b_{1}&0&0&\ldots&0&0\\\\[2.84526pt]
b_{1}&a_{2}&b_{2}&0&\ldots&0&0\\\\[2.84526pt] &&&&\ddots\\\\[2.84526pt]
0&0&0&0&\ldots&a_{n-1}&b_{n-1}\\\\[2.84526pt]
0&0&0&0&\ldots&b_{n-1}&a_{n}\end{bmatrix}.$

If $D_{i}$ denotes the determinant of the principal submatrix by taking first
$i$ rows and columns, then $\det\ B$ can be obtained by using the following
formula

$D_{i}=a_{i}D_{i-1}-b_{i-1}^{2}D_{i-2},$ (10)

where $D_{0}=1$ and $D_{1}=a_{1}$. Further let $a_{1}=a_{2}=\cdots=a_{n}=c$
and $b_{1}=b_{2}=\cdots=b_{n-1}=1$. If $D_{i}(c)$ denotes the determinant of
the principal submatrix by taking first $i$ rows and columns, then the
determinants $D_{i}(c)$, $i\geq 0$ can be computed (see [24, Theorem 3.1]) by

$D_{i}(c)=\begin{cases}\dfrac{\alpha^{i+1}-\beta^{i+1}}{\alpha-\beta}&\text{if
}c\neq\pm 2,\\\\[8.53581pt] i+1&\text{if }c=2,\\\\[5.69054pt]
(-1)^{i}(i+1)&\text{if }c=-2,\end{cases}$ (11)

where $\alpha=\frac{1}{\beta}=\displaystyle{\frac{c+\sqrt{c^{2}-4}}{2}}$.

######  Remark 3.3 (Determinant).

Putting $x=1$ in equation (9), we have

$\det Q_{S}=\frac{1}{2}\Big{[}2+(-1)^{k}(\det V-\det U)\Big{]},$ (12)

where $U=U_{1}$ and $V=V_{1}$. We can find out the determinant of the
tridiagonal matrices $U$ and $V$ by using the recurrence relation (10).
Therefore the determinant of the Seidel matrix is given by,

$\det S=(-1)^{n-2k}\det Q_{S}.$ (13)

######  Corollary 3.4.

Let $n=2k$, that is, $s_{i}=t_{i}=1$ for $i=1,\,2,\ldots,\,k$. Then

$\det S=(-1)^{\frac{n}{2}}\,n+1.$

###### Proof.

By (13), $\det S=\det Q_{S}$. Since $s_{i}=t_{i}=1$, by (11), we obtain

$\det U=D_{2k-3}(2)=2k-2,$

and

$\det V=4D_{2k-2}(2)-D_{2k-3}(2)=6k-2.$

Therefore, from (12), we get

$\displaystyle\det S$ $\displaystyle=$
$\displaystyle\frac{1}{2}\,\Big{[}2+(-1)^{k-1}\det U+(-1)^{k}\det V\Big{]}$
$\displaystyle=$ $\displaystyle(-1)^{\frac{n}{2}}\,n+1.$

Which completes the proof. ∎

##  4 Seidel energy of chain graph

In this section we give some energy bounds for Seidel matrix of chain graphs.
We obtain a better bound of $SE(G)$ than Haemers [18] bound. First we recall
some useful and important results.

######  Lemma 4.1.

[15] If $X,~{}Y,~{}Z$ be three real symmetric matrices of order $n$ such that
$Z=X+Y$, then

$E(Z)\leq E(X)+E(Y),$

where $E(X)=\sum_{i=1}^{n}|\lambda_{i}(X)|$ is the energy of $X$, and
$\lambda_{i}(X)$ $(i=1,2,\ldots,n)$ are the eigenvalues of $X$.

######  Lemma 4.2.

[11] For positive real numbers $a_{1},~{}a_{2},~{}a_{3},\cdots,a_{n}$,

$p_{1}\geq p_{2}^{\frac{1}{2}}\geq p_{3}^{\frac{1}{3}}\geq\cdots\geq
p_{n}^{\frac{1}{n}},$

where $p_{k}$ is the average of products of $k-$element subset of the set
$\\{a_{1},a_{2},a_{3},\ldots,a_{n}\\}$, that is,

$\displaystyle p_{1}$
$\displaystyle=\frac{1}{n}(a_{1}+a_{2}+a_{3}+\cdots+a_{n}),$ $\displaystyle
p_{2}$
$\displaystyle=\frac{1}{\frac{n(n-1)}{2}}(a_{1}a_{2}+a_{1}a_{3}+\cdots+a_{1}a_{n}+a_{2}a_{3}+\cdots+a_{n-1}a_{n}),$
$\displaystyle\vdots$ $\displaystyle p_{n}$ $\displaystyle=a_{1}a_{2}\cdots
a_{n}.$

Moreover, equalities hold if and only if $a_{1}=a_{2}=\cdots=a_{n}$.

######  Lemma 4.3.

Let $\lambda_{1},\,\lambda_{2},\ldots,\,\lambda_{2k}$ be the eigenvalues of
$Q_{S}$. Then $|\lambda_{1}|=|\lambda_{2}|=\cdots=|\lambda_{2k}|$ if and only
if $G\cong K_{2}$.

###### Proof.

First we assume that $|\lambda_{1}|=|\lambda_{2}|=\cdots=|\lambda_{2k}|$.
Since $\lambda_{i}$ $(1\leq i\leq 2k)$ are the eigenvalues of $Q_{S}$, then by
Theorem 2.2, there is an eigenvalue, say, $\lambda_{j}=-1$. By Theorem 2.10,
we have $\lambda_{1}\geq\frac{n}{2}+1-\frac{2k}{n}$. If $n\geq 3$, then
$|\lambda_{1}|\geq 1.5>1=|\lambda_{j}|$, a contradiction as
$|\lambda_{1}|=|\lambda_{2}|=\cdots=|\lambda_{2k}|$. Otherwise, $n=2$ and
hence $G\cong K_{2}$.

Conversely, one can easily see that $|\lambda_{1}|=|\lambda_{2}|$ for $K_{2}$.
∎

We are now at a position to establish the following bounds of Seidel energy of
a chain graph.

######  Theorem 4.4.

Let $G$ be a chain graph of order $n$ with $|\pi|=2k$. Then

$SE(G)\leq n-2k+\sqrt{2k(n^{2}-2n+2k)}$

with equality if and only if $G\cong K_{2}$.

###### Proof.

The multiplicity of the Seidel eigenvalue $-1$ is $n-2k+1$, in which $Q_{S}$
contributes one simple eigenvalue $-1$. Therefore we can write the Seidel
energy in the following form:

$SE(G)=n-2k+\sum\limits^{2k}_{i=1}\,|\lambda_{i}|,$ (14)

where $\lambda_{1},\,\lambda_{2},\ldots,\,\lambda_{2k}$ are the eigenvalues of
$Q_{S}$. By Lemma 2.1, we obtain

$\sum\limits^{2k}_{i=1}\,\lambda^{2}_{i}=trace\ Q_{S}^{2}=n^{2}-2n+2k.$ (15)

Setting $n=2k$ and $a_{i}=|\lambda_{i}|$ $(i=1,\,2,\ldots,\,2k)$ in Lemma 4.2,
we obtain

$\left(\frac{\sum\limits^{2k}_{i=1}\,|\lambda_{i}|}{2k}\right)^{2}\geq\frac{1}{\displaystyle{\frac{2k(2k-1)}{2}}}\,\sum\limits_{i<j}\,|\lambda_{i}|\,|\lambda_{j}|,$
(16)

that is,

$\displaystyle(2k-1)\,\left(\sum\limits^{2k}_{i=1}\,|\lambda_{i}|\right)^{2}$
$\displaystyle\geq 4k\,\sum\limits_{i<j}\,|\lambda_{i}|\,|\lambda_{j}|,$
$\displaystyle=2k\,\left[\left(\sum\limits^{2k}_{i=1}\,|\lambda_{i}|\right)^{2}-\sum\limits^{2k}_{i=1}\,\lambda^{2}_{i}\right],$

that is,

$\left(\sum\limits^{2k}_{i=1}\,|\lambda_{i}|\right)^{2}\leq
2k\,\sum\limits^{2k}_{i=1}\,\lambda^{2}_{i}=2k\,trace\
Q_{S}^{2}=2k\,(n^{2}-2n+2k),$

that is,

$\sum\limits^{2k}_{i=1}\,|\lambda_{i}|\leq\sqrt{2k\,(n^{2}-2n+2k)}.$

Combining the above result with equation (14), we obtain the required result.

Moreover, the equality holds if and only if the equality holds in (16), that
is, if and only if $|\lambda_{1}|=|\lambda_{2}|=\cdots=|\lambda_{2k}|$, that
is, if and only if $G\cong K_{2}$, by Lemma 4.3. ∎

######  Remark 4.5.

Our upper bound in Theorem 4.4 is better than the upper bound given in (1),
that is,

$n-2k+\sqrt{2k\,(n^{2}-2n+2k)}\leq n\,\sqrt{n-1},$

that is,

$2kn^{2}\leq n^{3}-2\,(n-2k)\,n\,\sqrt{n-1},$

that is,

$2\,(n-2k)\,n\,\sqrt{n-1}\leq n^{2}\,(n-2k),$

that is,

$(n-2)^{2}\geq 0,$

which is always true.

######  Theorem 4.6.

Let $G$ be a chain graph of order $n$ with $|\pi|=2k$. Then

$SE(G)\geq n-2k+\sqrt{n^{2}-2n+2k+2k(2k-1)|\det Q_{S}|^{\frac{1}{k}}}.$

###### Proof.

Since $\lambda_{1},\,\lambda_{2},\ldots,\,\lambda_{2k}$ are the eigenvalues of
$Q_{S}$, we have $\prod^{2k}_{i=1}\,|\lambda_{i}|=|\det Q_{S}|$. Setting
$n=2k$ and $a_{i}=|\lambda_{i}|$ $(i=1,\,2,\ldots,\,2k)$ in Lemma 4.2, we
obtain

$\frac{1}{\displaystyle{\frac{2k(2k-1)}{2}}}\,\sum\limits_{i<j}\,|\lambda_{i}|\,|\lambda_{j}|\geq\left(\prod^{2k}_{i=1}\,|\lambda_{i}|\right)^{\frac{1}{k}},$
(17)

that is,

$2\,\sum\limits_{i<j}\,|\lambda_{i}|\,|\lambda_{j}|\geq 2k(2k-1)\,|\det
Q_{S}|^{\frac{1}{k}},$

that is,

$\left(\sum\limits^{2k}_{i=1}\,|\lambda_{i}|\right)^{2}-\sum\limits^{2k}_{i=1}\,\lambda^{2}_{i}\geq
2k(2k-1)\,|\det Q_{S}|^{\frac{1}{k}},$

that is,

$\sum\limits^{2k}_{i=1}\,|\lambda_{i}|\geq\sqrt{n^{2}-2n+2k+2k(2k-1)\,|\det
Q_{S}|^{\frac{1}{k}}},$

by (15). Combining this result with equation (14), we can get the required
result.

Moreover, the equality holds if and only if the equality holds in (17), that
is, if and only if $|\lambda_{1}|=|\lambda_{2}|=\cdots=|\lambda_{2k}|$, that
is, if and only if $G\cong K_{2}$, by Lemma 4.3. ∎

######  Remark 4.7.

This lower bound is better than Haemers’ lower bound given in (1). For
example, consider a chain graph $0^{1}1^{2}0^{1}1^{1}$ on $5$ vertices. Using
Theorem 4.6 and the determinant formula given in Remark 3.3, we obtain
$E(S)\geq 8.78$. On the other hand, inequality (1) gives $E(S)\geq 8$.

We now establish another upper bound for the Seidel energy of chain graphs.

######  Theorem 4.8.

Let $G$ be a chain graph of order $n$ with $|\pi|=2k$. Then

$SE(G)\leq n(3+\sqrt{k})-2.$

###### Proof.

Seidel matrix $S$ of $G$ is given by

$S(G)=J-I-2A(G).$

where $J$ is all $1$ matrix, $I$ is the identity matrix, and $A(G)$ is the
adjacency matrix of $G$. Using Lemma 4.1, we can write

$SE(G)\leq E(J-I)+2E(A(G))=2(n-1)+2E(A(G)),$ (18)

where
$E(J-I)=E(A(K_{n}))=\sum\limits^{n}_{i=1}\,|\lambda_{i}(A(K_{n}))|=2(n-1)$ and
$E(A(G))=\sum\limits^{n}_{i=1}\,|\lambda_{i}(A(G))|$. From [13], we obtain

$E(A(G))\leq\frac{n}{\sqrt{8}}(\sqrt{2k}+\sqrt{2}).$

Using this result in inequality (18), we obtain

$SE(G)\leq 2(n-1)+\frac{2n}{\sqrt{8}}(\sqrt{2k}+\sqrt{2}),$

which gives the required result. ∎

We now consider a special case of chain graph. We call a chain graph symmetric
if $s_{i}=t_{i}=p$ for $1\leq i\leq k$ (for this case only the quotient matrix
of the corresponding chain graph is a symmetric matrix). We have calculated
the characteristic polynomial and energy of Seidel matrix $S$ for
$k=1,\,2,\,3$ in the following example.

######  Example 4.9 (Symmetric chain graphs).

For k=1, the binary string of $G$ is $b=0^{p}1^{p}$. The Seidel eigenvalues
are $-1^{2p-1},~{}2p-1$ and the characteristic polynomial is

$\psi_{S}(x)=(x+1)^{2p-1}(x+1-2p),$

and

$SE(G)=2(2p-1).$

For k=2, the binary string is $b=0^{p}1^{p}0^{p}1^{p}$. The Seidel eigenvalues
are $-1^{4p-3},~{}2p-1,~{}p-1\pm p\sqrt{5}$ and the characteristic polynomial
is

$\psi_{S}(x)=(x+1)^{4p-3}(x+1-2p)\big{[}(1+x)^{2}-2p(x+1)-4p^{2}\big{]},$

and

$SE(G)=2(3+\sqrt{5})p-6.$

For k=3, the binary string of $G$ is $b=0^{p}1^{p}0^{p}1^{p}0^{p}1^{p}$. The
Seidel characteristic polynomial of $G$ is

$\psi_{S}(x)=(x+1)^{6p-5}\big{[}(1+x)^{2}-2p(x+1)-4p^{2}\big{]}\big{[}(x+1)^{3}-4p(x+1)^{2}-4p^{2}(x+1)+8p^{3}\big{]},$

and the Seidel energy of $G$ is given by

$SE(G)=(10+2\sqrt{5})p-6-2\alpha,$

where $\alpha$ is the only negative root of the equation

$x^{3}-4px^{2}-4p^{2}x+8p^{3}=0.$

Let $\Gamma_{n,k}$ be a class of chain graphs of order $n$ with the binary
string $b=0^{s_{1}}\underbrace{1^{1}0^{1}1^{1}0^{1}\ldots
0^{1}}_{2k-2}1^{t_{k}}$ such that $s_{1}+t_{k}=n-2k+2$ with $1\leq s_{1}\leq
n-2k+1$ and $1\leq t_{k}\leq n-2k+1$.

######  Lemma 4.10.

Every chain graph in $\Gamma_{n,k}$ has the same spectrum.

###### Proof.

Let $G\in\Gamma_{n,k}$. Then
$b=0^{s_{1}}\underbrace{1^{1}0^{1}1^{1}0^{1}\ldots 0^{1}}_{2k-2}1^{t_{k}}$ is
the binary string of chain graph $G$. Then the multiplicity of $-1$ is
$n-2k+1$ and $-1$ is a simple eigenvalue of $Q_{S}$. Let $\lambda\neq-1$ be an
eigenvalue of $Q_{S}$ and let
$X=\left[\begin{array}[]{ccccc}x_{1}&x_{2}&x_{3}&\cdots&x_{2k}\end{array}\right]^{T}$
be corresponding eigenvector. Then $Q_{S}X=\lambda X$, that is,

$\displaystyle(s_{1}-1)x_{1}-x_{2}+x_{3}-x_{4}+\cdots+x_{2k-1}-t_{k}x_{2k}$
$\displaystyle=\lambda x_{1},$ (B) $\displaystyle-
s_{1}x_{1}+x_{3}+x_{4}+\cdots+x_{2k-1}+t_{k}x_{2k}$ $\displaystyle=\lambda
x_{2},$ $\displaystyle s_{1}x_{1}+x_{2}-x_{4}+\cdots+x_{2k-1}-t_{k}x_{2k}$
$\displaystyle=\lambda x_{3},$ $\displaystyle-
s_{1}x_{1}+x_{2}-x_{3}+\cdots+x_{2k-1}+t_{k}x_{2k}$ $\displaystyle=\lambda
x_{4},$
$\displaystyle\ldots~{}~{}\ldots~{}~{}\ldots~{}~{}\ldots~{}~{}~{}\ldots~{}~{}\ldots{}{}{}{}{}{}{}{}{}$
$\displaystyle~{}~{}\vdots$ $\displaystyle
s_{1}x_{1}+x_{2}+x_{3}+x_{4}+\cdots+x_{2k-2}-t_{k}x_{2k}$
$\displaystyle=\lambda x_{2k-1},$ $\displaystyle-
s_{1}x_{1}+x_{2}-x_{3}+x_{4}+\cdots-x_{2k-1}+(t_{k}-1)x_{2k}$
$\displaystyle=\lambda x_{2k}.$

Since $\lambda\neq-1$, from the first and last equations, we obtain

$x_{1}=-x_{2k}.$

Using $x_{1}=-x_{2k}$ and $s_{1}+t_{k}=n-2k+2$ in the system of equations (B),
we obtain the following system of $2k-1$ equations:

$\displaystyle(n-2k+1)x_{1}-x_{2}+x_{3}-x_{4}+\ldots+x_{2k-1}$
$\displaystyle=\lambda x_{1},$ (C)
$\displaystyle-(n-2k+2)x_{1}+x_{3}+x_{4}+\ldots+x_{2k-1}$
$\displaystyle=\lambda x_{2},$
$\displaystyle(n-2k+2)x_{1}+x_{2}-x_{4}+\ldots+x_{2k-1}$
$\displaystyle=\lambda x_{3},$
$\displaystyle-(n-2k+2)x_{1}+x_{2}-x_{3}+\ldots+x_{2k-1}$
$\displaystyle=\lambda x_{4},$
$\displaystyle\ldots~{}~{}\ldots~{}~{}\ldots~{}~{}\ldots~{}~{}~{}\ldots~{}~{}\ldots{}{}{}{}{}{}{}{}{}{}{}{}$
$\displaystyle~{}~{}\vdots$
$\displaystyle(n-2k+2)x_{1}+x_{2}+x_{3}+x_{4}+\ldots+x_{2k-2}$
$\displaystyle=\lambda x_{2k-1}.$

The above system of equations (C) is independent of $s_{1}$ and $t_{k}$.
Therefore system provides the same values of $\lambda$ for every choice of
$s_{1}$ and $t_{k}$ with $s_{1}+t_{k}=n-2k+2$. Therefore every chain graph in
$\Gamma_{n,k}$ has the same spectrum. ∎

######  Corollary 4.11.

Every chain graph in $\Gamma_{n,k}$ has the same Seidel energy.

######  Lemma 4.12.

Let $H\in\Gamma_{n,2}$. Then

$Spec_{S}(H)=\left\\{\frac{n-4\pm\sqrt{n^{2}+4n-12}}{2},\,1,-1^{n-3}\right\\}.$

###### Proof.

Since $H\in\Gamma_{n,2}$, the characteristic polynomial of $S(H)$ is

$\displaystyle\psi_{S}(x)$
$\displaystyle=(x+1)^{n-3}\,\Big{[}x^{3}-(s_{1}+t_{2}-1)\,x^{2}-(2s_{1}+2t_{2}+1)\,x+3s_{1}+3t_{2}-1\Big{]}$
$\displaystyle=(x+1)^{n-3}\,(x-1)\,\Big{[}x^{2}-(s_{1}+t_{2}-2)\,x-3s_{1}-3t_{2}+1\Big{]}$
$\displaystyle=(x+1)^{n-3}\,(x-1)\,\Big{[}x^{2}-(n-4)\,x-3n+7\Big{]},$

which gives the required result. ∎

######  Theorem 4.13.

Let $G$ be a chain graph of order $n$ with the binary string
$b=0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}$ $(s_{1}+s_{2}+t_{1}+t_{2}=n)$. Then
$SE(G)\geq n-2+\sqrt{n^{2}+4n-12}$ with equality if and only if
$G\in\Gamma_{n,2}$.

###### Proof.

First we assume that $G\in\Gamma_{n,2}$. Then by Lemma 4.12, we obtain

$SE(G)=n-2+\sqrt{n^{2}+4n-12}$

and hence the equality holds.

$G_{1}$ Figure 1: Graph $G_{1}$.

Next we assume that $G\notin\Gamma_{n,2}$. Then $2\leq s_{1}+t_{2}\leq n-3$
and $n\geq 5$. For $n=5$, $G\cong G_{1}$ (see, Fig. 1). One can easily obtain
that

$Spec_{S}(G_{1})=\left\\{3,\,1.56,\,-1^{2},\,-2.56\right\\}.$

Hence

$SE(G_{1})>9.12>8.75>n-2+\sqrt{n^{2}+4n-12}.$

Otherwise, $n\geq 6$. Now, the characteristic polynomial of $G$ is given by

$\psi_{S}(x)=(x+1)^{n-3}\,\Big{[}(x+1)^{3}-n(x+1)^{2}+4s_{2}t_{1}(s_{1}+t_{2})\Big{]}.$
(19)

Let $\lambda_{1}\geq\lambda_{2}\geq\lambda_{3}$ be the roots of the following
equation:

$f(x)=0,$

where

$f(x)=x^{3}-(n-3)\,x^{2}-(2n-3)\,x-n+1+4s_{2}t_{1}(s_{1}+t_{2}).$ (20)

Then $\psi_{S}(x)=(x+1)^{n-3}\,f(x)$. Moreover, we obtain

$\displaystyle\lambda_{1}+\lambda_{2}+\lambda_{3}$ $\displaystyle=n-3,$ (21)
$\displaystyle\lambda_{1}\,\lambda_{2}+\lambda_{2}\,\lambda_{3}+\lambda_{3}\,\lambda_{1}$
$\displaystyle=-(2n-3),$ (22)
$\displaystyle\lambda_{1}\,\lambda_{2}\,\lambda_{3}$
$\displaystyle=n-1-4s_{2}t_{1}(s_{1}+t_{2}).$ (23)

Claim 1. $\lambda_{1}\geq\lambda_{2}>1$ and $\lambda_{3}<0$.

Proof of Claim 1. Let us consider a function

$h(x,y)=xy\,(n-x-y),$

where $x$ are $y$ are positive integers such that $3\leq x+y\leq n-2$ and
$x\geq y\geq 1$. Since $x+y\geq 3$, we have $x\geq 2$. We have to prove that

$xy\,(n-x-y)\geq 2\,(n-3).$ (24)

First we assume that $y=1$. Then $2\leq x\leq n-3$. One can easily check that
$g(x)=x\,(n-x-1)$ is an increasing function on $x\leq\frac{n-1}{2}$ and a
decreasing function on $x\geq\frac{n-1}{2}$. Then
$xy\,(n-x-y)=x\,(n-x-1)\geq\min\\{g(2),\,g(n-3)\\}=2\,(n-3)$. Hence (24)
holds.

Next we assume that $y\geq 2$. If $x+y<\frac{n+1}{2}$, then
$xy\,(n-x-y)>2\,(n-3)$ as $x\geq 2$ and $y\geq 2$. Again (24) holds.
Otherwise, $x+y\geq\frac{n+1}{2}$. Then $x\geq\frac{n+1}{4}$ as $x\geq y$. For
$x+y\leq n-4$, we have

$xy\,(n-x-y)\geq 2\,(n+1)>2\,(n-3)~{}~{}\mbox{ as }y\geq 2~{}\mbox{ and
}n-x-y\geq 4,$

(24) holds. For $x+y=n-3$, we have

$xy\,(n-x-y)=3x(n-x-3)\geq 6(n-5)\geq 2\,(n-3)$

as $n\geq 6$,$\frac{n-3}{2}\leq x\leq n-5$. Again (24) holds. For $x+y=n-2$,

$xy\,(n-x-y)=2x\,(n-x-2)\geq 4(n-4)>2\,(n-3)$

as $\frac{n-2}{2}\leq x\leq n-4$ and $n\geq 6$. Hence (24) holds.

Since $s_{1}+s_{2}+t_{1}+t_{2}=n$, we obtain
$s_{2}t_{1}(s_{1}+t_{2})=s_{2}t_{1}\,(n-s_{2}-t_{1})\geq 2\,(n-3)$, by (24).
Using this result in (23), we obtain $\lambda_{1}\,\lambda_{2}\,\lambda_{3}<0$
as $n\geq 6$. Therefore $\lambda_{i}<0$ for $1\leq i\leq 3$, or
$\lambda_{1}\geq\lambda_{2}>0$ and $\lambda_{3}<0$. By (21), $\lambda_{i}<0$
$(1\leq i\leq 3)$ is not possible. Thus we have $\lambda_{1}\geq\lambda_{2}>0$
and $\lambda_{3}<0$. From (20), we obtain $f(x)\rightarrow+\infty$ as
$x\rightarrow\infty$ and

$f(1)=-4n+8+4s_{2}t_{1}(s_{1}+t_{2})=4\,\Big{[}-(n-2)+s_{2}t_{1}\,(n-s_{2}-t_{1})\Big{]}\geq
4\,(n-4)>0$

as $s_{1}+s_{2}+t_{1}+t_{2}=n$ and by (24). These results with (21), we obtain
$\lambda_{1}\geq\lambda_{2}>1$. This proves Claim 1.

Claim 2.
$\lambda_{1}\,\lambda_{2}>\displaystyle{\frac{n-4+\sqrt{n^{2}+4n-12}}{2}}$.

Proof of Claim 2. We consider the following two cases:

${\bf Case\,1.}$ $\lambda_{3}\leq-3$. We have
$\lambda_{1}+\lambda_{2}=n-3-\lambda_{3}\geq n$. Since $f(x)=x\,(n-x)$ is an
increasing function on $x\leq n/2$ and a decreasing function on $x\geq n/2$,
we obtain

$\lambda_{1}\,\lambda_{2}\geq(n-\lambda_{2})\,\lambda_{2}\geq
n-1>\frac{n-4+\sqrt{n^{2}+4n-12}}{2}$

as $1<\lambda_{2}<\frac{n-3}{2}$.

${\bf Case\,2.}$ $-3<\lambda_{3}<0$. Since $s_{1}+t_{2}\leq n-3$, we have
$3\leq s_{2}+t_{1}\leq n-2$. Since
$s_{2}t_{1}(s_{1}+t_{2})=s_{2}t_{1}\,(n-s_{2}-t_{1})\geq 2(n-3)$, from (23),
we obtain

$\lambda_{1}\,\lambda_{2}\,\lambda_{3}=n-1-4s_{2}t_{1}(s_{1}+t_{2})\leq-7n+23,$

that is,

$\lambda_{1}\,\lambda_{2}\geq\frac{-7n+23}{\lambda_{3}}\geq
n-1>\frac{n-4+\sqrt{n^{2}+4n-12}}{2}$

as $n\geq 6$. Which proves Claim 2.

By Claims 1 and 2 with (22), we obtain

$\displaystyle(|\lambda_{1}|+|\lambda_{2}|+|\lambda_{3}|)^{2}$
$\displaystyle=(\lambda_{1}+\lambda_{2}-\lambda_{3})^{2}$
$\displaystyle=(\lambda_{1}+\lambda_{2}+\lambda_{3})^{2}-4\,(\lambda_{1}\lambda_{2}+\lambda_{2}\lambda_{3}+\lambda_{3}\lambda_{1})+4\,\lambda_{1}\lambda_{2}$
$\displaystyle=(n-3)^{2}+4\,(2n-3)+2\,[n-4+\sqrt{n^{2}+4n-12}]$
$\displaystyle>n^{2}+4n-11+2\,\sqrt{n^{2}+4n-12}=(\sqrt{n^{2}+4n-12}+1)^{2},$

that is,

$|\lambda_{1}|+|\lambda_{2}|+|\lambda_{3}|>\sqrt{n^{2}+4n-12}+1.$

Since

$Spec_{S}(G)=\Big{\\{}\lambda_{1},\,\lambda_{2},\,\lambda_{3},\,-1^{n-3}\Big{\\}},$

we obtain

$SE(G)=n-3+|\lambda_{1}|+|\lambda_{2}|+|\lambda_{3}|>n-2+\sqrt{n^{2}+4n-12}.$

This completes the proof of the theorem. ∎

From the motivation of the above theorem with Corollary 4.11, we state the
following conjecture:

######  Conjecture 4.14.

Let $G$ be a chain graph of order $n$ with the binary string
$b=0^{s_{1}}1^{t_{1}}0^{s_{2}}\ldots 0^{s_{k}}1^{t_{k}}$ such that
$\sum\limits^{k}_{i=1}\,(s_{i}+t_{i})=n,\,s_{i}\geq 1\,(1\leq i\leq k)$, and
$t_{i}\geq 1\,(1\leq i\leq k)$. Then $SE(G)\geq SE(H)$, where
$H\in\Gamma_{n,k}$. Moreover, the equality holds if and only if
$G\in\Gamma_{n,k}$.

## Acknowledgements

S. Mandal thanks to University Grants Commission, India for financial support
under the beneficiary code BININ01569755. K. C. Das is supported by National
Research Foundation funded by the Korean government (Grant No.
2021R1F1A1050646).

## References

  * [1] S. Akbari, M. Einollahzadeh, M. M. Karkhaneei, M. A. Nematollahi, Proof of a conjecture on the Seidel energy of Graphs, European J. Combin. 86 (2020) 103078, 8 pp.
  * [2] S. Akbari, J. Aksari, K. C. Das, Some properties of eigenvalues of the Seidel matrix, Linear Multilinear Algebra (2020), in press. DOI: doi.org/10.1080/03081087.2020.1790481
  * [3] A. Alazemi, M. Anđelić, K. C. Das, C. M. D. Fonseca, Chain graph sequences and Laplacian spectra of chain graphs, Linear Multilinear Algebra (2022), in press.
  * [4] A. Alazemi, M. Anđelić, S. K. Simić, Eigenvalue location for chain graphs, Linear Algebra Appl. 505 (2016) 194–210.
  * [5] M. Anđelić, S. K. Simić, D. Zivković, E. Dolicanin, Fast algorithm for computing the characteristic polynomial of threshold and chain graphs, Appl. Math. Comput. 332 (2018) 329–337.
  * [6] J. Askari, A. Iranmanesh, K. C. Das, Seidel-Estrada Index, Jour. Ineq. Appl. (2016) 2016: 120.
  * [7] F. K. Bell, D. Cvetković, P. Rowlinson, S. K. Simić, Graphs for which least eigenvalue is minimal, I, Linear Algebra Appl. 429 (2008) 234–241.
  * [8] F. K. Bell, D. Cvetković, P. Rowlinson, S. K. Simić, Graphs for which least eigenvalue is minimal, II, Linear Algebra Appl. 429 (2008) 2168–2179.
  * [9] A. Berman, N. S. Monderer, R. Singh, X. D. Zhang, Complete multipartite graphs that are determined, up to switching, by their Seidel spectrum, Linear Algebra Appl. 564 (2019) 58–71.
  * [10] A. Bhattacharya, S. Friedland, U. N. Peled, On the first eigenvalue of bipartite graphs, Electron. J. Combin. 15 (1) (2008) #144, 23pp.
  * [11] P. Biler, A. Witkowski, Problems in Mathematical Analysis, Chapman and Hall, New York, 1990.
  * [12] A. E. Brouwer, W. H. Haemers, Spectra of Graphs, Springer, New York, 2012.
  * [13] K. C. Das, A. Alazemi, M. Anđelić, On energy and Laplacian energy of chain graphs, Discrete Appl. Math. 284 (2020) 391–400.
  * [14] K. C. Das, I. Gutman, Bounds for the energy of graphs, Hacet. J. Math. Stat. 45 (3) (2016) 695–703.
  * [15] K. Fan, Maximum properties and inequalities for the eigenvalues of completely continuous operators, Proc. Nat. Acad. Sci. USA. 37 (1951) 760–766.
  * [16] E. Ghorbani, On eigenvalues of Seidel matrices and Haemers’ conjecture, Des. Codes Cryptogr. 84 (1-2) (2017) 189–195.
  * [17] C. Godsil, G. Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001.
  * [18] W. H. Haemers, Seidel Switching and Graph Energy, MATCH Commun. Math. Comput. Chem. 68 (2012) 653–659.
  * [19] A. Iranmanesh, J. A. Farsangi, Upper and lower bounds for the power of eigenvalues in Seidel matrix, J. Appl. Math. Inform. 33 (5-6) (2015) 627–633. DOI: dx.doi.org/10.14317/jami.2015.627
  * [20] S. Mandal, R. Mehatari, On the Seidel spectrum of threshold graphs, (2021). Preprint: arXiv:2101.03364.
  * [21] Y. Mei, C. Guo, M. Liu, The bounds of the energy and Laplacian energy of chain graphs, AIMS Math. 6 (5) (2021) 4847–4859. DOI: 10.3934/math.2021284
  * [22] M. R. Oboudi, Energy and Seidel energy of graphs, MATCH Commun. Math. Comput. Chem. 75 (2016) 291–303.
  * [23] M. R. Oboudi, Seidel energy of complete multipartite graphs, Spec. Matrices 9 (2021) 212–216. DOI: doi.org/10.1515/spma-2020-0131.
  * [24] F. Qi, V. Čerňanová, Y. S. Semenov, Some tridiagonal determinants related to central Delannoy numbers, the Chebyshev polynomials, and the Fibonacci polynomials, Politehn. Univ. Bucharest Sci. Bull. Ser. A Appl. Math. Phys. 81 (2019) 123–136.
  * [25] H. S. Ramane, K. Ashoka, D. Patil, On the Seidel Laplacian and Seidel signless Laplacian polynomials of graphs, Kyungpook Math. J. 61 (1) (2021) 155–168. DOI: doi.org/10.5666/KMJ.2021.61.1.155
  * [26] H. Wolkowicz, G. P. H. Styan, Bounds for the eigenvalues using traces, Linear Algebra Appl. 29 (1980) 471–506.