A signed graph $ \Gamma $ is a pair $ (G, \sigma) $, where $ G = (V(G), E(G)) $ is a graph and $ \sigma :E(G) \to \{ + 1, - 1 \} $ is a sign function on the edges of $ G $. The unsigned graph $ G $ of $ \Gamma $ is called the underlying graph. Most of concepts defined for (unsigned) graphs are directly extendable to signed graphs. For example, the degree of a vertex $ u $ in $ G $, denoted by $ d_u $, is also its degree in $ \Gamma $. A signed subgraph of $ (G, \sigma) $ is a subgraph of $ G $ with signature induced by $ \sigma $. Thus if $ u \in V(G) $, then $ \Gamma - u $ denotes the signed subgraph having $ G - u $ as the underlying graph, while its signature is the restriction form $ E(G) $ of $ \sigma $ to $ E(G-u) $. If $ U \subset V( G ) $ then $ \Gamma \left[ U \right] $ denotes the signed induced subgraph arising from $ U $, while $ \Gamma - U = \Gamma \left[ {V\left( G \right){\rm{ \backslash }}U} \right] $. We also write $ \Gamma - \Gamma \left[ U \right] $ instead of $ \Gamma - U $. The order of $ \Gamma $ is the order of $ G $ and it is denoted by $ \left| \Gamma \right| $. The cycle, the path, and the complete graph all on $ n $ vertices are denoted by $ C_n $, $ P_n $ and $ K_n $, respectively. The graph $ G $ which contains only one vertex is called trivial. Otherwise, it is called nontrivial. The girth $ g $ of $ G $ the length of a shortest cycle contained in the graph $ G $. A pendant vertex of $ G $ is a vertex of degree $ 1 $. A path $ P: v_0 v_1 \dots v_{t-1}v_t $ in $ G $ is called a pendant path if $ d(v_i) = 2, i = 1, 2, \dots, t-1 $ and $ d(v_t) = 1 $. If $ t = 1 $, then $ v_0v_1 $ is a pendant edge of $ G $. If $ d(v_0) \ge 3 $, we say that $ P $ is a maximal pendant path.

Let $ C $ be a cycle in $ \Gamma $, the sign of $ C $ is given by $ \sigma \left( C \right) = \prod\nolimits_{e \in C} {\sigma \left( e \right)} $. A cycle whose sign is $ 1 $ (resp. $ -1 $) is called positive (resp. negative). Clearly, a cycle is positive if and only if it contains an even number of negative edges. A signed graph is balanced if all cycles are positive, otherwise it is unbalanced. If all edges in $ \Gamma $ are positive (negative), then $ \Gamma $ is denoted by $ \left( {G, + } \right) $ (resp. $ \left( {G, -} \right)) $, and we say that such a signature is all-positive (resp., all-negative). For $ \Gamma = (G, \sigma) $ and $ U \subset V(G) $, let $ \Gamma^U $ be the signed graph obtained from $ \Gamma $ by reversing the signature of the edges in the cut $ \left[ {U, V(G){\rm{ \backslash }}U} \right] $, namely $ {\sigma _{{\Gamma ^U}}}\left( e \right) = - {\sigma _\Gamma }\left( e \right) $ for any edge $ e $ between $ U $ and $ V(G){\rm{ \backslash }}U $, and $ {\sigma _{{\Gamma ^U}}}\left( e \right) = {\sigma _\Gamma }\left( e \right){\rm{ }} $ otherwise. The signed graph $ \Gamma^U $ is said to be (signature) switching equivalent to $ \Gamma $, and this is denoted by $ {\Gamma ^U} \sim \Gamma $. Switching equivalent signed graphs can be considered as (switching) isomorphic graphs and their signatures are said to be equivalent.

Signed graphs, like unsigned ones, can be studied by means of the eigenvalues of several matrices associated to graphs. The adjacency matirx $ A(\Gamma) = \left( {{a_{ij}}} \right) $ of $ \Gamma $ is naturally defined similarly to that of unsigned graphs by putting $ 1 $ or $ -1 $, whenever the corresponding edge is either positive or negative, respectively. The Laplacian matrix $ L $ is defined as $ L: L(\Gamma) = D(G)-A(\Gamma) $, where $ D $ is the diagonal matrix of vertex degrees. It is worth mentioning that switching equivalent signed graphs have similar adjacency and Laplacian matrix. In fact, let $ {S_U} = diag\left( {{s_1}, {s_2}, \cdots , {s_n}} \right) $ with $ {s_i} = 1 $ for each $ i \in U \subset V(G) $, and $ {s_i} = -1 $ otherwise. We have

$ A\left( \Gamma \right) = {S_U}A\left( {{\Gamma ^U}} \right){S_U}{\rm{ \ \ and \ \ }}L\left( \Gamma \right) = {S_U}L\left( {{\Gamma ^U}} \right){S_U}. $

