# Eigenvalues of signed graphs 111Supported by NSFC (Nos. 11901498, 11771141
and 12011530064), Tianshan Youth Project of Xinjiang(No. 2019Q069), the
Scientific Research Plan of Universities in Xinjiang, China (No.
XJEDU2021I001), XJTCDP (No. 04231200746), BS (No. 62031224601).

Dan Lia, Huiqiu Linb, Jixiang Menga
aCollege of Mathematics and System Science, Xinjiang University, Urumqi
830046, PR China
bSchool of Mathematics, East China University of Science and Technology,
Shanghai 200237, PR China Corresponding author. E-mail<EMAIL_ADDRESS>(H.Q. Lin<EMAIL_ADDRESS>(D. Li<EMAIL_ADDRESS>(J.X. Meng).

Abstract:

Signed graphs have their edges labeled either as positive or negative.
$\rho(M)$ denote the $M$-spectral radius of $\Sigma$, where $M=M(\Sigma)$ is a
real symmetric graph matrix of $\Sigma$. Obviously,
$\rho(M)=\mbox{max}\\{\lambda_{1}(M),-\lambda_{n}(M)\\}$. Let $A(\Sigma)$ be
the adjacency matrix of $\Sigma$ and $(K_{n},H^{-})$ be a signed complete
graph whose negative edges induce a subgraph $H$. In this paper, we first
focus on a central problem in spectral extremal graph theory as follows: Which
signed graph with maximum $\rho(A(\Sigma))$ among $(K_{n},T^{-})$ where $T$ is
a spanning tree? To answer the problem, we characterize the extremal signed
graph with maximum $\lambda_{1}(A(\Sigma))$ and minimum
$\lambda_{n}(A(\Sigma))$ among $(K_{n},T^{-})$, respectively. Another
interesting graph matrix of a signed graph is distance matrix, i.e.
$D(\Sigma)$ which was defined by Hameed, Shijin, Soorya, Germina and Zaslavsky
[8]. Note that $A(\Sigma)=D(\Sigma)$ when $\Sigma\in(K_{n},T^{-})$. In this
paper, we give upper bounds on the least distance eigenvalue of a signed graph
$\Sigma$ with diameter at least 2. This result implies a result proved by Lin
[11] was originally conjectured by Aouchiche and Hansen [1].

Keywords: Signed graph; signed distance matrix; spectral radius; the least
distance eigenvalue

AMS Classification: 05C50; 05C35

##  1 Introduction

All the underlying graphs in our consideration are simple and connected,
unless otherwise stated. A signed graph $\Sigma=(G,\sigma)$ consists of a
underlying graph $G=(V,E)$ with a signature function
$\sigma:E\rightarrow\\{-1,1\\}$. The (unsigned) graph $G$ is said to be the
underlying graph of $\Sigma$, while the function $\sigma$ is called the
signature of $\Sigma$. In signed graphs, edge signs are usually interpreted as
$\pm 1$. Signed graphs first appeared in works of Harary [7] and Cartwright
and Harary [4], and the matroids of graphs were extended to matroids of signed
graphs by Zaslavsky [16]. Chaiken [3] and Zaslavsky [16] obtained the Matrix-
Tree Theorem for signed graph independently. In fact, the theory of signed
graphs is a special case of that of gain graphs and of biased graphs [17]. In
the very beginnings, these graphs are studied in the context of social
psychology where the vertices are considered as individuals, while positive
edges represent friendships and negative edges enmities between them. The
notion of balance was introduced by Harary in [7], it plays a central role in
the matroid theory of signed graphs. A signed cycle is called positive (resp.
negative) if it contains an even (resp. odd) number of negative edges. A
signed graph is balanced if all its cycles are positive; otherwise it is
unbalanced. Unsigned graphs are treated as (balanced) signed graphs where all
edges get a positive sign, that is, the all-positive signature.

Let $M=M(\Sigma)$ be a real symmetric graph matrix of a signed graph
$\Sigma=(G,\sigma)$ and $P_{M}(\lambda)=\mbox{det}(\lambda I-M)$ be the
$M$-polynomial. The spectrum of $M$ is called the $M$-spectrum of the signed
graph $\Sigma$. As usual, we use
$\lambda_{1}(M)\geq\lambda_{2}(M)\geq\cdots\geq\lambda_{n}(M)$ to denote the
spectrum of $M$. The adjacency matrix of $\Sigma$ is defined as
$A(\Sigma)=(a^{\sigma}_{ij})$, where $a^{\sigma}_{ij}=\sigma(v_{i}v_{j})$ if
$v_{i}\thicksim v_{j}$, and $0$ otherwise.

Our first motivation is from Koledin and Stanić [9] who studied the connected
signed graphs of fixed order, size, and number of negative edges with maximum
index. In the paper, they conjectured that if $\Sigma$ is a signed complete
graph of order $n$ with $k$ negative edges, $k<n-1$ and $\Sigma$ has maximum
index, then the negative edges induce the signed star $K_{1,k}$. Akbari,
Dalvandi, Heydari and Maghasedi [2] proved the conjecture holds for signed
complete graphs whose negative edges form a tree. Very recently, Ghorbani and
Majidi [6] confirmed the conjecture. In this paper, we first consider an
unbalanced signed complete graph of order $n$ with $k$ negative edges whose
negative edges form a spanning tree, i.e., $k=n-1$. Let $T_{a,b}$ denote the
double star obtained by adding $a$ pendent vertices to one end vertex of
$P_{2}$ and $b$ pendent vertices to the other. Then we have the following
result.

######  Theorem 1.

Let $\Sigma$ be an unbalanced signed complete graphs with order $n\geq 6$
whose negative edges form a spanning tree $T$ and maximizes the
$\lambda_{1}(A(\Sigma))$, then $T\cong T_{1,n-3}$.

Note that $A(\Sigma)$ is a real symmetric matrix. Then the spectral radius of
$\Sigma$ is the largest absolute value of the eigenvalues of $A(\Sigma)$,
denoted by $\rho(A(\Sigma))$, i.e.,
$\rho(A(\Sigma))=\mbox{max}\\{\lambda_{1}(A(\Sigma)),-\lambda_{n}(A(\Sigma))\\}$.
A further question is asked as follows.

######  Problem 1.

Which connected signed graphs with maximum $\rho(A(\Sigma))$ among the
unbalanced signed complete graphs with order $n$ whose negative edges form a
spanning tree?

In order to give the answer to problem 1, a key problem is to characterize the
unbalanced signed complete graph with order $n$ whose negative edges form a
spanning tree minimizes $\lambda_{n}(A(\Sigma))$. Up to now, a lot of
researchers pay attention to $\lambda_{n}(A(\Sigma))$. Vijayakumar [13] showed
that any connected signed graph with smallest eigenvalue less than $-2$ has an
induced signed subgraph with at most 10 vertices and smallest eigenvalue less
than $-2$. Chawathe and Vijayakumar [5] determined all minimal forbidden
signed graphs for the class of signed graphs whose smallest eigenvalue is at
least $-2$. Vijayakumar [14] showed that any signed graph with least
eigenvalue $<-2$ contains an induced subgraph the least eigenvalue of which
equals $-2$, Singhi and Vijayakumar [12] gave a simple proof subsequently. Let
$\mathcal{T}_{a-1,b-1}$ (see Figure 1) denote the graph obtained from
$K_{1,a-1}$ and $K_{1,b-1}$ by adding an edge between two pendent vertices of
them. In the paper, we determine the unbalanced signed complete graphs with
order $n$ whose negative edges form a spanning tree $T$, which minimizes
$\lambda_{n}(A(\Sigma))$.

######  Theorem 2.

Let $\Sigma$ be an unbalanced signed complete graphs with order $n\geq 6$
whose negative edges form a spanning tree $T$ and minimizes the
$\lambda_{n}(A(\Sigma))$. Then
$T\cong\mathcal{T}_{\lceil\frac{n}{2}\rceil-1,\lfloor\frac{n}{2}\rfloor-1}$.

Let $(K_{n},H^{-})$ be a signed complete graph whose negative edges induce a
subgraph $H$. Note that
$\lambda_{1}(A((K_{5},T^{-}_{1,2})))=-\lambda_{n}(A((K_{5},P^{-}_{5})))=3$ for
$n=5$ and
$-\lambda_{n}(A((K_{n},\mathcal{T}^{-}_{\lceil\frac{n}{2}\rceil-1,\lfloor\frac{n}{2}\rfloor-1})))<n-2<\lambda_{1}(A((K_{n},T^{-}_{1,n-3})))$
for $n\geq 6$. Then by Theorems 1 and 2, we finally give an answer to problem
1.

######  Theorem 3.

Let $\Sigma$ be an unbalanced signed complete graph with order $n$ whose
negative edges form a spanning tree $T$ and maximizes the $\rho(A(\Sigma))$.
Then

  1. (I)

$T\cong T_{1,2}$ or $T\cong P_{5}$ when $n=5$;

  2. (II)

$T\cong T_{1,n-3}$ for $n\geq 6$.

$T_{1,n-3}$$\mathcal{T}_{a-1,b-1}$$S^{+}_{2,n-2}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{n}$
Figure 1: The graphs $T_{1,n-3}$, $\mathcal{T}_{a-1,b-1}$ and $S^{+}_{2,n-2}$.

Another interesting graph matrix on signed graph is distance matrix. The
definition is given by Hameed, Shijin, Soorya, Germina and Zaslavsky [8]. The
sign of a path $P$ in $\Sigma$ is defined as $\sigma(P)=\Pi_{e\in
E(P)}\sigma(e)$. Let $P_{(u,v)}$ denote a shortest path between vertices $u$
and $v$ and $\mathcal{P}_{(u,v)}=\\{P_{(u,v)}\mid u,v~{}\mbox{are two given
vertices of}~{}G\\}$. Let $\sigma_{max}(u,v)=\max\\{\sigma(P_{(u,v)})\mid
P_{(u,v)}\in\mathcal{P}_{(u,v)}\\}$ and
$\sigma_{min}(u,v)=\min\\{\sigma(P_{(u,v)})\mid
P_{(u,v)}\in\mathcal{P}_{(u,v)}\\}$. The distance between vertices $u$ and
$v$, i.e., the length of a shortest path between $u$ and $v$, is denoted by
$d_{uv}$. Let $d_{max}(u,v)=\sigma_{max}(u,v)d_{uv}$ and
$d_{min}(u,v)=\sigma_{min}(u,v)d_{uv}$. Two types of distance matrices in a
signed graph are defined as $D^{max}(\Sigma)=(d_{max}(u,v))_{n\times n}$ and
$D^{min}(\Sigma)=(d_{min}(u,v))_{n\times n}$. Two vertices $u$ and $v$ in a
signed graph $\Sigma$ are said to be distance-compatible (briefly, compatible)
if $d_{max}(u,v)=d_{min}(u,v)$. And $\Sigma$ is said to be
(distance-)compatible if every two vertices are compatible. Then
$D^{max}(\Sigma)=D^{min}(\Sigma)=D^{\pm}(\Sigma)$.

If we consider about signed complete graphs, then $A(\Sigma)=D^{\pm}(\Sigma)$.
The diameter of $\Sigma=(G,\sigma)$ is the diameter of its underlying graph
$G$, namely, the maximum distance between any two vertices in $G$, denoted by
$d$ or $d(G)$. Our second motivation of the paper is from the following
problem: what are the upper bound on eigenvalues of a signed distance matrix
with diameter $d\geq 2$? In this paper, we give an upper bound on the least
eigenvalues of the signed distance matrices. Let
$K_{2,n-4}=2K_{1}\vee(n-4)K_{1}$ and $2K_{1}=\\{v_{2},v_{3}\\}$ and let
$S^{+}_{2,n-2}$ (see Figure 1) denote the graph obtained from $K_{2,n-4}$ by
adding an edge between $v_{2}$ and $v_{3}$ and attaching two pendent vertices
to each vertex of $v_{2}$ and $v_{3}$, respectively. Now we have the following
result.

######  Theorem 4.

Let $\Sigma=(G,\sigma)$ be a connected signed graph with diameter $d(G)=d$.
Then we have the following statements.

  1. (I)

If $d=2$, then $\max\\{\lambda_{n}(D^{max}),~{}\lambda_{n}(D^{min})\\}\leq-2$
with equality holding if and only if $\Sigma$ is a balanced signed complete
$k$-partite graph with $2\leq k\leq n-1$;

  2. (II)

If $d=3$, then
$\max\\{\lambda_{n}(D^{max}),~{}\lambda_{n}(D^{min})\\}\leq-2-\sqrt{2}$ with
equality holding if and only if $\Sigma$ is a signed graph with underlying
graph $S^{+}_{2,n-2}$ such that all triangles with the same sign;

  3. (III)

If $d\geq 4$, then
$\max\\{\lambda_{n}(D^{max}),\lambda_{n}(D^{min})\\}\leq-\frac{4}{3}(d-1)$.

It is worth to mention that Theorem 4 implies that $\lambda_{n}(D)\leq-d$ with
equality holding if and only if $G$ is a complete multipartite graph which was
conjectured by Aouchiche and Hansen [1] and confirmed by Lin [11].

##  2 Proof of Theorem 1

######  Lemma 1.

[2] Let $\Sigma=(K_{n},T^{-}_{s,t})$ be a signed complete graph and $n\geq
s+t+2$. Then

$\displaystyle P_{D^{\pm}(\Sigma)}(\lambda)$
$\displaystyle=(\lambda+1)^{n-5}({\lambda}^{5}+\left(5-n\right){\lambda}^{4}+\left(10-4\,n\right){\lambda}^{3}$
$\displaystyle+\left(4ku+8\,st-6\,n+10\right){\lambda}^{2}+\left(8ku+16\,st-4\,n+5\right)\lambda+4ku+8st-16stu+1-n),$

where $k=s+t+1$ and $u=n-s-t-2$.

######  Remark 1.

Let $n=s+t+2$ and
$g_{s,t}(\lambda)={\lambda}^{5}+\left(5-n\right){\lambda}^{4}+\left(10-4\,n\right){\lambda}^{3}+\left(8\,st-6\,n+10\right){\lambda}^{2}+\left(16\,st-4\,n+5\right)\lambda+8st+1-n$,
where $1\leq s\leq t$ and $1\leq s\leq\lfloor\frac{n-2}{2}\rfloor$. Note that
$g_{s-1,t+1}(\lambda)-g_{s,t}(\lambda)=-8(\lambda+1)^{2}(n-2s-1)<0$ for
$\lambda\neq-1$, thus
$\lambda_{1}(A((K_{n},T^{-}_{s,t})))<\lambda_{1}(A((K_{n},T^{-}_{s-1,t+1})))<\lambda_{1}(A((K_{n},T^{-}_{1,n-3})))$
for $s\geq 2$.

By Lemma 1, we can get the characteristic polynomial of
$\Sigma=(K_{n},T^{-}_{1,n-3})$ is

$P_{D^{\pm}(\Sigma)}(\lambda)=(\lambda+1)^{n-3}({\lambda}^{3}+\left(3-n\right){\lambda}^{2}+\left(3-2\,n\right){\lambda}+7n-23).$

Let
$g(\lambda)={\lambda}^{3}+\left(3-n\right){\lambda}^{2}+\left(3-2\,n\right){\lambda}+7n-23$.
Note that $g(n-2)=-(n-5)^{2}<0$, thus
$\lambda_{1}(A((K_{n},T^{-}_{1,n-3})))>n-2$ for $n\geq 6$.

######  Lemma 2.

[9] Let $r,s,t$ and $u$ be distinct vertices of a signed graph $\Sigma$,
$X=(x_{1},x_{2},\ldots,x_{n})^{T}$ be an eigenvector corresponding to
$\lambda_{1}(A(\Sigma))$. Then

  1. (i)

let $\Sigma^{\prime}$ be obtained from $\Sigma$ by reversing the sign of the
positive edge $rs$ and the negative edge $rt$. If

$\left\\{\begin{array}[]{ll}x_{r}\geq 0,x_{t}\geq x_{s}~{}~{}or\\\ x_{r}\leq
0,x_{t}\leq x_{s},\end{array}\right.$

then $\lambda_{1}(A(\Sigma))\leq\lambda_{1}(A(\Sigma^{\prime}))$. If at least
one inequality for the entries of $X$ is strict, then
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$;

  2. (ii)

let $\Sigma^{\prime}$ be obtained from $\Sigma$ by reversing the sign of the
positive edge $rs$ and the negative edge $tu$. If $x_{r}x_{s}\leq x_{t}x_{u}$,
then $\lambda_{1}(A(\Sigma))\leq\lambda_{1}(A(\Sigma^{\prime}))$. If at least
one of the entries $x_{r},x_{s},x_{t},x_{u}$ is distinct from zero, then
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$.

Let $N_{G}(v)$ or $N(v)$ denote the neighbor set of vertex $v$ of $G$ and
$d_{G}(v)=\mid N_{G}(v)\mid$ be the degree of the vertex $v$ in $G$. For any
$U\subset V(G)$, let $N_{G}(U)$ denote the neighbor set of vertices $v\in U$
of $G$.

###### Proof of Theorem 1..

Since $\Sigma$ is an unbalanced signed complete graphs, $T\ncong K_{1,n-1}$,
$d(T)>2$ and $\lambda_{1}(A(\Sigma))<n-1$. Let
$X=(x_{1},x_{2},\ldots,x_{n})^{T}$ be an unit eigenvector corresponding to
$\lambda_{1}(A(\Sigma))$. By arranging the vertices of $\Sigma$ appropriately,
we can assume that $V(\Sigma)=\\{v_{1},v_{2},\ldots,v_{n}\\}$ such that
$x_{1}\leq x_{2}\leq\cdots\leq x_{n}$.

$\underline{\mbox{Case 1. }}$ $X$ is a nonnegative eigenvector. Obviously,
$x_{n}>0$ since $X\neq\mathbf{0}$.

######  Claim 2.

$d_{T}(v_{1})\geq 2$.

Otherwise, let $v_{t}v_{1}\in E(T)$, then $d_{T}(v_{t})\geq 2$ since $d(T)\geq
3$. If $x_{t}=x_{1}$, then we just need to exchange the subscripts $v_{t}$ and
$v_{1}$, as desired. If $x_{t}>x_{1}$, then we can construct a new signed
graph $\Sigma^{\prime}$ by reversing the sign of the positive edge $v_{1}w$
and the negative edge $v_{t}w$ for any $w\in N_{T}(v_{t})\setminus\\{v_{1}\\}$
whose negative edges also form a spanning tree such that
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2, a
contradiction.

Let $x_{p}=\mbox{min}_{w\in N_{T}(v_{1})}x_{w}$ and $x_{q}=\mbox{max}_{w\in
N_{T}(v_{1})}x_{w}$.

######  Claim 3.

$p=2.$

Otherwise, if $x_{p}=x_{2}$, then we just need to exchange the subscripts
$v_{p}$ and $v_{2}$, as desired. Next, suppose that $0\leq x_{2}<x_{p}\leq
x_{n}$ and $v_{2}v_{1}\notin E(T)$. Note that there exists an unique path $P$
between $v_{p}$ and $v_{2}$ in $T$ since $T$ is connected. If $v_{1}\notin
V(P)$, then a new signed graph $\Sigma^{\prime}$ can be obtained from $\Sigma$
by reversing the sign of the positive edge $v_{1}v_{2}$ and the negative edge
$v_{1}v_{p}$ whose negative edges also form a spanning tree such that
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2, a
contradiction. If $v_{1}\in V(P)$, it means that we can find another vertex
$v_{t}$ such that $P=v_{2}\cdots v_{t}v_{1}v_{p}$, then $p<t$ and $0\leq
x_{2}<x_{p}\leq x_{t}$ clearly. And so a new signed graph $\Sigma^{\prime}$
can be obtained from $\Sigma$ by reversing the sign of the positive edge
$v_{1}v_{2}$ and the negative edge $v_{1}v_{t}$ whose negative edges also form
a spanning tree such that
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2, a
contradiction.

######  Claim 4.

$x_{q}>0.$

It is nature when $q=n$. Next, suppose that $x_{q}=0$ and $q<n$. Then
$x_{1}=\cdots=x_{q}=0$ and
$\sum\limits_{i=q+1}^{n}x_{i}=\lambda_{1}(A(\Sigma))x_{1}=0$, it means
$X=\textbf{0}$, a contradiction.

######  Claim 5.

$x_{i}>x_{1}\geq 0$ for $i\geq 2$.

We only need to prove $x_{2}>x_{1}$. Otherwise, we first revers the sign of
the positive edge $v_{2}v_{q}$ and the negative edge $v_{1}v_{q}$, and then
exchange the subscripts $v_{1}$ and $v_{2}$, the new signed graph is denoted
by $\Sigma^{\prime}$ whose negative edges also form a spanning tree, but
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2, a
contradiction.

######  Claim 6.

The subscripts of the neighbourhoods of $v_{1}$ in $T$ must be continuous.

Otherwise, let $t$ be the minimum subscript such that $v_{t}v_{1}\notin E(T)$
and $2<t<q$. If $x_{t}=x_{q}$, then we just need to exchange the subscripts
$v_{q}$ and $v_{t}$, as desired. Next, let $0\leq x_{t}<x_{q}$. Since $T$ is
connected, there exists an unique path $P$ between $v_{q}$ and $v_{t}$ in $T$.
We first notice that $v_{2}\in V(P)$ and $v_{1}\notin V(P)$ is impossible,
otherwise, there exists a cycle which contains $v_{1},v_{2},v_{q}$ in $T$, a
contradiction. If $\\{v_{1},v_{2}\\}\nsubseteq V(P)$, then a new signed graph
$\Sigma^{\prime}$ can be obtained from $\Sigma$ by reversing the sign of the
positive edge $v_{1}v_{t}$ and the negative edge $v_{1}v_{q}$ whose negative
edges also form a spanning tree such that
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2, a
contradiction. If $\\{v_{1},v_{2}\\}\subset V(P)$ and $v_{2}v_{t}\in E(T)$,
then a new signed graph $\Sigma^{\prime}$ can be obtained from $\Sigma$ by
reversing the sign of the positive edge $v_{1}v_{t}$ and the negative edge
$v_{2}v_{t}$ whose negative edges also form a spanning tree such that
$\lambda_{1}(A(\Sigma))<\lambda_{n}(A(\Sigma^{\prime}))$ by Lemma 2 and Claim
5, a contradiction. Assume that $\\{v_{1},v_{2}\\}\subset V(P)$ but
$v_{2}v_{t}\notin E(T)$, this means that we can find a vertex $v_{s}$ such
that $v_{2}v_{s}\in E(T)$, so $t<s$. Then a new signed graph $\Sigma^{\prime}$
can be obtained from $\Sigma$ by reversing the sign of the positive edge
$v_{1}v_{t}$ and the negative edge $v_{2}v_{s}$ whose negative edges also form
a spanning tree such that
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2 and Claim
5, a contradiction. Now, there is only one case, i.e., $v_{2}\notin V(P)$ and
$v_{1}\in V(P)$, it means that there is a vertex $v_{s}$ such that
$v_{s}v_{1}\in E(T)$ and $v_{s}\in V(P)$. Thus, $s>2$. If $v_{t}v_{s}\in
E(T)$, then a new signed graph $\Sigma^{\prime}$ can be obtained from $\Sigma$
by reversing the sign of the positive edge $v_{1}v_{t}$ and the negative edge
$v_{s}v_{t}$ whose negative edges also form a spanning tree such that
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2 and Claim
5, a contradiction. If $v_{t}v_{s}\notin E(T)$, then there is a vertex $v_{r}$
such that $v_{r}v_{s}\in E(T)$ and $v_{r}\in V(P)$, and so $r>t$. Then a new
signed graph $\Sigma^{\prime}$ can be obtained from $\Sigma$ by reversing the
sign of the positive edge $v_{1}v_{t}$ and the negative edge $v_{s}v_{r}$
whose negative edges also form a spanning tree such that
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2 and Claim
5, a contradiction.

######  Claim 7.

$q=n-1$.

Otherwise, we consider the vertex $v_{q+1}$ and $q+1\leq n-1$ since $d(T)\geq
3$. Let $P$ be the path of $T$ between $v_{1}$ and $v_{q+1}$, then there must
exist a vertex $v_{s}\in N_{T}(v_{1})$ such that $v_{s}\in V(P)$. If
$v_{s}v_{q+1}\in E(T)$, then a new signed graph $\Sigma^{\prime}$ can be
obtained from $\Sigma$ by reversing the sign of the positive edge
$v_{1}v_{q+1}$ and the negative edge $v_{s}v_{q+1}$ whose negative edges also
form a spanning tree such that
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2 and Claim
5, a contradiction. If $v_{s}v_{q+1}\notin E(T)$, then there exists another
vertex $v_{r}\in N_{T}(v_{s})$ such that $v_{r}\in V(P)$, and $r>q+1$
obviously. Then a new signed graph $\Sigma^{\prime}$ can be obtained from
$\Sigma$ by reversing the sign of the positive edge $v_{1}v_{q+1}$ and the
negative edge $v_{s}v_{r}$ whose negative edges also form a spanning tree such
that $\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2 and
Claim 5, a contradiction.

######  Claim 8.

$v_{2}v_{n}\in E(T)$.

Otherwise, suppose that $v_{s}v_{n}\in E(T)$ and $s>2$, then a new signed
graph $\Sigma^{\prime}$ can be obtained from $\Sigma$ by reversing the sign of
the positive edge $v_{2}v_{n}$ and the negative edge $v_{s}v_{n}$ whose
negative edges also form a spanning tree such that
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2, a
contradiction.

By Claims 2-8, $T\cong T_{1,n-3}$ immediately. Note that $-X$ must be an
eigenvector of $\Sigma$ if $X$ is an eigenvector. Thus the case that $X$ is a
nonpositive eigenvector is not considered independently.

$\underline{\mbox{Case 2. }}$ $X$ is neither nonpositive nor nonnegative. Let
$V_{+}=\\{v_{i}|x_{v_{i}}\geq 0\\}$ and $V_{-}=\\{v_{i}|x_{v_{i}}<0\\}$.
Clearly, $V_{+},V_{-}\neq\emptyset$ and there must exist a vertex $v$ such
that $x_{v}>0$. Let $\mid V_{+}\mid=a$, $\mid V_{-}\mid=b$ and
$x_{1}\leq\ldots\leq x_{b}<0\leq x_{b+1}\leq\ldots\leq x_{n}$. For
convenience, set $u_{i}=v_{n-(i-1)}$ and $y_{i}=x_{n-(i-1)}$ for $1\leq i\leq
a$, then $x_{1}\leq\ldots\leq x_{b}<0\leq y_{a}\leq\ldots\leq y_{1}$ and
$y_{1}>0$.

$\underline{\mbox{Subcase 2.1. }}$ $a\geq 2$ and $b\geq 2$.

######  Claim 9.

$V_{+}$ and $V_{-}$ are independent sets in $T$.

Without loss of generality, we only consider $V_{+}$. Assume the contrary,
there must exist three vertices $v_{r},$ $u_{s}$ and $u_{t}$ such that
$\\{v_{r}u_{s},u_{s}u_{t}\\}\subset E(T)$. Then a new signed graph
$\Sigma^{\prime}$ can be obtained from $\Sigma$ by reversing the sign of the
positive edge $v_{r}u_{t}$ and the negative edge $u_{s}u_{t}$ whose negative
edges also form a spanning tree such that
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2, a
contradiction.

######  Claim 10.

$u_{1}v_{1}\in E(T)$.

Otherwise, let $u_{1}v_{s}\in E(T)$ but $s>1$. If $x_{1}=x_{s}$, then we just
need to exchange the subscripts $v_{1}$ and $v_{s}$, as desired. If
$x_{1}<x_{s}<0$, then a new signed graph $\Sigma^{\prime}$ can be obtained
from $\Sigma$ by reversing the sign of the positive edge $v_{1}u_{1}$ and the
negative edge $v_{s}u_{1}$ whose negative edges also form a spanning tree such
that $\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2, a
contradiction.

######  Claim 11.

$u_{1}v_{i}\in E(T)$ for all $1\leq i\leq b$.

Assume the contrary, let $u_{1}v_{t}\notin E(T)$, $t>1$ clearly. Then there
must be a vertex $u_{s}$ and a path $P$ between $u_{1}$ and $v_{t}$ in $T$
such that $u_{s}v_{t}\in E(P)$. We construct a new signed graph
$\Sigma^{\prime}$ from $\Sigma$ by reversing the sign of the positive edge
$u_{1}v_{t}$ and the negative edge $u_{s}v_{t}$ whose negative edges also form
a spanning tree such that
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2, a
contradiction.

Let $W=N_{T}(V_{+}\setminus\\{u_{1}\\})=\\{v_{1},\ldots,v_{s}\\}$ for $1\leq
s\leq b$. By Claim 11, we have every vertex in $V_{+}\setminus\\{u_{1}\\}$ is
adjacent to just one vertex in $W$ and $x_{1}=\cdots=x_{s}$ by Lemma 2.
Without loss of generality, let $d_{T}(v_{1})\geq\cdots\geq d_{T}(v_{s})$. For
any $1\leq i<j\leq s$, let $\\{u_{k}v_{i},u_{l}v_{j}\\}\subset E(T)$. Set
$\lambda_{1}=\lambda_{1}(A(\Sigma))$, by characteristic equation we get

$\left\\{\begin{array}[]{ll}(\lambda_{1}+1)(x_{i}-x_{j})=2(\sum\limits_{w\in
N_{T}(v_{j})\setminus\\{u_{1}\\}}y_{w}-\sum\limits_{w\in
N_{T}(v_{i})\setminus\\{u_{1}\\}}y_{w}),\\\
(\lambda_{1}+1)(y_{k}-y_{l})=2(x_{j}-x_{i}).\end{array}\right.$

Obviously, $\sum\limits_{w\in
N_{T}(v_{j})\setminus\\{u_{1}\\}}y_{w}=\sum\limits_{w\in
N_{T}(v_{i})\setminus\\{u_{1}\\}}y_{w}$ and $y_{k}=y_{l}$ since $x_{i}=x_{j}$.
Thus, $y_{2}=\cdots=y_{a}$ and $d_{T}(v_{1})=\cdots=d_{T}(v_{s}).$

If $s=1$, then $T\cong T_{a-1,b-1}$, but
$\lambda_{1}(A((K_{n},T^{-}_{a-1,b-1})))\leq\lambda_{1}(A((K_{n},T^{-}_{1,n-3})))$
with equality if and only if one of $a$ and $b$ equals to 2 by Remark 1, and
we are done. We assume $s\geq 2$ following. If $y_{2}=\cdots=y_{a}>0$, then we
can construct a new signed graph $\Sigma^{\prime}$ from $\Sigma$ by reversing
the sign of the positive edge $v_{1}w$ and the negative edge $v_{i}w$ whose
negative edges also form a spanning tree, where $2\leq i\leq s$ and $w\in
N_{T}(v_{i})$, such that
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2, a
contradiction. If $y_{2}=0$. Note that $y_{1}>0.$ By characteristic equation,
we have

$\left\\{\begin{array}[]{ll}\lambda_{1}y_{1}=-\sum\limits_{i=1}^{b}x_{i},\\\
y_{1}=x_{j}-\sum\limits_{i=1,i\neq j}^{b}x_{i},\\\
\lambda_{1}x_{j}=-y_{1}+\sum\limits_{i=1,i\neq j}^{b}x_{i},\end{array}\right.$

by the above equations, we have

$\lambda_{1}^{2}-2\lambda_{1}-3=0,$

thus $\lambda_{1}=3$. However, $3<\lambda_{1}(A((K_{n},T^{-}_{1,n-3})))$ for
$n\geq 6$ by Remark 1, a contradiction. Thus, $T\cong T_{1,n-3}$.

$\underline{\mbox{Subcase 2.2. }}$ $a=1$ or $b=1$. If $a=1$, then
$u_{1}v_{1}\in E(T)$ by using a similar discussion as Claim 10 firstly. Since
$T\ncong K_{1,n-1}$, there exists at least one vertex which is not adjacent to
$u_{1}$. Let $U=V^{-}\setminus N_{T}(u_{1})$. If $\mid U\mid\geq 2$, then
there are two vertices $v\in N_{T}(u_{1})$ and $w\in U$ such that $vw\in
E(T)$. And we can construct a new signed graph $\Sigma^{\prime}$ from $\Sigma$
by reversing the sign of the positive edge $u_{1}w$ and the negative edge $vw$
whose negative edges also form a spanning tree, but
$\lambda_{1}(A(\Sigma))<\lambda_{1}(A(\Sigma^{\prime}))$ by Lemma 2, a
contradiction. Thus, $\mid U\mid=1$. By similar discussion with Claim 8, we
have $v_{2}v_{n}\in E(T)$, that is, $T\cong T_{1,n-3}$. $b=1$ is similar. This
completes the proof. ∎

##  3 Proof of Theorem 2

We first give the following result about $\lambda_{n}(A(\Sigma))$, which are
the most used tools in the identifications of graphs with minimum least
eigenvalue.

######  Lemma 3.

Let $r,s,t$ and $u$ be distinct vertices of a signed graph $\Sigma$,
$X=(x_{1},x_{2},\ldots,x_{n})^{T}$ be an unit eigenvector corresponding to
$\lambda_{n}(A(\Sigma))$. Then

  1. (i)

let $\Sigma^{\prime}$ be obtained from $\Sigma$ by reversing the sign of the
positive edge $rs$ and the negative edge $rt$. If $x_{r}(x_{s}-x_{t})\geq 0$,
then $\lambda_{n}(A(\Sigma))\geq\lambda_{n}(A(\Sigma^{\prime}))$. If
$x_{r}\neq 0$ or $x_{s}\neq x_{t}$, then
$\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$;

  2. (ii)

let $\Sigma^{\prime}$ be obtained from $\Sigma$ by reversing the sign of the
positive edge $rs$ and the negative edge $tu$. If $x_{r}x_{s}\geq x_{t}x_{u}$,
then $\lambda_{n}(A(\Sigma))\geq\lambda_{n}(A(\Sigma^{\prime}))$. If at least
one of the entries $x_{r},x_{s},x_{t},x_{u}$ is distinct from zero, then
$\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$.

######  Proof.

(i) Firstly, we have

$\displaystyle\lambda_{n}(A(\Sigma))-\lambda_{n}(A(\Sigma^{\prime}))$
$\displaystyle\geq X^{T}(A(\Sigma)-A(\Sigma^{\prime}))X$
$\displaystyle=4x_{r}(x_{s}-x_{t})$ $\displaystyle\geq 0.$

If $\lambda_{n}(A(\Sigma))=\lambda_{n}(A(\Sigma^{\prime}))$, then $X$ is also
an eigenvector of $A(\Sigma^{\prime})$ corresponding to
$\lambda_{n}(A(\Sigma^{\prime}))$. If $x_{r}\neq 0$ (resp. $x_{s}\neq x_{t}$),
then the eigenvalue equation cannot hold for $s$ (resp. $r$) in both signed
graphs, and we are done.

(ii)

$\displaystyle\lambda_{n}(A(\Sigma))-\lambda_{n}(A(\Sigma^{\prime}))$
$\displaystyle\geq X^{T}(A(\Sigma)-A(\Sigma^{\prime}))X$
$\displaystyle=4(x_{r}x_{s}-x_{t}x_{u})$ $\displaystyle\geq 0.$

If $\lambda_{n}(A(\Sigma))=\lambda_{n}(A(\Sigma^{\prime}))$, then $X$ is also
an eigenvector of $A(\Sigma^{\prime})$ corresponding to
$\lambda_{n}(A(\Sigma^{\prime}))$. Without loss of generality, if $x_{r}\neq
0$, then the eigenvalue equation cannot hold for $s$ in both signed graphs,
and we are done. ∎

$G[S]$ denotes the subgraph of $G$ induced by $S$, where $S\subset V(G)$.

######  Lemma 4.

Let $\Sigma$ be an unbalanced signed complete graphs with order $n$ whose
negative edges form a spanning tree $T$ and minimizes the
$\lambda_{n}(A(\Sigma))$, then the negative edges form $T_{1,n-3}$ or
$\mathcal{T}_{a-1,b-1}$, where $a+b=n$.

######  Proof.

Let $X=(x_{1},x_{2},\ldots,x_{n})^{T}$ be an unit eigenvector corresponding to
$\lambda_{n}(A(\Sigma))$. Since $\Sigma$ is an unbalanced signed complete
graphs, $T\ncong K_{1,n-1}$ and $d(T)>2$. And
$\lambda_{n}(A(\Sigma))\leq\lambda_{n}(A((K_{4},P^{-}_{4})))<-2$ by Lemma 7.
By arranging the vertices of $\Sigma$ appropriately, we can assume that
$V(\Sigma)=\\{v_{1},v_{2},\ldots,v_{n}\\}$ such that $x_{1}\leq
x_{2}\leq\cdots\leq x_{n}$.

$\underline{\mbox{Case 1. }}$ $X$ is a nonnegative eigenvector. Obviously,
$x_{n}>0$ since $X\neq\mathbf{0}$.

######  Claim 12.

$d_{T}(v_{n})\geq 2$.

Otherwise, suppose that $v_{t}v_{n}\in E(T)$, then $d_{T}(v_{t})\geq 2$ since
$d(T)\geq 3$. If $x_{t}=x_{n}$, then we just need to exchange the subscripts
$v_{t}$ and $v_{n}$, as desired. If $x_{t}<x_{n}$, then we can construct a new
signed graph $\Sigma^{\prime}$ by reversing the sign of the positive edge
$v_{n}w$ and the negative edge $v_{t}w$ for any $w\in
N_{T}(v_{t})\setminus\\{v_{n}\\}$ whose negative edges also form a spanning
tree such that $\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$ by
Lemma 3, a contradiction.

Let $x_{p}=\mbox{min}_{w\in N_{T}(v_{n})}x_{w}$, $x_{q}=\mbox{max}_{w\in
N_{T}(v_{n})}x_{w}$.

######  Claim 13.

$q=n-1.$

Otherwise, if $x_{q}=x_{n-1}$, then we just need to exchange the subscripts
$v_{q}$ and $v_{n-1}$, as desired. Next, let $0\leq x_{q}<x_{n-1}\leq x_{n}$
and $v_{n-1}v_{n}\notin E(T)$. Note that there exists an unique path $P$
between $v_{q}$ and $v_{n-1}$ in $T$. If $v_{n}\notin V(P)$, then a new signed
graph $\Sigma^{\prime}$ can be obtained from $\Sigma$ by reversing the sign of
the positive edge $v_{n-1}v_{n}$ and the negative edge $v_{q}v_{n}$ whose
negative edges also form a spanning tree such that
$\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$ by Lemma 3, a
contradiction. If $v_{n}\in V(P)$, it means that we can find another vertex
$v_{t}$ such that $P=v_{n-1}\cdots v_{t}v_{n}v_{q}$, thus $t<q<n-1$ and $0\leq
x_{t}\leq x_{q}<x_{n-1}\leq x_{n}$ clearly. Then a new signed graph
$\Sigma^{\prime}$ can be obtained from $\Sigma$ by reversing the sign of the
positive edge $v_{n-1}v_{n}$ and the negative edge $v_{t}v_{n}$ whose negative
edges also form a spanning tree such that
$\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$ by Lemma 3, a
contradiction.

######  Claim 14.

The subscripts of the neighbourhoods of $v_{n}$ in $T$ must be continuous.

Otherwise, suppose that $t$ is the maximum subscript such that
$v_{t}v_{n}\notin E(T)$ and $p<t<n-1$. If $x_{t}=x_{p}$, then we just need to
exchange the subscripts $v_{p}$ and $v_{t}$, as desired. Next, let $0\leq
x_{p}<x_{t}\leq x_{n-1}\leq x_{n}$. Since $T$ is connected, there exists an
unique path $P$ between $v_{p}$ and $v_{t}$ in $T$. We first notice that
$v_{n-1}\in V(P)$ and $v_{n}\notin V(P)$ is impossible, otherwise, there
exists a cycle which contains $v_{p},v_{n-1},v_{n}$ in $T$, a contradiction.
If $\\{v_{n-1},v_{n}\\}\nsubseteq V(P)$, then a new signed graph
$\Sigma^{\prime}$ can be obtained from $\Sigma$ by reversing the sign of the
positive edge $v_{t}v_{n}$ and the negative edge $v_{p}v_{n}$ whose negative
edges also form a spanning tree such that
$\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$ by Lemma 3, a
contradiction. If $\\{v_{n-1},v_{n}\\}\subset V(P)$ and $v_{t}v_{n-1}\in
E(T)$, then a new signed graph $\Sigma^{\prime}$ can be obtained from $\Sigma$
by reversing the sign of the positive edge $v_{t}v_{n}$ and the negative edge
$v_{t}v_{n-1}$ whose negative edges also form a spanning tree such that
$\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$ by Lemma 3, a
contradiction. Suppose that $\\{v_{n-1},v_{n}\\}\subset V(P)$ but
$v_{t}v_{n-1}\notin E(T)$, this means we can find a vertex $v_{s}$ such that
$v_{s}v_{n-1}\in E(T)$, so $s<p$. Then a new signed graph $\Sigma^{\prime}$
can be obtained from $\Sigma$ by reversing the sign of the positive edge
$v_{t}v_{n}$ and the negative edge $v_{s}v_{n-1}$ whose negative edges also
form a spanning tree such that
$\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$ by Lemma 3, a
contradiction.

Now, there is only one case, i.e., $v_{n-1}\notin V(P)$ and $v_{n}\in V(P)$,
it means that there is a vertex $v_{s}$ such that $v_{s}v_{n}\in E(T)$ and
$v_{s}\in V(P)$. If $v_{t}v_{s}\in E(T)$, then a new signed graph
$\Sigma^{\prime}$ can be obtained from $\Sigma$ by reversing the sign of the
positive edge $v_{t}v_{n}$ and the negative edge $v_{s}v_{n}$ whose negative
edges also form a spanning tree such that
$\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$ by Lemma 3, a
contradiction. If $v_{t}v_{s}\notin E(T)$, then there is a vertex $v_{r}$ such
that $v_{r}v_{s}\in E(T)$ and $v_{r}\in V(P)$, and so $r<p$. Then a new signed
graph $\Sigma^{\prime}$ can be obtained from $\Sigma$ by reversing the sign of
the positive edge $v_{t}v_{n}$ and the negative edge $v_{r}v_{n}$ whose
negative edges also form a spanning tree such that
$\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$ by Lemma 3, a
contradiction.

######  Claim 15.

$x_{1}>0$ and $p=2$.

Since $d(T)>2$, $d_{T}(v_{n})\leq n-2$. Let $x_{1}=0$. If there exists a
vertex $v_{t}$ such that $x_{t}>0$ and $t<p$, then we can find a vertex
$v_{s}\in N_{T}(v_{n})$ such that $v_{s}$ belongs to the unique path $P$
between $v_{t}$ and $v_{n}$. If $v_{t}v_{s}\in E(T)$, then a new signed graph
$\Sigma^{\prime}$ can be obtained from $\Sigma$ by reversing the sign of the
positive edge $v_{t}v_{n}$ and the negative edge $v_{t}v_{s}$ whose negative
edges also form a spanning tree such that
$\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$ by Lemma 3, a
contradiction. If $v_{t}v_{s}\notin E(T)$, then there exists a vertex
$v_{r}\in V(P)$ such that $v_{r}v_{t}\in E(T)$ and a new signed graph
$\Sigma^{\prime}$ can be obtained from $\Sigma$ by reversing the sign of the
positive edge $v_{t}v_{n}$ and the negative edge $v_{t}v_{r}$ whose negative
edges also form a spanning tree such that
$\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$ by Lemma 3, a
contradiction. Thus, $v_{i}\in N_{T}(v_{n})$ if $x_{i}>0$.

Let $s<t<n$ and $x_{s}=0<x_{t}\leq x_{n}$, then

$\lambda_{n}(A(\Sigma))x_{s}=\sum\limits_{i=p,i\neq t}^{n}x_{i}-x_{t},$

it leads to $x_{t}=\sum\limits_{i=p,i\neq t}^{n}x_{i}$. And
$\lambda_{n}(A(\Sigma))x_{n}=-\sum\limits_{i=p}^{n}x_{i}=-2x_{t}$, thus
$x_{t}>x_{n}$ since $\lambda_{n}(A(\Sigma))<-2$, it is impossible. Therefore,
$x_{1}>0$ and $p=2$.

######  Claim 16.

$v_{1}v_{n-1}\in E(T)$.

Otherwise, suppose that $v_{1}v_{s}\in E(T)$ and $s<n-1$, then a new signed
graph $\Sigma^{\prime}$ can be obtained from $\Sigma$ by reversing the sign of
the positive edge $v_{1}v_{n-1}$ and the negative edge $v_{1}v_{s}$ whose
negative edges also form a spanning tree such that
$\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$ by Lemma 3, a
contradiction.

Obviously, $T\cong T_{1,n-3}$ by the above claims. The proof of Case 1 also
shows that $X>0$ if $X$ nonnegative. And we know that $-X$ must be an
eigenvector of $\Sigma$ if $X$ is an eigenvector. Thus the case that $X$ is a
nonpositive eigenvector is not considered independently.

$\underline{\mbox{Case 2. }}$ $X$ is neither nonpositive nor nonnegative. Let
$V_{+}=\\{v_{i}|x_{v_{i}}\geq 0\\}$ and $V_{-}=\\{v_{i}|x_{v_{i}}<0\\}$.
Clearly, $V_{+},V_{-}\neq\emptyset$ and there must exist a vertex $v$ such
that $x_{v}>0$. Let $\mid V_{+}\mid=a$, $\mid V_{-}\mid=b$ and
$x_{1}\leq\ldots\leq x_{b}<0\leq x_{b+1}\leq\ldots\leq x_{n}$. For
convenience, set $u_{i}=v_{n-(i-1)}$ and $y_{i}=x_{n-(i-1)}$ for $1\leq i\leq
a$, then $x_{1}\leq\ldots\leq x_{b}<0\leq y_{a}\leq\ldots\leq y_{1}$.

######  Claim 17.

There exists an unique one negative edge $e=u_{a}v_{b}$ between $V_{+}$ and
$V_{-}$.

Otherwise, let $e_{1}=u_{s}v_{k}$ and $e_{2}=u_{t}v_{l}$ be two negative edges
between $V_{+}$ and $V_{-}$. If $e_{1}\cap e_{2}\neq\emptyset$, without loss
of generality, let $u_{s}=e_{1}\cap e_{2}$, then constructing a new signed
graph $\Sigma^{\prime}$ from $\Sigma$ by reversing the sign of the positive
edge $v_{k}v_{l}$ and the negative edge $u_{s}v_{k}$ whose negative edges also
form a spanning tree, and
$\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$ by Lemma 3, a
contradiction. Let $e_{1}\cap e_{2}=\emptyset$ next. Since there is only one
path containing the four vertices, we can find two of them as the end vertices
of the path. Without loss of generality, let $v_{k},v_{l}$ be the vertices we
found, and $v_{k}v_{l}\notin E(T)$, then constructing a new signed graph
$\Sigma^{\prime}$ from $\Sigma$ by reversing the sign of the positive edge
$v_{k}v_{l}$ and the negative edge $u_{s}v_{k}$ whose negative edges also form
a spanning tree, and $\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$
by Lemma 3, a contradiction. Thus, there exists only one negative edge
$e=u_{s}v_{t}$ between $V_{+}$ and $V_{-}$. Suppose that $s=a$ but $t\neq b$.
If $x_{t}=x_{b}$, we just need to exchange the subscripts $v_{t}$ and $v_{b}$,
as desired. If $x_{t}<x_{b}$, then constructing a new signed graph
$\Sigma^{\prime}$ from $\Sigma$ by reversing the sign of the positive edge
$u_{a}v_{b}$ and the negative edge $u_{a}v_{t}$ whose negative edges also form
a spanning tree, and $\lambda_{n}(A(\Sigma))>\lambda_{n}(A(\Sigma^{\prime}))$
by Lemma 3, a contradiction. We can get the similar contradictions when $s\neq
a$ but $t=b$ or $s\neq a$ and $t\neq b$ by Lemma 3. And we are done.

By the similar discussion as Case 1 on $V_{+}$ and $V_{-}$, the following
claim holds immediately.

######  Claim 18.

$T[V_{+}]=K_{1,a-1}$ with $d_{T}(u_{1})=a-1$ and $T[V_{1}]=K_{1,b-1}$ with
$d_{T}(v_{b})=b-1$.

By Claims 17 and 18, $T\cong T_{1,n-3}$ if $a=1$ or $b=1$ and
$T\cong\mathcal{T}_{a-1,b-1}$ if $a,b\geq 2$. This completes the proof. ∎

######  Lemma 5.

Let $\Sigma=(K_{n},\mathcal{T}^{-}_{a-1,b-1})$ with order $n=a+b\geq 6$, where
$2\leq b\leq\lfloor\frac{n}{2}\rfloor$. Then

$\displaystyle P_{D^{\pm}(\Sigma)}(\lambda)$
$\displaystyle=(\lambda+1)^{n-6}(\lambda-1)({\lambda}^{5}+\left(9-n\right){\lambda}^{4}+\left(34-6\,n\right){\lambda}^{3}$
$\displaystyle+\left(8\,ab-24\,n+58\right){\lambda}^{2}+\left(16\,ab-26\,n-3\right)\lambda-24\,ab+89\,n-323).$

Furthermore, if $a=\lceil\frac{n}{2}\rceil$ and $b=\lfloor\frac{n}{2}\rfloor$,
then $\lambda_{n}(A(\Sigma))>2-n$ for $n\geq 6$ and
$\lambda_{n}(A(\Sigma))<-4$ for $n\geq 8$.

######  Proof.

$D^{\pm}(\Sigma)=\left(\begin{array}[]{cccccc}0&\mathbf{1}_{a-2}&-1&-1&\mathbf{1}_{b-2}&1\\\
\mathbf{1}^{T}_{a-2}&J_{a-2}-I_{a-2}&-\mathbf{1}^{T}_{a-2}&\mathbf{1}^{T}_{a-2}&J_{(a-2)\times(b-2)}&\mathbf{1}^{T}_{a-2}\\\
-1&-\mathbf{1}_{a-2}&0&1&\mathbf{1}_{b-2}&1\\\
-1&\mathbf{1}_{a-2}&1&0&\mathbf{1}_{b-2}&-1\\\
\mathbf{1}^{T}_{b-2}&J_{(b-2)\times(a-2)}&\mathbf{1}^{T}_{b-2}&\mathbf{1}^{T}_{b-2}&J_{b-2}-I_{b-2}&-\mathbf{1}^{T}_{b-2}\\\
1&\mathbf{1}_{a-2}&1&-1&-\mathbf{1}_{b-2}&0\\\ \end{array}\right),$

then $det(\lambda
I-D^{\pm}(\Sigma))=(\lambda+1)^{n-6}(\lambda-1)f_{a,b}(\lambda)$, where
$f_{a,b}(\lambda)={\lambda}^{5}+\left(7-n\right){\lambda}^{4}+\left(22-6\,n\right){\lambda}^{3}\\\
+\left(8\,ab-16\,n+18\right){\lambda}^{2}+\left(16\,ab-10\,n-39\right)\lambda-24\,ab+65\,n-169.$
Set $\alpha=\lambda_{n}(A(\Sigma))$. Since $f_{a,b}(-3)=32n-160>0$ for $n\geq
6$, $\alpha<-3$. Note that
$f_{a+1,b-1}(\lambda)-f_{a,b}(\lambda)=-8\,\left(\lambda+3\right)\left(\lambda-1\right)\\\
\left(a-b+1\right)$, so $f_{a+1,b-1}(\alpha)-f_{a,b}(\alpha)<0$ for $n\geq 6$.
It follows that $\alpha$ decreases as $b$ increases. If $n$ is even, then
$\alpha$ is minimum when $a=b=\frac{n}{2}$ and
$f_{n/2,n/2}(\lambda)=h_{1}(\lambda)h_{2}(\lambda),$ where
$h_{1}(\lambda)={\lambda}^{2}+\left(6-n\right)\lambda-3\,n+13$ and
$h_{2}(\lambda)={\lambda}^{3}+{\lambda}^{2}+\left(3-2\,n\right)\lambda+2\,n-13.$
The least eigenvalue of $h_{1}(\lambda)$ is $n/2-3-1/2\,\sqrt{{n}^{2}-16}>-3$,
thus $\alpha$ must be the least eigenvalue of $h_{2}(\lambda)$. We also find
that $h_{2}(-4)=10n-73>0$ for $n\geq 8$. Thus, we have $\alpha<-4$ for $n\geq
8$. Note that $h_{2}(2-n)=-(n-5)(n^{2}-4n+1)<0$ obviously and
$h^{\prime}_{2}(\lambda)=3\lambda^{2}+2\lambda-2n+3$ with two stagnation point
$-\frac{1\pm\sqrt{6n-8}}{3}>2-n$, thus $\alpha>2-n$ for $n\geq 6$. If $n$ is
odd, then $a=\frac{n+1}{2}$ and $b=\frac{n-1}{2}$. Using the similar method,
we can also obtained $f_{a,b}(-4)=10n^{2}-23n-375>0$ for $n\geq 8$,
$f_{a,b}(2-n)=-(n-5)(n-3)(2n^{3}-17n^{2}+40n-9)<0$ and $f_{a,b}(\lambda)$ is
strictly monotone increasing when $\lambda<2-n$, thus the result is still
valid. ∎

######  Remark 19.

Since $\Sigma=(K_{n},T^{-}_{1,n-3})$ is unbalanced, $\lambda_{n}(A(\Sigma))$
must be an eigenvalue of $g(\lambda)$ by Remark 1. Note that
$g^{\prime}(\lambda)=\left(\lambda+1\right)\left(3\,\lambda-2\,n+3\right)$ and
$g^{\prime}(\lambda)>0$ when $\lambda<-1$, and so $g(\lambda)$ is strictly
monotone increasing when $\lambda<-1$. Combining this with $g(-4)=-n-51<0$,
thus $\lambda_{n}(A(\Sigma))>-4$. If $n=6,7$, we can get
$\lambda_{n}(A((K_{n},\mathcal{T}^{-}_{\lceil\frac{n}{2}\rceil-1,\lfloor\frac{n}{2}\rfloor-1})))<\lambda_{n}(A((K_{n},T^{-}_{1,n-3})))$
by simple calculation. If $n\geq 8$, then
$\lambda_{n}(A((K_{n},\mathcal{T}^{-}_{\lceil\frac{n}{2}\rceil-1,\lfloor\frac{n}{2}\rfloor-1})))<-4<\lambda_{n}(A((K_{n},T^{-}_{1,n-3})))$.

By Lemmas 4 and 5 and Remark 19, we can get the Theorem 2 immediately.

##  4 Proof of Theorem 4

For the sake of convenience, $\sigma_{ij}$ for short
$\sigma_{max}(v_{i},v_{j})$ and $\sigma^{\prime}_{ij}$ for short
$\sigma_{min}(v_{i},v_{j})$.

######  Lemma 6.

Let $\Sigma=(S^{+}_{2,n-2},\sigma)$ be a connected signed graph and $D^{max}$
and $D^{min}$ be its signed distance matrices. If all triangles have the same
sign, then $D^{max}(\Sigma)=D^{min}(\Sigma)=D^{\pm}(\Sigma)$ and

  1. (1)

$P_{D^{\pm}(\Sigma)}(\lambda)=(\lambda+2)^{n-5}\left({\lambda}^{2}+4\,\lambda+2\right)({\lambda}^{3}+(-2n+6)\,{\lambda}^{2}-(2n+6)\,\lambda+2n-20)$
when
$\sigma_{23}\sigma_{35}\sigma_{25}=1$ and
$\lambda_{n}(D^{\pm}((S^{+}_{2,n-2},\sigma)))=-2-\sqrt{2}$;

  2. (2)

$P_{D^{\pm}(\Sigma)}(\lambda)=(\lambda+2)^{n-5}\left({\lambda}^{2}-4\,\lambda-6\right))({\lambda}^{3}+(-2n+14)\,{\lambda}^{2}-(18n-8)\,\lambda+8n-100)$
when $\sigma_{23}\sigma_{35}\sigma_{25}=-1$ and
$\lambda_{n}(D^{\pm}((S^{+}_{2,n-2},\sigma)))=-2-\sqrt{2}$ if and only if
$\Sigma=(P_{4},\sigma)$.

###### Proof..

Let $V(S^{+}_{2,n-2})=\\{v_{1},v_{2},\ldots,v_{n}\\}$. Then $\Sigma$ is
compatible since all triangles have the same sign, i.e.,
$D^{max}(\Sigma)=D^{min}(\Sigma)=D^{\pm}(\Sigma)$ and

$D^{\pm}((S^{+}_{2,n-2},\sigma))=\left(\begin{array}[]{ccccccc}0&\sigma_{12}&2\sigma_{13}&3\sigma_{14}&2\sigma_{15}&\cdots&2\sigma_{1n}\\\
\sigma_{12}&0&\sigma_{23}&2\sigma_{24}&\sigma_{25}&\cdots&\sigma_{2n}\\\
2\sigma_{13}&\sigma_{23}&0&\sigma_{34}&\sigma_{35}&\cdots&\sigma_{3n}\\\
3\sigma_{14}&2\sigma_{24}&\sigma_{34}&0&2\sigma_{45}&\cdots&2\sigma_{4n}\\\
2\sigma_{15}&\sigma_{25}&\sigma_{35}&2\sigma_{45}&0&\cdots&2\sigma_{5n}\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ldots&\vdots\\\
2\sigma_{1n}&\sigma_{2n}&\sigma_{3n}&2\sigma_{4n}&2\sigma_{5n}&\cdots&0\\\
\end{array}\right).$

Note that $\sigma_{13}=\sigma_{12}\sigma_{23}$,
$\sigma_{14}=\sigma_{13}\sigma_{34}$ and
$\sigma_{25}\sigma_{35}\sigma_{2i}\sigma_{3i}=1$ for $6\leq i\leq n$. Then
$det(\lambda I-D^{\pm}(\Sigma))=(\lambda+2)^{n-5}f(\lambda)$, where

$f(\lambda)=\begin{vmatrix}\lambda&-1&-\sigma_{23}&-3\sigma_{23}&-2(n-4)\\\
-1&\lambda&-\sigma_{23}&-2\sigma_{23}&-(n-4)\\\
-2\sigma_{23}&-\sigma_{23}&\lambda&-1&-(n-4)\sigma_{35}\setminus\sigma_{25}\\\
-3\sigma_{23}&-2\sigma_{23}&-1&\lambda&-2(n-4)\sigma_{35}\setminus\sigma_{25}\\\
-2&-1&-\sigma_{35}\setminus\sigma_{25}&-2\sigma_{35}\setminus\sigma_{25}&\lambda-2(n-5)\end{vmatrix}.$

If $\sigma_{23}\sigma_{35}\sigma_{25}=1$, then
$f(\lambda)=(\lambda+2-\sqrt{2})(\lambda+2+\sqrt{2})f_{1}(\lambda)$, where
$f_{1}(\lambda)={\lambda}^{3}+(-2n+6)\,{\lambda}^{2}-(2n+6)\,\lambda+2n-20$.
Note that the least stagnation point of $f_{1}(\lambda)$ is
$\frac{2n-4-\sqrt{4n^{2}-18n+54}}{3}>-2-\sqrt{2}$ and $f_{1}(-2-\sqrt{2})<0$
for $n\geq 5$. Thus
$\lambda_{n}(D^{\pm}((S^{+}_{2,n-2},\sigma)))=-2-\sqrt{2}$. If
$\sigma_{23}\sigma_{35}\sigma_{25}=-1$, then
$f(\lambda)=(\lambda-2-\sqrt{10})(\lambda-2+\sqrt{10})f_{2}(\lambda)$, where
$f_{2}(\lambda)={\lambda}^{3}+(-2n+14)\,{\lambda}^{2}-(18n-8)\,\lambda+8n-100$.
Note that $f_{2}(-2-\sqrt{2})=(10n-40)\sqrt{2}+14n-56$ equals to zero if and
only if $n=4$. Then $\lambda_{n}(D^{\pm}((S^{+}_{2,n-2},\sigma)))=-2-\sqrt{2}$
if and only if $n=4$, that is, $\Sigma=(P_{4},\sigma)$. ∎

######  Lemma 7.

(Cauchy Interlace Theorem). Let $A$ be a Hermitian matrix with order $n$ and
let $B$ be a principal submatrix of $A$ with order $m$. If
$\lambda_{1}(A)\geq\lambda_{2}(A)\geq\cdots\geq\lambda_{n}(A)$ list the
eigenvalues of $A$ and $\mu_{1}(B)\geq\mu_{2}(B)\geq\cdots\geq\mu_{m}(B)$ list
the eigenvalues of $B$, then
$\lambda_{n-m+i}(A)\leq\mu_{i}(B)\leq\lambda_{i}(A)$ for $i=1,\ldots,m$.

###### Proof of Theorem 4..

(I). If $d=2$, then the result follows from (III) of Theorem 5. (II). Let
$d=3$. Since the least signed distance eigenvalues of a signed $P_{4}$ equal
to $-2-\sqrt{2}$, let’s assume that $n\geq 5$. Let
$V(P_{4})=\\{v_{1},v_{2},v_{3},v_{4}\\}$, then $A_{1}$ is the principal
submatrix of $D^{max}$ and $B_{1}$ is the principal submatrix of $D^{min}$
indexed by $V(P_{4})$ respectively, and both $\lambda_{4}(A_{1})$ and
$\lambda_{4}(B_{1})$ are less than or equal to $-2-\sqrt{2}$ besides the
matrices as follows

$A_{1}=\left(\begin{array}[]{cccc}0&1&2&3\\\ 1&0&-1&2\\\ 2&-1&0&1\\\
3&2&1&0\\\
\end{array}\right)~{}~{}~{}~{}B_{1}=\left(\begin{array}[]{cccc}0&1&-2&-3\\\
1&0&1&-2\\\ -2&1&0&1\\\ -3&-2&1&0\\\ \end{array}\right).$

$A_{1}$ shows that $\sigma_{12}=1$, $\sigma_{23}=-1$ but $\sigma_{13}=1$, it
means that there exists another vertex $u$ such that
$\\{uv_{1},uv_{3}\\}\subset E$ and $\sigma_{13}=1$. $B_{1}$ shows that
$\sigma^{\prime}_{12}=\sigma^{\prime}_{23}=1$ but $\sigma^{\prime}_{13}=-1$,
it means that there exists another vertex $w$ such that $wv_{1},wv_{3}\in E$
and $\sigma^{\prime}_{13}=-1$. However, the least eigenvalue of the principal
submatrix of $D^{max}$ (resp. $D^{min}$) indexed by $V(P_{4})\cup\\{u\\}$
(resp. $V(P_{4})\cup\\{w\\})$ is always less than $-2-\sqrt{2}$. Thus, both
$\lambda_{n}(D^{max})$ and $\lambda_{n}(D^{min})$ are less than or equal to
$-2-\sqrt{2}$ when $d=3$ by Lemma 7. Next, we consider the necessary and
sufficient condition of the equality. The sufficiency holds obviously by Lemma
6. Conversely, we can get the following claims.

######  Claim 20.

$u\in\cup_{i=1}^{4}N(v_{i})$ for any vertex $u\in V\setminus V(P_{4})$.

Otherwise, there exists a vertex $v_{5}$ such that $d_{i5}=2$ or $3$ for
$1\leq i\leq 4$ and $\mid\sigma_{ij}\mid=1$. Then $A_{2}$ and $B_{2}$ are
principle submatrices of $D^{max}$ and $D^{min}$ indexed by
$V(P_{4})\cup\\{v_{5}\\}$, respectively. For the entries of $A_{2}$, we must
note that $\sigma_{13}=1$ if $\sigma_{12}\sigma_{23}=1$, $\sigma_{24}=1$ if
$\sigma_{23}\sigma_{34}=1$ and $\sigma_{14}=1$ if
$\sigma_{12}\sigma_{23}\sigma_{34}=1$. We should also note the relationship
between the elements of $B_{2}$, $\sigma^{\prime}_{13}=-1$ if
$\sigma^{\prime}_{12}\sigma^{\prime}_{23}=-1$, $\sigma^{\prime}_{24}=-1$ if
$\sigma^{\prime}_{23}\sigma^{\prime}_{34}=-1$ and $\sigma^{\prime}_{14}=-1$ if
$\sigma^{\prime}_{12}\sigma^{\prime}_{23}\sigma^{\prime}_{34}=-1$. However,
calculated by Matlab, both $\lambda_{5}(A_{2})$ and $\lambda_{5}(B_{2})$ are
less than $-2-\sqrt{2}$, thus both $\lambda_{n}(D^{max})$ and
$\lambda_{n}(D^{min})$ are less than $-2-\sqrt{2}$ by Lemma 7, a
contradiction.

$A_{2}=\left(\begin{array}[]{ccccc}0&\sigma_{12}&2\sigma_{13}&3\sigma_{14}&\sigma_{15}d_{15}\\\
\sigma_{12}&0&\sigma_{23}&2\sigma_{24}&\sigma_{25}d_{25}\\\
2\sigma_{13}&\sigma_{23}&0&\sigma_{34}&\sigma_{35}d_{35}\\\
3\sigma_{14}&2\sigma_{24}&\sigma_{34}&0&\sigma_{45}d_{45}\\\
\sigma_{15}d_{15}&\sigma_{25}d_{25}&\sigma_{35}d_{35}&\sigma_{45}d_{45}&0\\\
\end{array}\right)$
$~{}~{}B_{2}=\left(\begin{array}[]{ccccc}0&\sigma^{\prime}_{12}&2\sigma^{\prime}_{13}&3\sigma^{\prime}_{14}&\sigma^{\prime}_{15}d_{15}\\\
\sigma^{\prime}_{12}&0&\sigma^{\prime}_{23}&2\sigma^{\prime}_{24}&\sigma^{\prime}_{25}d_{25}\\\
2\sigma^{\prime}_{13}&\sigma^{\prime}_{23}&0&\sigma^{\prime}_{34}&\sigma^{\prime}_{35}d_{35}\\\
3\sigma^{\prime}_{14}&2\sigma^{\prime}_{24}&\sigma^{\prime}_{34}&0&\sigma^{\prime}_{45}d_{45}\\\
\sigma^{\prime}_{15}d_{15}&\sigma^{\prime}_{25}d_{25}&\sigma^{\prime}_{35}d_{35}&\sigma^{\prime}_{45}d_{45}&0\\\
\end{array}\right)$

######  Claim 21.

$N(v_{i})\cap N(v_{2})\cap N(v_{3})=\emptyset$ for $i=1,4$.

By symmetry, we only need to prove that $N(v_{1})\cap N(v_{2})\cap
N(v_{3})=\emptyset$. If $(H_{3},\sigma)\subset\Sigma$, then the least
eigenvalues of the principal submatrices of $D^{max}$ and $D^{min}$ indexed by
$V(H_{3})$ are always less than $-2-\sqrt{2}$ besides $A_{3}$ and $B_{3}$,
respectively. From $A_{3}$ we find that $\sigma_{12}=1$, $\sigma_{23}=-1$ but
$\sigma_{13}=1$, it means that there exists another vertex $u$ such that
$\\{uv_{1},uv_{3}\\}\subset E$ and
$\sigma_{max}(uv_{1})\sigma_{max}(uv_{3})=1$. $B_{3}$ shows that
$\sigma^{\prime}_{12}=\sigma^{\prime}_{23}=1$ but $\sigma^{\prime}_{13}=-1$,
it means that there exists another vertex $w$ such that $wv_{1},wv_{3}\in E$
and $\sigma_{min}(wv_{1})\sigma_{min}(wv_{3})=-1$. However, the least
eigenvalue of the principal submatrix of $D^{max}$ (resp. $D^{min}$) indexed
by $V(H_{3})\cup\\{u\\}$ (resp. $V(H_{3})\cup\\{w\\}$) is always less than
$-2-\sqrt{2}$ through Matlab, thus both $\lambda_{n}(D^{max})$ and
$\lambda_{n}(D^{min})$ are less than $-2-\sqrt{2}$ by Lemma 7, a
contradiction.

$A_{3}=\left(\begin{array}[]{ccccc}0&1&2&3&1\\\ 1&0&-1&2&1\\\ 2&-1&0&1&-1\\\
3&2&1&0&2\\\ 1&1&-1&2&0\\\
\end{array}\right)~{}~{}B_{3}=\left(\begin{array}[]{ccccc}0&1&-2&-3&1\\\
1&0&1&-2&1\\\ -2&1&0&1&1\\\ -3&-2&1&0&-2\\\ 1&1&1&-2&0\\\ \end{array}\right)$

######  Claim 22.

$N(v_{1})\cap N(v_{3})=\emptyset$ and $N(v_{2})\cap N(v_{4})=\emptyset$

We assume that $N(v_{1})\cap N(v_{3})\neq\emptyset$, then
$(H_{2},\sigma)\subset\Sigma$ and the least eigenvalues of the principal
submatrices of $D^{max}$ and $D^{min}$ indexed by $V(H_{2})$ are always less
than $-2-\sqrt{2}$ besides $A_{4}$ and $B_{4}$, respectively. $A_{4}$
indicates $\sigma_{12}=1$, $\sigma_{23}=-1$ but $\sigma_{13}=1$, it means that
there exists another vertex $u$ such that $\\{uv_{1},uv_{3}\\}\subset E$ and
$\sigma_{max}(uv_{1})\sigma_{max}(uv_{3})=1$. And $B_{4}$ suggests
$\sigma^{\prime}_{12}\sigma^{\prime}_{23}=1$ but $\sigma^{\prime}_{13}=-1$, it
means that there exists another vertex $w$ such that $wv_{1},wv_{3}\in E$ and
$\sigma_{min}(wv_{1})\sigma_{min}(wv_{3})=-1$. Combining this with claim 21,
we can observe the least eigenvalue of the principal submatrix of $D^{max}$
(resp. $D^{min}$) indexed by $V(H_{2})\cup\\{u\\}$ (resp.
$V(H_{2})\cup\\{w\\}$) is always less than $-2-\sqrt{2}$ through Matlab, thus
both $\lambda_{n}(D^{max})$ and $\lambda_{n}(D^{min})$ are less than
$-2-\sqrt{2}$ by Lemma 7, a contradiction.

$A_{4}=\left(\begin{array}[]{ccccc}0&1&2&3&1\\\ 1&0&-1&2&2\\\ 2&-1&0&1&-1\\\
3&2&1&0&2\\\ 1&2&-1&2&0\\\
\end{array}\right)~{}~{}B_{4}=\left(\begin{array}[]{ccccc}0&1&-2&-3&1\\\
1&0&1&-2&2\\\ -2&1&0&1&1\\\ -3&-2&1&0&-2\\\ 1&2&1&-2&0\\\ \end{array}\right)$

Note that the least eigenvalue of the principal submatrices of $D^{max}$ (or
$D^{min}$) indexed by $V(H_{4})$ and $V(H_{8})$ are always less than
$-2-\sqrt{2}$, respectively. Thus, the following claim is obvious.

######  Claim 23.

$N(v_{1})=\\{v_{2}\\}$ and $N(v_{4})=\\{v_{3}\\}$.

######  Claim 24.

$N(v_{2})\setminus(N(v_{2})\cap N(v_{3}))=N(v_{3})\setminus(N(v_{2})\cap
N(v_{3}))=\emptyset$.

By symmetry, we only need to prove that $N(v_{2})\setminus(N(v_{2})\cap
N(v_{3}))=\emptyset$. If $(H_{7},\sigma)\subset\Sigma$, then the least
eigenvalues of the principal submatrices of $D^{max}$ and $D^{min}$ indexed by
$V(H_{7})$ are always less than $-2-\sqrt{2}$ besides $A_{5}$ and $B_{5}$,
respectively. By $A_{5}$ and $B_{5}$, we have $v_{3}v_{5}\notin E$ and
$d(v_{4},v_{5})=2$, then there is another vertex $u$ such that $uv_{4}\in E$
by Claims 20-22, but it contradicts to Claim 23.

$~{}~{}A_{5}=\left(\begin{array}[]{ccccc}0&1&2&3&2\\\ 1&0&-1&2&1\\\
2&-1&0&1&2\\\ 3&2&1&0&2\\\ 2&1&2&2&0\\\
\end{array}\right)~{}~{}B_{5}=\left(\begin{array}[]{ccccc}0&1&-2&-3&2\\\
1&0&1&-2&1\\\ -2&1&0&1&-2\\\ -3&-2&1&0&-2\\\ 2&1&-2&-2&0\\\
\end{array}\right)$

By Claims 20-24, we conclude that $u\in N(v_{2})\cap N(v_{3})$ for any vertex
$u\in V\setminus V(P_{4})$. If $\mid N(v_{2})\cap
N(v_{3})\mid=0~{}\mbox{or}~{}1$, then the result is follows. So let $\mid
N(v_{2})\cap N(v_{3})\mid\geq 2$ and $\\{u_{1},u_{2}\\}\subseteq N(v_{2})\cap
N(v_{3})$.

######  Claim 25.

  1. (1)

$u_{1}u_{2}\notin E$;

  2. (2)

$\sigma_{max}(u_{1}v_{2})\sigma_{max}(u_{1}v_{3})\sigma_{max}(u_{2}v_{2})\sigma_{max}(u_{2}v_{3})=1$;

  3. (3)

$\sigma_{min}(u_{1}v_{2})\sigma_{min}(u_{1}v_{3})\sigma_{min}(u_{2}v_{2})\sigma_{min}(u_{2}v_{3})=1$.

If $u_{1}u_{2}\in E$, then $(H_{5},\sigma)\subset\Sigma$ and the least
eigenvalues of the principal submatrices of $D^{max}$ and $D^{min}$ indexed by
$V(H_{5})$ are always less than $-2-\sqrt{2}$, a contradiction. If
$\sigma_{max}(u_{1}v_{2})\sigma_{max}(u_{1}v_{3})$=-$\sigma_{max}(u_{2}v_{2})\sigma_{max}(u_{2}v_{3})$,
then the least eigenvalues of the principal submatrices of $D^{max}$ and
$D^{min}$ indexed by $V(H_{6})$ are always less than $-2-\sqrt{2}$, a
contradiction. (3) is similar.

From Claim 25, we have $\Sigma$ is a signed graph with underly graph
$S^{+}_{2,n-2}$ such that all triangles with the same sign.

(III). Suppose that $d\geq 4$ and $P_{d+1}=v_{1}v_{2}\ldots v_{d+1}$ is a
diameter path of $\Sigma$ such that
$\sigma_{1,d+1}=\sigma_{1,d}\sigma_{d,d+1}$. Let
$X=(x_{1},x_{2},\ldots,x_{n})^{T}$ be an vector with $x_{i}$ corresponding to
$v_{i}$. Assume that $x_{1}=1$, $x_{d}=-\sigma_{1,d}$, and
$x_{d+1}=-\sigma_{1,d+1}$, then

$\displaystyle\lambda_{n}(D^{max})$
$\displaystyle\leq\frac{X^{T}D^{max}X}{X^{T}X}$
$\displaystyle=\frac{2}{3}(\sigma_{1d}(d-1)x_{1}x_{d}+\sigma_{1,d+1}dx_{1}x_{d+1}+\sigma_{d,d+1}x_{d}x_{d+1})$
$\displaystyle=-\frac{4}{3}(d-1).$

And this bound still holds for $D^{min}$ clearly. ∎

######  Remark 26.

Let $\Sigma$ is a balanced graph with diameter $d\geq 4$ and
$P_{d+1}=v_{1}v_{2}\ldots v_{d+1}$ is a diameter path of $\Sigma$ such that
$\sigma_{1,d+1}=\sigma_{1,d}\sigma_{d,d+1}$. Let
$X=(x_{1},x_{2},\ldots,x_{n})^{T}$ be an vector with $x_{i}$ corresponding to
$v_{i}$. Assume that $x_{1}=\sigma_{1,d}$, $x_{2}=\sigma_{2,d}$, $x_{d}=-1$,
and $x_{d+1}=-\sigma_{d,d+1}$, then

$\displaystyle\lambda_{n}(D^{max})$
$\displaystyle\leq\frac{X^{T}D^{max}X}{X^{T}X}$
$\displaystyle=\frac{1}{2}(-3d+4+\sigma_{1,2}\sigma_{1,d}\sigma_{2,d}-\sigma_{2,d+1}(d-1)\sigma_{2,d}\sigma_{d,d+1}).$

Note that the shortest paths of every two vertices have the same sign since
$\Sigma$ is balanced, thus $\sigma_{1,d}=\sigma_{1,2}\sigma_{2,d}$ and
$\sigma_{2,d+1}=\sigma_{2,d}\sigma_{d,d+1}$. Then
$\lambda_{n}(D^{max})\leq-2d+3.$ The conclusion still holds for $D^{min}$.

##  5 Conclusion remark

As usual, let $K_{n}$, $P_{n}$ and $K_{n_{1},n_{2},\cdots,n_{k}}$, where
$\sum\limits_{i=1}^{k}n_{i}=n$, denote the complete graph, the path and the
complete $k$-partite graph with order $n$, respectively. The girth of
$\Sigma=(G,\sigma)$, short for $g$, is the girth of its underlying graph $G$,
namely, the length of a shortest cycle in $G$. Let $D(G)=(d_{uv})_{n\times n}$
be the distance matrix of a connected graph $G$. Yu [15] investigated the
least distance eigenvalue of a graph, and determined all connected graphs with
$\lambda_{n}(D(G))\in[-2.383,0]$ among graphs with $n$ vertices. Lin, Hong,
Wang and Shu [10] extended the above result separately. The authors showed
that $\lambda_{n}(D(G))=-1$ if and only if $G\cong K_{n}$ and
$\lambda_{n}(D(G))=-2$ if and only if $G\cong K_{n_{1},\cdots,n_{k}}$. And
there does not exist a graph $G$ of order $n$ with $-2<\lambda_{n}(D(G))<-1$.
Motivated by the papers, we pose the following problem:

######  Problem 2.

Which connected signed graphs have the least eigenvalue of the signed distance
matrices belonging to $[-2,-1]$?

$P_{4}$$C_{5}$$H_{1}$$H_{2}$$H_{3}$$H_{4}$$H_{5}$$H_{6}$$H_{7}$$H_{8}$ Figure
2: The graphs $P_{4}$, $C_{5}$, $H_{1}$-$H_{8}$.

######  Remark 27.

If $(K_{n},\sigma)$ is unbalanced, then the shortest negative cycle must be
$(C_{3},\sigma)$. Otherwise, suppose that $(C_{k},\sigma)$ is a shortest
negative cycle of $(K_{n},\sigma)$ and $k\geq 4$. Let
$C_{k}=v_{1}v_{2}v_{3}v_{4}\ldots v_{k}v_{1}$. Note that $(K_{n},\sigma)$ is
compatible, thus $\sigma_{uv}=\sigma^{\prime}_{uv}$. If
$\sigma_{12}\sigma_{23}=-1$, then $\sigma_{13}=-1$, it implies that
$C_{k-2}=v_{1}v_{3}v_{4}\ldots v_{k}v_{1}$ is a negative cycles with length
$k-1$, a contradiction. If $\sigma_{12}\sigma_{23}=1$, then $\sigma_{14}=1$,
it implies that $C^{\prime}=v_{1}v_{3}v_{4}\ldots v_{k}v_{1}$ is also a
negative cycles with length $k-1$, a contradiction. And
$\lambda_{3}(D^{\pm}((K_{3},\sigma)))=-2$ when $\sigma(K_{3})=-1$.

######  Lemma 8.

[10]. Let $G$ be a connected graph and $D(G)$ be the distance matrix of $G$.
Then $\lambda_{n}(D(G))=-2$ with multiplicity $n-k$ if and only if $G$ is a
complete $k$-partite graph for $2\leq k\leq n-1$.

######  Lemma 9.

Let $\Sigma=(K_{n_{1},n_{2},\ldots,n_{k}},\sigma)$ be an unbalanced signed
completed $k$-partite graph, where $k\geq 3$. If $\Sigma$ satisfies the
following conditions:

  1. (i)

The paths of length two for any two nonadjacent vertices have the same sign;

  2. (ii)

$\sigma(K_{3})=-1$ for every $K_{3}\subset K_{n_{1},n_{2},\ldots,n_{k}},$

then

  1. (1)

$D^{max}(\Sigma)=D^{min}(\Sigma)=D^{\pm}(\Sigma)$, that is, $\Sigma$ is
compatible;

  2. (2)

$-2$ is an eigenvalue of $D^{\pm}(\Sigma)$ with multiplicity $n-k+1(i.e.,n-2)$
for $k=3$;

  3. (3)

$-2$ is an eigenvalue of $D^{\pm}(\Sigma)$ with multiplicity $n-k$ for $k\geq
4$.

###### Proof.

Let $V=V_{1}\cup V_{2}\cup\ldots\cup V_{k}$, where $V_{i}$ is an independent
set and $\mid V_{i}\mid=n_{i}$ for $1\leq i\leq k$. Since the diameter of
$\Sigma$ is 2, $\Sigma$ is compatible by (i) immediately. We partition $V_{i}$
to $v_{i1}$, $V_{i2}$ and $V_{i3}$ such that the paths of length two between
$v_{i1}$ and $u$ with positive sign, the paths of length two between $v_{i1}$
and $w$ with negative sign, where $u\in V_{i2}$ and $w\in V_{i3}$. Let $\mid
V_{i2}\mid=s_{i}$ for $1\leq i\leq k$ . Then

$D^{\pm}(\Sigma)=\left(\begin{array}[]{cccc}A_{n_{1}\times
n_{1}}&A_{n_{1}\times n_{2}}&\cdots&A_{n_{1}\times n_{k}}\\\
A^{T}_{n_{1}\times n_{2}}&A_{n_{2}\times n_{2}}&\cdots&A_{n_{2}\times
n_{k}}\\\ \vdots&\vdots&\ddots&\vdots\\\ A^{T}_{n_{1}\times
n_{k}}&A^{T}_{n_{2}\times n_{k}}&\cdots&A_{n_{k}\times n_{k}}\\\
\end{array}\right),$

where

$A_{n_{i}\times n_{i}}=\left(\begin{array}[]{ccc}0&2J_{1\times
s_{i}}&-2J_{1\times(n_{i}-s_{i}-1)}\\\ 2J_{s_{i}\times 1}&2(J_{s_{i}\times
s_{i}}-I_{s_{i}\times s_{i}})&-2J_{s_{i}\times(n_{i}-s_{i}-1)}\\\
-2J_{(n_{i}-s_{i}-1)\times 1}&-2J_{(n_{i}-s_{i}-1)\times
s_{i}}&2(J_{(n_{i}-s_{i}-1)\times(n_{i}-s_{i}-1)}-I_{(n_{i}-s_{i}-1)\times(n_{i}-s_{i}-1)})\\\
\end{array}\right)$

and

$A_{n_{i}\times
n_{j}}=\sigma(v_{i1}v_{j1})\left(\begin{array}[]{ccc}1&J_{1\times
s_{j}}&-J_{1\times(n_{j}-s_{j}-1)}\\\ J_{s_{i}\times 1}&J_{s_{i}\times
s_{j}}&-J_{s_{i}\times(n_{j}-s_{j}-1)}\\\ -J_{(n_{i}-s_{i}-1)\times
1}&-J_{(n_{i}-s_{i}-1)\times
s_{j}}&J_{(n_{i}-s_{i}-1)\times(n_{j}-s_{j}-1)}\\\ \end{array}\right).$

Then $det(\lambda I-D^{\pm}(\Sigma))=(\lambda+2)^{n-k}f(\lambda)$, where

$f(\lambda)=\begin{vmatrix}\lambda-2n_{1}+2&-\sigma(v_{11}v_{21})n_{2}&\cdots&-\sigma(v_{11}v_{k1})n_{k}\\\
-\sigma(v_{11}v_{21})n_{1}&\lambda-2n_{2}+2&\cdots&-\sigma(v_{21}v_{k1})n_{k}\\\
\vdots&\vdots&\vdots&\vdots\\\
-\sigma(v_{11}v_{k1})n_{1}&-\sigma(v_{21}v_{k1})n_{2}&\cdots&\lambda-2n_{k}+2\end{vmatrix}.$

Note that $\sigma(v_{i1}v_{j1})=-\sigma(v_{11}v_{i1})\sigma(v_{11}v_{j1})$ by
(ii) for $1<i\neq j\leq k$ and $\sigma^{2}(v_{i1}v_{j1})=1$ for $1\leq i,j\leq
k$, thus

$f(\lambda)=\begin{vmatrix}\lambda-2n_{1}+2&-\sigma(v_{11}v_{21})n_{2}&\cdots&-\sigma(v_{11}v_{k1})n_{k}\\\
-\sigma(v_{11}v_{21})n_{1}&\lambda-2n_{2}+2&\cdots&\sigma(v_{11}v_{21})\sigma(v_{11}v_{k1})n_{k}\\\
\vdots&\vdots&\vdots&\vdots\\\
-\sigma(v_{11}v_{k1})n_{1}&\sigma(v_{11}v_{21})\sigma(v_{11}v_{31})n_{2}&\cdots&\lambda-2n_{k}+2\end{vmatrix}.$

And

$\displaystyle f(-2)$
$\displaystyle=\begin{vmatrix}-2n_{1}&-\sigma(v_{11}v_{21})n_{2}&\cdots&-\sigma(v_{11}v_{k1})n_{k}\\\
-\sigma(v_{11}v_{21})n_{1}&-2n_{2}&\cdots&\sigma(v_{11}v_{21})\sigma(v_{11}v_{k1})n_{k}\\\
\vdots&\vdots&\vdots&\vdots\\\
-\sigma(v_{11}v_{k1})n_{1}&\sigma(v_{11}v_{21})\sigma(v_{11}v_{31})n_{2}&\cdots&-2n_{k}\end{vmatrix}$
$\displaystyle=\Pi_{i=1}^{k}n_{k}\begin{vmatrix}-2&-1&\cdots&-1\\\
-1&-2&\cdots&1\\\ \vdots&\vdots&\vdots&\vdots\\\ -1&1&\cdots&-2\end{vmatrix}$
$\displaystyle=\Pi_{i=1}^{k}n_{k}(-3)^{k-1}(k-3),$

$f(-2)=0$ if and only if $k=3$ and this shows that (3) is correct.

If $k=3$, then $det(\lambda
I-D^{\pm}((K_{n_{1},n_{2},,n_{3}},\sigma))=(\lambda+2)^{n-3}g(\lambda)$, where

$\displaystyle g(\lambda)$
$\displaystyle=\begin{vmatrix}\lambda-2n_{1}+2&-\sigma(v_{11}v_{21})n_{2}&-\sigma(v_{11}v_{31})n_{3}\\\
-\sigma(v_{11}v_{21})n_{1}&\lambda-2n_{2}+2&\sigma(v_{11}v_{21})\sigma(v_{11}v_{31})n_{3}\\\
-\sigma(v_{11}v_{31})n_{1}&\sigma(v_{11}v_{21})\sigma(v_{11}v_{31})n_{2}&\lambda-2n_{3}+2\end{vmatrix}$
$\displaystyle=(\lambda+2)h(\lambda),$

and
$h(\lambda)={\lambda}^{2}+\left(-2\,n+4\right)\lambda+3\,n_{{1}}n_{{2}}+3\,n_{{1}}n_{{3}}+3\,n_{{2}}n_{{3}}-4\,n+4$,
note that $h(-2)=3(n_{1}n_{2}+n_{1}n_{3}+n_{2}n_{3})\neq 0$. It means that the
multiplicity of $-2$ is $n-2$ and (2) holds. This completes the proof. ∎

######  Lemma 10.

[8] The following properties of a signed graph $\Sigma$ are equivalent.

  1. (i)

$\Sigma$ is balanced;

  2. (ii)

$D^{max}(\Sigma)$ is cospectral with $D(G)$;

  3. (iii)

$D^{min}(\Sigma)$ is cospectral with $D(G)$.

The main outcomes of our investigation are as follows.

######  Theorem 5.

Let $\Sigma=(G,\sigma)$ be a connected signed graph and $D^{max}$ and
$D^{min}$ be two signed distance matrices of $\Sigma$. Then

  1. (I)

$\lambda_{n}(D^{max}(\Sigma))=\lambda_{n}(D^{min}(\Sigma))=-1$ if and only if
$\Sigma$ is a balanced signed completed graph $K_{n}$;

  2. (II)

There does not exist a signed graph $\Sigma$ of order $n$ such that
$\\{\lambda_{n}(D^{max}(\Sigma)),\lambda_{n}(D^{min}(\Sigma))\\}\in(-2,-1)$;

  3. (III)

$\lambda_{n}(D^{max}(\Sigma))=\lambda_{n}(D^{min}(\Sigma))=-2$ with
multiplicity $n-k$ if and only if $\Sigma$ is a balanced signed complete
$k$-partite graph with $2\leq k\leq n-1$.

###### Proof.

(I). Sufficiency is clearly established. If diameter $d\geq 2$, then both
$\lambda_{n}(D^{max})$ and $\lambda_{n}(D^{min})$ are less than or equal to
$-2$ by Lemma 4, a contradiction. Thus, $d=1$, i.e., $G\cong K_{n}$ and the
proof is completed by Lemma 10 and Remark 27. And there does not exist a
signed graph $\Sigma$ of order $n$ such that
$\\{\lambda_{n}(D^{max}(\Sigma)),\lambda_{n}(D^{min}(\Sigma))\\}\in(-2,-1)$
clearly, (II) is correct.

(III). The sufficiency holds immediately by Lemmas 10 and 8. Conversely, we
first claim that diameter $d\leq 2$. Otherwise, $(P_{4},\sigma)$ is an induced
subgraph of $\Sigma$, and both $\lambda_{n}(D^{max}(\Sigma))$ and
$\lambda_{n}(D^{min}(\Sigma))$ less than $-2$ by Lemma 7. Now, we derive the
proof into the following cases.

$\underline{\mbox{Case 1. }}$ $\Sigma$ is a signed tree. Obviously, $\Sigma$
is compatible, that is, $D^{max}(\Sigma)=D^{min}(\Sigma)=D^{\pm}(\Sigma)$.
Thus $\Sigma=(K_{1,n-1},\sigma)$ and the conclusion is valid by Lemmas 10 and
8.

$\underline{\mbox{Case 2.}}$ $\Sigma$ contains signed cycles. Since the least
eigenvalues of the principle submatrices indexed by $V(P_{4})$ or $V(C_{5})$
are always less than $-2$, the girth $g\leq 4$.

$\underline{\mbox{Subcase 2.1.}}$ $g=3$. If $\Sigma$ is an unbalanced complete
graph, the the shortest negative cycle must be $C_{3}$ by Remark 27. If $n\geq
4$, then $(K_{4},\sigma)\subset\Sigma$ and
$D^{max}(\Sigma)=D^{min}(\Sigma)=D^{\pm}(\Sigma)$ must contain one of the
following matrices as a principle submatrix,

$\left(\begin{array}[]{ccccc}0&-1&1&i\\\ -1&0&1&j\\\ 1&1&0&k\\\ i&j&k&0\\\
\end{array}\right)~{}~{}~{}~{}\left(\begin{array}[]{ccccc}0&-1&-1&i\\\
-1&0&-1&j\\\ -1&-1&0&k\\\ i&j&k&0\\\ \end{array}\right),$

where $\mid i\mid=\mid j\mid=\mid k\mid=1$. It is a pity that the least
eigenvalues of the above matrices are always less than $-2$, a contradiction.
Thus, $\Sigma$ is an unbalanced $K_{3}$ and its eigenvalues are $-2$ and $1$
with multiplicity $2$, a contradiction.

Thus $\Sigma$ is not an unbalanced complete graph. Since the least eigenvalue
of the principle submatrix indexed by $V(H_{1})$ is always less than $-2$ and
$n\geq 4$, then $V(\Sigma)$ can be partitioned into four parts
$V_{1},V_{2},V_{3}$ and $V_{4}$, where $V_{1}=\\{u|uv_{2},uv_{3}\in
E(\Sigma)\\}$, $V_{2}=\\{u|uv_{1},uv_{3}\in E(\Sigma)\\}$,
$V_{3}=\\{u|uv_{1},uv_{2}\in E(\Sigma)\\}$ and
$V_{4}=\\{u|uv_{1},uv_{2},uv_{3}\in E(\Sigma)\\}$. Clearly, $v_{1}\in V_{1}$,
$v_{2}\in V_{2}$ and $v_{3}\in V_{3}$. Meanwhile, $V_{i}$ is an independent
set and every vertex of $V_{j}$ is adjacent to every vertex of $V_{k}$ for
$1\leq i\leq 3$ and $1\leq j\neq k\leq 4$. We partition $V_{4}$ to independent
sets $V_{41}\cup\cdots\cup V_{4t}$, then $uv\in E$ for any $u\in V_{4i}$ and
$v\in V_{4j}$ for $1\leq i\neq j\leq t$ and $t\geq 2$ through the same methods
in [10]. Therefore, $\Sigma$ is a signed completed multipartite graph
$(K_{n_{1},n_{2},\ldots,n_{k}},\sigma)$. If $\Sigma$ is balanced, then the
proof is completed by Lemmas 10 and 8. Next, let’s assume $\Sigma$ is
unbalanced. Then $\Sigma$ must be an unbalanced completed $3$-partite graph
since $\Sigma$ cannot contain an unbalanced $K_{4}$ as an induced subgraph.
Let $V=V_{1}\cup V_{2}\cup V_{3}$, where $\mid V_{i}\mid=n_{i}\geq 1$ and
$n=n_{1}+n_{2}+n_{3}\geq 5$.

######  Claim 28.

The paths of length two for any two nonadjacent vertices have the same sign.

Otherwise, $D^{max}(\Sigma)$ must contain one of $\\{A_{6},A_{7}\\}$ as a
principle submatrix,

$A_{6}=\left(\begin{array}[]{ccccc}0&1&2&1\\\ 1&0&-1&i\\\ 2&-1&0&1\\\
1&i&1&0\\\
\end{array}\right)~{}~{}~{}\mbox{or}~{}~{}~{}A_{7}=\left(\begin{array}[]{ccccc}0&1&2&-1\\\
1&0&-1&i\\\ 2&-1&0&-1\\\ -1&i&-1&0\\\ \end{array}\right)$

and $D^{min}(\Sigma)$ must contain one of $\\{A_{8},A_{9}\\}$ as a principle
submatrix,

$A_{8}=\left(\begin{array}[]{ccccc}0&1&-2&1\\\ 1&0&-1&j\\\ -2&-1&0&1\\\
1&j&1&0\\\
\end{array}\right)~{}~{}\mbox{or}~{}~{}A_{9}\left(\begin{array}[]{ccccc}0&1&-2&-1\\\
1&0&-1&j\\\ -2&-1&0&-1\\\ -1&j&-1&0\\\ \end{array}\right),$

where $i=\pm 1,2$, $j=\pm 1,-2$. Yet, sad to say, the least eigenvalues of the
above matrices are less than $-2$, a contradiction.

######  Claim 29.

$(K_{n_{i},n_{j}},\sigma)$ is balanced for $n_{i},n_{j}\geq 2$, $1\leq i\neq
j\leq 3$.

Otherwise, assume that $C_{2k}=v_{1}v_{2}\ldots v_{2k}$ is a shortest negative
cycle, then $k\geq 3$ since $\sigma(C_{4})=1$ for any
$(C_{4},\sigma)\subset\Sigma$ by Claim 28. Without loss of generality, assume
that $\sigma_{12}=1$ and $\sigma_{1,2k}=-1$. Let
$C^{\prime}=v_{1}v_{2}v_{2k-1}v_{2k}v_{1}$ and
$C^{\prime\prime}=v_{2}v_{3}\ldots v_{2k-2}v_{2k-1}v_{2}$, then
$\sigma(C^{\prime\prime})=-1$ since $\sigma(C^{\prime})=1$, but the length of
$C^{\prime\prime}$ is $2k-2$, a contradiction.

######  Claim 30.

The length of shortest negative cycle must be three.

Otherwise, assume that $(C_{k},\sigma)$ is a shortest negative cycle, then
$k\geq 5$ by Claim 28. We assume that $\sigma_{12}=1$ and $\sigma_{1k}=-1$ at
first. If $v_{2}v_{k}\in E$, then $\sigma_{2k}=-1$. We can construct a new
negative cycle $C^{\prime}=v_{2}\ldots v_{k}v_{2}$, but the length of
$C^{\prime}$ is $k-1$, a contradiction. If $v_{2}v_{k}\notin E$, then
$v_{2}v_{k-1}\in E$ and $\sigma_{2,k-1}\sigma_{k,k-1}=-1$ by Claim 28.
Constructing a new negative cycle $C^{\prime\prime}=v_{2}\ldots v_{k-1}v_{2}$
with length $k-2$, a contradiction. We can get the similar contradiction when
$\sigma(v_{1}v_{2})=\sigma(v_{1}v_{k})=-1$.

######  Claim 31.

$\sigma(K_{3})=-1$ for every $K_{3}\subset K_{n_{1},n_{2},n_{3}}$.

We will prove the claim by using reduction to absurdity. Note that any two
triangles with a common edge must have the same sign by Claim 28. Suppose that
$C^{\prime}=v_{1}v_{2}v_{3}v_{1}$,
$C^{\prime\prime}=v^{\prime}_{1}v^{\prime}_{2}v^{\prime}_{3}v^{\prime}_{1}$,
where $\sigma(C^{\prime})\sigma(C^{\prime\prime})=-1$ and
$v_{i},v^{\prime}_{i}\in V_{i}$ for $1\leq i\leq 3$. Let
$C^{\prime\prime\prime}=v_{1}v^{\prime}_{2}v_{3}v_{1}$. If
$v_{1}=v^{\prime}_{1}$, $v_{2}\neq v^{\prime}_{2}$ and $v_{3}\neq
v^{\prime}_{3}$, then $\sigma(C^{\prime})\sigma(C^{\prime\prime\prime})=1$ and
$\sigma(C^{\prime\prime})\sigma(C^{\prime\prime\prime})=1$, it is impossible.
And this situation shows that any two triangles with a common vertex also have
the same sign. If $v_{1}\neq v^{\prime}_{1}$, $v_{2}\neq v^{\prime}_{2}$ and
$v_{3}\neq v^{\prime}_{3}$, then
$\sigma(C^{\prime})\sigma(C^{\prime\prime\prime})=1$ and
$\sigma(C^{\prime\prime})\sigma(C^{\prime\prime\prime})=1$, it is impossible.
Therefore, Claim 31 holds by Claim 30.

By Claims 28-31, we discover that $\Sigma$ is an unbalanced completed
$3$-partite graph which satisfies the conditions in Lemma 9. However, the
multiplicity of $-2$ is $n-2$, a contradiction.

$\underline{\mbox{Subcase 2.2.}}$ $g=4$. Since the least eigenvalue of the
principle submatrix indexed by $V(H_{2})$ is always less than $-2$, we can get
$\Sigma$ is a signed complete bipartite graph through the same methods in
[10]. And then $\Sigma$ is balanced by Claim 29 of Subcase 2.1 immediately. ∎

## References

  * [1] M. Aouchiche, P. Hansen, Distance spectra of graphs: A survey, _Linear Algebra Appl._ 458 (2014) 301–386.
  * [2] S. Akbari, S. Dalvandi, F. Heydari, M. Maghasedi, Signed complete graphs with maximum index, _Discuss Math Graph Theory_ 40 (2020) 393–403.
  * [3] S. Chaiken, A combinatorial proof of the all minors matrix tree theorem, _SIAM J. Algebraic Discrete Methods_ 3 (1982) 319–329.
  * [4] D. Cartwright, F. Harary, Structural balance: a generalization of Heider’s theory, _Psychol Rev._ 63 (1956) 277–293.
  * [5] P.D. Chawathe, G.R. Vijayakumar, A characterization of signed graphs represented by root system $D_{\infty}$, _European J. Combin._ 11 (1990) 523-533.
  * [6] E. Ghorbani, A. Majidi, Signed graphs with maximal index, _Discrete Math._ 344 (2021) 112463.
  * [7] F. Harary, On the notion of balance in a signed graph,_Michigan Math. J._ 2 (1953) 143–146.
  * [8] S.K. Hameed, T.V. Shijin, P. Soorya, K.A. Germina, T. Zaslavsky, Signed distance in signed graphs, _Linear Algebra Appl._ 608 (2021) 236–247.
  * [9] T. Koledin, Z. Stanić, Connected signed graphs of fixed order, size, and number of negative edges with maximal index, _Linear Multilinear Algebra_ 65 (2017) 2187–2198.
  * [10] H.Q. Lin, Y. Hong, J.F. Wang, J.L. Shu, On the distance spectrum of graphs, _Linear Algebra Appl._ 439 (2013) 1662–1669.
  * [11] H.Q. Lin, On the least distance eigenvalue and its applications on the distance spread, _Discrete Math._ 338 (2015) 868–874.
  * [12] N.M. Singhi, G.R. Vijayakumar, Signed graphs with least eigenvalue $<-2$, _European J. Combin._ 13 (1992) 219–220.
  * [13] G.R. Vijayakumar, Signed graphs represented by $D_{\infty}$, _European J. Combin._ 8 (1987) 103–112.
  * [14] G.R. Vijayakumar, Algebraic equivalence of signed graphs with all eigenvalues $\geq-2$, _Ars Combin._ 35 (1993) 173–191.
  * [15] G. Yu, On the least distance eigenvalue of a graph, _Linear Algebra Appl._ 439 (2013) 2428–2433.
  * [16] T. Zaslavsky, Signed graphs, _Discrete Appl. Math._ 4 (1982) 47–74.
  * [17] T. Zaslavsky, Biased graphs, I: bias, balance, and gains, _J. Combin. Theory Ser. B_ 47 (1989) 32–52