Conversely, if $ L(\Gamma_1) $ and $ L(\Gamma_2) $ are similar by a diagonal matrix with its entries are $ 1 $ or $ -1 $, then $ \Gamma_1 $ and $ \Gamma_2 $ are switching equivalent. The characteristic polynomial $ {\phi _L}\left( {\Gamma , x} \right): = \phi \left( {\Gamma , x} \right) = \det \left( {xI - L\left( \Gamma \right)} \right) $ is called the Laplacian characteristic polynomial of $ \Gamma $. The Laplacian eigenvalues $ {\lambda _1}\left( \Gamma \right) \ge {\lambda _2}\left( \Gamma \right) \ge \cdots \ge {\lambda _n}\left( \Gamma \right) \ge 0 $ of $ \Gamma $ of order $ n $ are all real numbers, because $ L(\Gamma) $ is a real semi-defined symmetric matrix.

The least Laplacian eigenvalue has a special role in the spectral theory of signed Graphs. It is well-known that $ \Gamma $ is balanced, that is, $ \Gamma = (G, \sigma) $ is switching equivalent to $ \left( {G, + } \right) $, and $ L(\Gamma) $ is similar to $ L(G) = D(G)-A(G) $, where $ A(G) $ is the adjacency matrix of the unsigned graph $ G $, if and only if $ \lambda \left( \Gamma \right):{\lambda _n}\left( \Gamma \right) = 0 $. Therefore, if $ \Gamma $ is not balanced, then $ {\lambda _n} > 0 $ and $ \lambda $ has been shown to be a very good measure of the graph frustration, that is the smallest number of vertices to be deleted form $ \Gamma $ in order to get a balanced signed graph(see [1, 2]). The study on the signed graph has attracted a lot of attention. One can refer to [3] for basic results on graph spectra, to [4-7] for basic results on the spectra of signed graphs, to [8] for a possibly complete bibliography on signed graphs, and to [9] for a glossary of terms related to signed graphs. Recently, Francesco Belardo and others studied the least Laplacian eigenvalue of signed graphs. He showed that among unbalanced connected signed graphs of given order the least eigenvalue is minimal for an unbalanced triangle with a hanging path, while the least eigenvalue is maximal for the complete graph with the all-negative sign function, and among the unbalanced bicyclic signed graphs of given order $ n \ge 5 $ the least laplacian eigenvalue is minimal for signed graphs consisting of two triangles, only one of which is unbalanced, connected by a path, in [10] and [11] respectively.

In this paper, we investigate how the least eigenvalue of the Laplacian of a signed graph changes by relocating a tree branch from one vertex to another vertex. As an application, we determine the graph whose least laplacian eigenvalue attains the minimum among all connected unbalanced signed graphs of fixed order and given number of pendant vertices.

We begin with some fundamental results which will be used later. For a vector $ x = {\left( {{x_1}, {x_2}, \cdots , {x_n}} \right)^T} $ of $ L(\Gamma) $, we denote by $ x_u $ the entry of $ x $ at $ u \in V(G) $. If $ x $ is an eigenvector of $ L(\Gamma) = L $ with respect to an eigenvalue $ \lambda $, then we have eigenvalue equation

$ \lambda {x_u} = {d_u}{x_u} - \sum\limits_{v \sim u} {\sigma \left( {uv} \right)} {x_v}\ \ {\rm{ for }}\ \ u \in V\left( G \right), $

where $ v \sim u $ means that $ v $ is adjacent to $ u $.

The quadratic form $ \langle {L\left( \Gamma \right), x} \rangle $ can be respected as

$ \langle {L\left( \Gamma \right), x} \rangle = {x^T}L\left( \Gamma \right)x = {\sum\limits_{uv \in E(G)} {\left( {{x_u} - \sigma \left( {uv} \right){x_v}} \right)} ^2}. $

Since $ L(\Gamma) $ is a real symmetric matrix, by Rayleigh principle, it follows that

$ \lambda \left( \Gamma \right) = {\lambda _n}\left( \Gamma \right): = {\lambda _n}\left( L \right) = \mathop {\min }\limits_{\left\| x \right\| = 1} \langle {L\left( \Gamma \right), x} \rangle. $

We need to introduce an operation on graphs as the following.

Coalescence   Let $ \Gamma_1 $, $ \Gamma_2 $ be two vertex-disjoint signed graphs, and let $ v_1 \in V(\Gamma_1) $, $ v_2 \in V(\Gamma_2) $. The coalescence of $ \Gamma_1 $, $ \Gamma_2 $, denoted by $ {\Gamma_1(v_1)} \circ {\Gamma_2(v_2)} $, is obtained from $ \Gamma_1 $, $ \Gamma_2 $ by identifying $ v_1 $ with $ v_2 $ and forming a new vertex $ u $. The graph $ {\Gamma_1(v_1)} \circ {\Gamma_2(v_2)} $ is also written as $ {\Gamma_1(u)} \circ {\Gamma_2(u)} $. Suppose $ \Gamma $ is a connected graph and can be expressed in the form $ \Gamma = {\Gamma_1(v_1)} \circ {\Gamma_2(v_2)} $, where $ \Gamma_1 $ and $ \Gamma_2 $ are both nontrivial and connected, then $ \Gamma_1 $ is called a branch of $ \Gamma $ with root $ u $. Let $ x $ be a vector defined on $ \Gamma $. A branch of $ \Gamma $ is called zero branch with respect to $ x $ if $ x_v = 0 $ for all $ v $ in it.

Lemma 2.1    Let $ \lambda(\Gamma) $ be the least laplacian eigenvalue of $ \Gamma(G, \sigma) $ with corresponding unit eigenvector $ x = {\left( {{x_1}, {x_2}, \cdots , {x_n}} \right)^T} $. If $ uv $ is a bridge, then $ \sigma(uv) x_u x_v \ge 0 $.

Proof   Suppose $ uv $ is a bridge, then $ G $ is a connected sum of two graphs $ G_1 $ and $ G_2 $ where $ V( G ) = V( {{G_1}} ) \cup V( {{G_2}} ) $ and $ E(G) $ differs from $ E( G ) = E( {{G_1}} ) \cup E( {{G_2}} ) $ by addition of a single edge joining the vertex $ u $ of $ G_1 $ to the vertex $ v $ of $ G_2 $. If $ \sigma (uv) = 1 $, suppose $ x_u x_v<0 $, let $ y $ be a valuation of $ \Gamma $ by

$ \left\{ \begin{array}{l} y_w = x_w, \ \ w \in V\left( {{G_1}} \right);\\ y_w = - x_w, w \in V\left( {{G_2}} \right). \end{array} \right. $

We have

$ \begin{array}{l} \langle {L\left( \Gamma \right), y} \rangle = {\left( {{x_u} + {x_v}} \right)^2} + \sum\limits_{ws \in E\left( {{G_1}} \right)} {{{\left( {{x_w} - \sigma \left( {ws} \right){x_s}} \right)}^2}} + {\sum\limits_{ws \in E\left( {{G_2}} \right)} {\left[ { - {x_w} - \sigma \left( {ws} \right)\left( { - {x_s}} \right)} \right]} ^2}\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ < {\left( {\left| {{x_u}} \right| + \left| {{x_v}} \right|} \right)^2} + \sum\limits_{ws \in E\left( {{G_1}} \right)} {{{\left( {{x_w} - \sigma \left( {ws} \right){x_s}} \right)}^2}} + \sum\limits_{ws \in E\left( {{G_2}} \right)} {{{\left( {{x_w} - \sigma \left( {ws} \right){x_s}} \right)}^2}} \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = {\left( {\left| {{x_u}} \right| + \left| {{x_v}} \right|} \right)^2} + \sum\limits_{ws \in E\left( G \right){\rm{\backslash }}uv} {{{\left( {{x_w} - \sigma \left( {ws} \right){x_s}} \right)}^2}} \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \lambda, \end{array} $

contradiction. Proof of the case $ \sigma (uv) = -1 $ is similar, here omitted.

Next, we will give some properties of the eigenvector corresponding to the least laplacian eigenvalue of signed graphs. Note that the signature is not relevant in trees and in general for edges which are bridges, for the sake of simplicity, we will put a positive sign on bridges, unless otherwise stated.

Lemma 2.2    Let $ \Gamma $ be a signed graph of order $ n $ with minimum degree $ \delta $, then $ \lambda (\Gamma)< \delta $. If $ G $ contains a pendant vertex, then $ \lambda (\Gamma)< 1 $.

Proof   Let $ x = {( {{x_1}, {x_2}, \dots, {x_n}} )^T} $ be an any nonzero unit vector in $ \mathbb R^n $. We have

$ \begin{eqnarray*} \lambda (\Gamma) \le \langle {L\left( \Gamma \right), x} \rangle = \sum\limits_{uv \in E(G)} {{{\left( {{x_u} - \sigma \left( {uv} \right){x_v}} \right)}^2.}} \end{eqnarray*} $

Putting $ x = {( {{0}, {0}, \dots , {1}} )^T} $, we get that $ \lambda \le \delta $. We can easily see $ x = {( {{0}, {0}, \dots , {1}} )^T} $ is not an eigenvector corresponding to $ \lambda (\Gamma) $, the inequality is strict.

Lemma 2.3    Let $ \Gamma $ be a signed graph which contains a tree branch $ T $ with root $ u $. Let $ x $ be a unit eigenvector corresponding to the least laplacian eigenvalue $ \lambda(\Gamma) $.

(ⅰ) $ x_p x_q \ge 0 $, for every $ p, q \in T $.

(ⅱ) Assume that there is a vertex $ v\in T $ such that $ x_v = 0 $. Then $ x_w = 0 $ for every $ w\in T $.

(ⅲ) Let $ \Gamma $ be an unbalanced signed graph and $ x_u \ne 0 $, and let $ P = v_0(u)v_1 \dots v_k $ be a path on $ T $, then $ \left| {{x_{{v_0}}}} \right| = \left| {{x_u}} \right| < \left| {x_{{v_1}}} \right| < \cdots < \left| {x_{{v_k}}} \right| $.

Proof    Note that all edges in $ T $ are bridges, by lemma 2.1, (i) is proved. To prove the result (2), we consider two following cases.

Case 1    $ v \in T-u. $ Considering the entry of $ L\left( {{\Gamma }} \right)x $ at $ v $, we have $ \lambda {x_v} = {d_v}{x_v} - \sum\limits_{w \sim v} {{x_w}}. $ By (ⅰ), the result holds.

Case 2   $ v = u. $ Let $ y $ be a valuation of $ \Gamma $ by

$ \left\{ {\begin{array}{*{20}{c}} {{y_w} = {x_w}, w \in \Gamma {\rm{\backslash }}T;}\\ {{y_w} = - {x_w}, w \in T.} \end{array}} \right. $

Note that $ \left\| y \right\| = 1 $, and $ \langle {L\left( \Gamma \right), y} \rangle = \langle {L\left( \Gamma \right), x} \rangle $. So $ y $ is also a eigenvector corresponding to $ \lambda(\Gamma) $. Considering the entry of $ L\left( {{\Gamma }} \right)x $ and $ L\left( {{\Gamma }} \right)y $ at $ u $, respectively. We have

$ \sum\limits_{w \sim u, w \in \Gamma {\rm{\backslash }}T} {\sigma \left( {uw} \right){x_w}} + \sum\limits_{w \in T - u} {{x_w}} = 0, \ \ \ \ \ \ \ \ \sum\limits_{w \sim u, w \in \Gamma {\rm{\backslash }}T} {\sigma \left( {uw} \right){x_w}} + \sum\limits_{w \in T - u} {\left( { - {x_w}} \right)} = 0. $

Thus, we have $ \sum\limits_{w \in T-u} {{x_w}} = 0{\rm{ }} $, and hence $ x_w = 0 $ for for every $ w\in T $.

Next, we give the proof of (ⅲ). By Lemma 2.3, for a connected unbalanced signed graph $ \Gamma $ containing a pendant vertex, we have $ 0 < \lambda(\Gamma) < 1 $. Assume that $ v_k $ is a pendant vertex. Since $ x_u \ne 0 $, by (ⅱ) we drive that all $ x_{v_i} \ne 0 $. Considering the eigenvector equation of $ x $ at $ v_k $, we have

$ \left( {\lambda \left( \Gamma \right) - 1} \right){x_{{v_k}}} = - {x_{{v_{k - 1}}}}. $

The result holds. Now suppose $ v_i $ is not a pendant vertex. By the eigenvector of $ x $ at $ v_i $,

$ \lambda {x_{{v_i}}} = {d_{{v_i}}}{x_{{v_i}}} - \sum\limits_{w \sim {v_i}} {{x_w}}, $

by (ⅰ), we have

$ {d_{{v_i}}}\left| {{x_{{v_i}}}} \right| = \lambda \left( \Gamma \right)\left| {{x_{{v_i}}}} \right| + \left| {{x_{{v_{i - 1}}}}} \right| + \sum\limits_{w \sim {v_i}, w \ne {v_{i - 1}}} {\left| {{x_w}} \right|}, $

which leads to, by induction,

$ {d_{{v_i}}}\left| {{x_{{v_i}}}} \right| > \left| {{x_{{v_{i - 1}}}}} \right| + \sum\limits_{w \sim {v_i}, w \ne {v_{i - 1}}} {\left| {{x_w}} \right|} > \left| {{x_{{v_{i - 1}}}}} \right| + \left( {{d_{{v_i}}} - 1} \right)\left| {{x_{{v_i}}}} \right|. $

Hence $ \left| {{x_{{v_i}}}} \right| > \left| {{x_{{v_{i - 1}}}}} \right| $.

Next, we will discuss how the least laplacian eigenvalue changes when relocating a $ T $ branch for one vertex to another.

Lemma2.4   Let $ \Gamma = {\Gamma_1(v_2)} \circ {T(u)} $ and $ \Gamma ^\dagger = {\Gamma_1(v_1)} \circ {T(u)} $ be two graphs as depicted in Fig. 1, where $ v_1 $, $ v_2 $ are two distinct vertices of $ \Gamma_1 $ and $ u $ is a vertex of $ T $. Let $ x $ be a unit eigenvector corresponding to the least laplacian eigenvalue $ \lambda(\Gamma) $. If $ \left| {{x_{{v_1}}}} \right| \ge \left| {{x_{{v_2}}}} \right| $, then

$ \begin{eqnarray} \lambda \left( {{\Gamma ^\dagger }} \right) \le \lambda \left( \Gamma \right). \end{eqnarray} $

(2.1)

Furthermore, if $ \left| {{x_{{v_1}}}} \right| > \left| {{x_{{v_2}}}} \right| $or $ \left| {{x_{{v_1}}}} \right| = \left| {{x_{{v_2}}}} \right| > 0 $, the inequality is strict.

Proof   Assume that $ {x_{{v_1}}} \ge 0 $. Let $ y $ be a valuation of $ \Gamma ^\dagger $ by

$ \left\{ \begin{array}{l} {y_w} = {x_w}, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ w \in {\Gamma _1};\\ {y_w} = \left| {x_w} \right| + {x_{{v_1}}} - \left| {x_{{v_2}}} \right|, w \in T - u. \end{array} \right. $

Then for each edge $ wv_2 \in E(\Gamma) $ contained in $ T $, we have

$ {\left( {{x_w} - {x_{{v_2}}}} \right)^2} = {\left( {\left| {{x_w}} \right| - \left| {{x_{{v_2}}}} \right|} \right)^2} = {\left( {\left| {{x_w}} \right| + {x_{{v_1}}} - \left| {{x_{{v_2}}}} \right| - {x_{{v_1}}}} \right)^2} = {\left( {{y_w} - {y_{{v_1}}}} \right)^2.} $

For each edge $ vw \in E(T-u) $ and $ vw \in E(\Gamma_1) $, we have

$ {\left( {{x_w} - \sigma \left( {wv} \right){x_v}} \right)^2} = {\left( {{y_w} - \sigma \left( {wv} \right){x_v}} \right)^2}. $

Hence we have

$ \langle {L\left( {{\Gamma ^\dagger }} \right), y} \rangle = \sum\limits_{vw \in E\left( {{\Gamma ^\dagger }} \right)} {{{\left( {{y_w} - {\sigma \left( {wv} \right)} {y_v}} \right)}^2} = } \sum\limits_{vw \in E\left( \Gamma \right)} {{{\left( {{y_w} - {\sigma \left( {wv} \right)} {y_v}} \right)}^2} = } \langle {L\left( \Gamma \right), x} \rangle. $

By $ \left| {{x_{{v_1}}}} \right| \ge \left| {{x_{{v_2}}}} \right| $, we have

$ {\left\| y \right\|^2} = \sum\limits_{v \in V({\Gamma ^\dagger })} {y_v^2 \ge } \sum\limits_{v \in V(\Gamma )} {x_v^2 = 1}. $

All results lead to

$ \lambda \left( {{\Gamma ^\dagger }} \right) \le \frac{{\langle {L\left( {{\Gamma ^\dagger }} \right), y} \rangle }}{{{{\left\| y \right\|}^2}}} \le \langle {L\left( {{\Gamma ^\dagger }} \right), y} \rangle = \langle {L\left( {{\Gamma }} \right), x} \rangle = \lambda \left( \Gamma \right). $

Suppose that the equality holds, then $ \left| {{x_{{v_1}}}} \right| = \left| {{x_{{v_2}}}} \right| $ and $ y $ is an eigenvector of $ \lambda \left( {{\Gamma ^\dagger }} \right) $. Considering the eigenvector equations of $ x $ and $ y $, respectively, both at $ v_2 $, we have

$ \begin{eqnarray} d_u^T{x_u} = \sum\limits_{v \sim u, v \in T - u} {{x_v}}, \end{eqnarray} $

(2.2)

where $ d_u^T = \left| {\left\{ {v:v \sim u, v \in T - u} \right\}} \right| $.

If $ \left| {{x_{{v_1}}}} \right| > \left| {{x_{{v_2}}}} \right| $, the inequality (2.1) is strict. So we suppose $ \left| {{x_{{v_1}}}} \right| = \left| {{x_{{v_2}}}} \right| > 0 $. If $ \lambda \left( {{\Gamma ^\dagger }} \right) = \lambda \left( \Gamma \right) $, by (2.2) and lemma 2.3, we will have a contradiction. So inequality is also strict. The proof is completed.

We denote the class of unbalanced unicyclic signed graphs of order $ n $ with girth $ g $ and $ k \ge 1 $ pendant vertices by $ \mathcal U_n^k (g, \overline \sigma) $. In order to simplify the notation, we choose to represent any graph $ \Gamma $ in $ \mathcal U_n^k (g, \overline \sigma) $ with all positive edges other than the edge $ pq $ which is lying on the unique cycle of $ \Gamma $. Denote by $ U_n^k\left( {g, \overline \sigma , l;{l_1}, {l_2}, \cdots , {l_k}} \right) \in \mathcal U_n^k (g, \overline \sigma) $ the graph of order $ n $ obtained by coalescing $ P_l $ with a cycle $ C_g $ by identifying one of its end vertices with some vertex of $ C_g $, and also coalescing this $ P_l $ with each of paths $ P_{l_i} (i = 1, 2, \dots, k) $ by identifying its other end vertex with one of the vertices of $ P_{l_i} $, where $ l \ge 1, l_i \ge 2 (i = 1, 2, \dots, k) $. If $ l_1 = l_2 = \dots = l_k = 2 $, $ U_n^k\left( {g, \overline \sigma , l;{l_1}, {l_2}, \cdots , {l_k}} \right) $ is denoted by $ U_n^k(g) $ (up to switching equivalence, the graph is unique, see Fig 2, thin and thick edges represent positive and negative edges, respectively).

To achieve the goal, some useful results will be introduced. For more details, one can refer to [10].

Lemma 2.5(Theorem 2.2, [10]) Let $ \Gamma = (G, \sigma) $ be a signed graph, and let $ \Gamma ' $ be obtained from $ \Gamma $ by deleting the edge $ rs \in E(G) $ with sign $ \sigma (rs) $ and by adding the edge $ rt \in E(G) $ with sign $ \sigma (rt) $. Let $ x = {\left( {{x_1}, {x_2}, \cdots , {x_n}} \right)^T} $ be an eigenvector related to $ \lambda (\Gamma) $. If

$ (\sigma \left( {rt} \right){x_t} - \sigma \left( {rs} \right){x_s})\left( {\sigma \left( {rt} \right){x_t} + \sigma \left( {rs} \right){x_s} - 2{x_r}} \right) \le 0, $

then $ \lambda \left( {\Gamma '} \right) \le \lambda \left( \Gamma \right) $. Furthermore, $ \lambda \left( {\Gamma '} \right) = \lambda \left( \Gamma \right) $ if and only if $ {x_r} = \sigma \left( {rs} \right){x_s} = \sigma \left( {rt} \right){x_t} $.

Proposition 2.6(Proposition 2.3, [10]) Let $ \Gamma $ be a signed graph and $ {\Gamma '} $ switching equivalent via the state matrix $ S $. If $ x $ is an eigenvector of $ \lambda $ for $ \Gamma $, then $ Sx $ is the corresponding eigenvector of $ \lambda $ for $ {\Gamma '} $.

Lemma 2.7(Lemma 4.4, [10]) Let $ \Gamma \in \mathcal U_n^k (g, \overline \sigma) $ and $ x = {( {{x_1}, {x_2}, \dots, {x_n}} )^T} $ be an eigenvector corresponding to $ \lambda (\Gamma) $. If $ \sigma $ is taken such that all edges are positive with the exception of the $ pq $ which minimizes $ \left| {{x_p}{x_q}} \right| $, then $ x $ can be chosen such that

(1) $ x_v \ge 0 $ for all $ v \in \Gamma $.

(2) if $ x_p x_q = 0 $ then either $ x_p $ or $ x_q $ is non-zero.

(3) if $ x_p x_q > 0 $ then $ x_v > 0 $ for all $ v \in \Gamma $.

In view of the above results and the proof Lemma 4.2 in [10], it deserves to be mentioned that state matrix is a diagonal matrix with values in $ \{ 1, -1 \} $, then the eigenvectors after switching just change in the signs of the components corresponding to the switched vertices. The moduli of the eigenvector components are invariant with respect to switching. Let $ pq $ be the edge which minimizes $ \left| {{x_p}{x_q}} \right| $, then the corresponding eigenvector $ x = {( {{x_1}, {x_2}, \dots, {x_n}} )^T} $ to $ \lambda (\Gamma) $, for any $ \Gamma \in \mathcal U_n^k (g, \overline \sigma) $, satisfied

(1) there exists at most one component of $ x $ on the cycle is zero.

(2) if $ \left| x_p x_q \right| >0 $. then $ \left| x_v \right| > 0 $ for all $ v \in \Gamma $.

Theorem 2.8    Among all graphs in $ \mathcal U_n^k (g, \overline \sigma) $, the unique, up to switching equivalence, which minimizes the least Laplacian eigenvalue is $ U_n^k(g) $.

Proof    Let $ \Gamma $ be the signed graph which minimizes the least Laplacian eigenvalue in $ \mathcal U_n^k (g, \overline \sigma) $, $ x $ be a unit eigenvector corresponding to $ \lambda(\Gamma) $ and $ C_g $ be the unique cycle of $ \Gamma $. $ \Gamma $ can be considered from $ C_g $ by identifying each $ w \in C_g $ with one vertex of some tree $ T_w $ of order $ n_w $, where $ \sum\limits_{w \in {C_g}} {{n_w}} = n $. Note that if $ T_w $ is trivial, $ n_w = 1 $.

We assert that each nontrivial tree $ T_w $ is a nonzero branch with respect to $ x $.

Otherwise, by lemma 2.3 (ⅱ), there exists a nontrivial tree $ T_w $ attached at $ w $, $ w \in C_g $, such that $ x_w = 0 $. By lemma 2.4, relocating the tree $ T_w $ from $ w $ to $ v $ for which $ \left| x_v\right| \ne 0 $, we obtain a signed graph in $ \mathcal U_n^k (g, \overline \sigma) $ with smaller least Laplacian eigenvalue.

$ T_p $ and $ T_q $ are trivial.

If $ x_p = 0 $, $ x_q \ne 0 $, as above the proof $ T_p $ is trivial. Let $ s $ be another vertex adjacent to $ p $, considering the the eigenvector equation at $ p $, we have $ \lambda {x_p} = 2{x_p} + {x_q} - {x_s}, $ which leads to $ x_q = x_s $. If $ T_q $ is nontrivial, relocating the tree $ T_q $ from $ q $ to $ s $ for which $ \left| x_q\right| = \left| x_s\right| > 0 $, we obtain a signed graph in $ \mathcal U_n^k (g, \overline \sigma) $ with smaller least Laplacian eigenvalue, contradiction. If $ \left| x_p x_q \right| >0 $, by its minimum variance, there exits a vertex $ w $ on the cycle satisfied $ \left| {{x_w}} \right| \ge \max \left\{ {\left| {{x_p}} \right|, \left| {{x_q}} \right|} \right\} $, say $ {\left| {{x_p}} \right|} $. Relocating the tree $ T_p $ from $ p $ to $ w $, we obtain a signed graph in $ \mathcal U_n^k (g, \overline \sigma) $ with smaller least Laplacian eigenvalue, contradiction.

All maximal pendant paths are attached at the same vertex $ u $.

Otherwise, there exist two maximal pendant paths, say $ P $ and $ {P'} $, attached at $ p $ and $ p' $, respectively. Since $ {P'} $ is maximal pendant path, we have $ d\left( {p'} \right) \ge 3 $. Assume that $ \left| {{x_p}} \right| \ge \left| {{x_{p'}}} \right| > 0 $. Then, by lemma 2.4, we will arrive at a new graph still in $ \mathcal U_n^k (g, \overline \sigma) $ but with smaller least Laplacian eigenvalue by relocating $ {P'} $ from $ p' $ to $ p $.

Therefore, $ \Gamma $, up to switching equivalence, is obtained from a unbalanced signed $ C_g $ by attaching one path at some vertex of $ C_g $, or $ \Gamma = U_n^k\left( {g, \overline \sigma , l;{l_1}, {l_2}, \cdots , {l_k}} \right) $. Next we only consider the case $ k \ge 2 $ and show that $ {l_1} = {l_2} = \cdots = {l_k} = 2 $. Suppose that $ l_i \ge 3 $, for some $ i $. Let $ P_{l_i} = (u)v_1 \dots v_{l_i} $, by lemma 2.3 and the above discussion, $ 0 < \left| {{x_{{v_1}}}} \right| < \left| {{x_{{v_{{l_i} - 1}}}}} \right| $. Relocating some $ P_{l_j} $ other than $ P_{l_i} $ from $ v_1 $ to $ v_{l_i-1} $, by lemma 2.4, a new graph with smaller least Laplacian eigenvalue in $ \mathcal U_n^k (g, \overline \sigma) $ is obtained, contradiction.

In the sequel, the signature such that the sole negative edge corresponds to the cycle edge $ pq $ minimizing the product of the least eigenvector components (on the cycle) is denoted by $ U_n^k\left( {\overline g } \right) $. Furthermore, $ \lambda (U_n^k\left( {\overline g } \right)) $ has a nonnegative eigenvector. Without loss of generality, we take $ x_p \le x_q $, so that $ x_v > 0 $ for all $ v \in U_n^k\left( {\overline g } \right) -p $.

Lemma 2.9   With respect to $ g \ge 3 $ and $ k \ge 1 $, we have

$ \lambda \left( {U_n^{k - 1}\left( g \right)} \right) < \lambda \left( {U_n^k\left( g \right)} \right), \ \ \ \ \lambda \left( {U_n^k\left( {g - 1} \right)} \right) < \lambda \left( {U_n^k\left( g \right)} \right). $

Proof    The graph $ U_n^k\left( {\overline g } \right) $ the sole negative edge corresponds to the cycle edge $ pq $ minimizing the product of the least eigenvector components is depicted in Fig 2. From the proof of Theorem 2.8, we have $ T_p $ and $ T_q $ are trivial.

Let $ x $ be a unit eigenvalue corresponding to $ \lambda \left( {U_n^k\left( \overline g \right)} \right) $. Replacing the edge $ vv_1 $ by $ v_1 v_2 $, we arrive at a new graph $ \widetilde \Gamma \in \mathcal U_n^k (g, \overline \sigma) $, and by lemma 2.4, (note that $ \left| {{x_v}} \right| < \left| {{x_{{v_1}}}} \right| $), we have $ \lambda \left( {\widetilde \Gamma } \right) < \lambda \left( {U_n^k\left( \overline g \right)} \right) $. So, by Theorem 2.8, we have

$ \lambda \left( {U_n^{k - 1}\left( g \right)} \right) \le \lambda \left( {\widetilde \Gamma } \right) < \lambda \left( {U_n^k\left( \overline g \right)} \right) = \lambda \left( {U_n^k\left( g \right)} \right). $

For the second result, $ g\ge 4 $, we assert that $ {x_u} > {x_s} \ge {x_t} $ or $ {x_u} > {x_t} \ge {x_s} $. Otherwise, relocating $ T_u $ from $ u $ to $ s $ or $ t $, we arrive at a switching equivalent graph with smaller the least Laplacian eigenvalue, contradiction. We consider the case $ {x_u} > {x_t} \ge {x_s} $. Deleting the edge $ su $ and adding the edge $ st $, we arrive at a new graph $ {U_n^k\left( {g - 1} \right)} $, and $ \left( {{x_t} - {x_u}} \right)\left( {{x_t} + {x_u} - 2{x_s}} \right) < 0. $ So we have

$ \lambda \left( {U_n^k\left( {g - 1} \right)} \right) < \lambda \left( {U_n^k\left( \overline g \right)} \right) = \lambda \left( {U_n^k\left( g \right)} \right). $

Theorem 2.10   (Interlacing [14]) Let $ \Gamma = (G, \sigma) $ be a signed graph and $ \Gamma - e $ be the signed graph obtained from $ \Gamma $ by deleting the edge $ e $. Then

$ {\lambda _1}\left( \Gamma \right) \ge {\lambda _1}\left( {\Gamma - e} \right) \ge {\lambda _2}\left( {\Gamma - e} \right) \ge \cdots \ge {\lambda _n}\left( \Gamma \right){ \ge \lambda_n}\left( {\Gamma - e} \right). $

The main result of this section is as the following.

Theorem 2.11    Among all unbalanced signed connected graphs of order $ n $ and $ k \ge 1 $ pendant vertices, the unique, up to switching equivalence, which minimizes the least Laplacian eigenvalue is $ U_n^k\left( 3 \right) $.

Proof    Let $ \Gamma $ be a graph which minimizes the least Laplacian eigenvalue. Since $ \Gamma $ is unbalanced, then $ \Gamma $ contains at least an induced negative cycle, say $ C_g $. Let $ \Gamma ' $ be a connected unicyclic spanning subgraph of $ \Gamma $, which contains the unique cycle $ C_g $ and all pendant edges of $ \Gamma $. The signed graph $ \widehat \Gamma \in \mathcal U_n^{k '} (g, \overline \sigma ) $ is switching equivalent to $ \Gamma ' $, $ k' \ge k $. By lemmas above, we have

$ \begin{eqnarray} \lambda \left( {U_n^k\left( 3 \right)} \right) \le \lambda \left( {U_n^k\left( g \right)} \right) \le \lambda \left( {U_n^{k'}\left( g \right)} \right) \le \lambda (\widehat \Gamma) = \lambda \left( {\Gamma '} \right) \le \lambda \left( \Gamma \right). \end{eqnarray} $

(2.3)

So $ {U_n^k\left( 3 \right)} $ is a signed graph, which minimizes the the least Laplacian eigenvalue.

Next, we will prove that the minimizer among connected unbalanced graphs of order $ n $ and $ k \ge 1 $ pendant vertices is just $ {U_n^k\left( 3 \right)} $. By lemma 2.9 and Theorem 2.8, $ \lambda \left( \Gamma \right) = \lambda \left( {\Gamma '} \right) = \lambda \left( { \widehat \Gamma} \right) = \lambda \left( {U_n^k\left( 3 \right)} \right) $ implies $ k = k ' $, $ g = 3 $ and $ \Gamma ' $ is switching equivalent to $ {U_n^k\left( 3 \right)} $, and denoted by $ {U_n^k\left( 3 ' \right)} $. So $ \Gamma $ can be obtained form $ {U_n^k\left( 3 ' \right)} $ by adding edges. By the definition of $ \Gamma ' $, it suffices to derive a contradiction when $ \Gamma = U_n^k\left( 3 ' \right) + uv $, where $ uv $ is an edge joining a vertex of $ C_3 $ and a vertex of $ P_l $, or two vertices of $ P_l $. Let $ x = {\left( {{x_1}, {x_2}, \cdots , {x_n}} \right)^T} $ be a unit eigenvector corresponding to $ \lambda \left( \Gamma \right) $. Then

$ \begin{array}{l} \lambda \left( \Gamma \right) = \langle {L\left( \Gamma \right), x} \rangle = \langle {L\left( {U_n^k\left( 3' \right)} \right), x} \rangle + {\left( {{x_u} - \sigma \left( {uv} \right){x_v}} \right)^2}\\ \ \ \ \ \ \ \ \ \ge \lambda \left( {U_n^k\left( 3' \right)} \right) + {\left( {{x_u} - \sigma \left( {uv} \right){x_v}} \right)^2} \ \ge \lambda \left( {U_n^k\left( 3' \right)} \right). \end{array} $

Since $ \lambda \left( \Gamma \right) = \lambda \left( {U_n^k\left( 3' \right)} \right) $, and $ x $ is an eigenvector for $ \lambda \left( {U_n^k\left( 3' \right)} \right) $, we have that $ {{x_u} - \sigma \left( {uv} \right){x_v}} = 0 $, namely $ \left| {{x_u}} \right| = \left| {{x_v}} \right| $. By Proposition 3.5, there exists a state matrix $ S $ satisfied the vector $ x' = Sx = {\left( {{x_1 '}, {x_2'}, \cdots , {x_n'}} \right)^T} $ belonging to $ \lambda \left( {U_n^k\left( 3 \right)} \right) $. Hence $ \left| {{x_u '}} \right| = \left| {{x_v '}} \right| $. By Lemma 2.3, Lemma 2.7 and the proof of Lemma 2.9, contradiction, and we are done.