# Further Results on the Nullity of Signed Graphs

Authors: Yu Liu; Lihua You
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. A signed graph is a graph with a sign attached to each of its edges. In this paper, we apply the coefficient theorem on the characteristic polynomial of a signed graph and give two formulae on the nullity of signed graphs with cut-points. As applications of the above results, we investigate the nullity of the bicyclic signed graphΓ
∞
p
,
q
,
l, obtain the nullity set of unbalanced bicyclic signed graphs, and thus determine the nullity set of bicyclic signed graphs.


---

## Body

## 1. Introduction

LetG
=
(
V
,
E
) be a simple graph with vertex set V
=
V
(
G
)
=
{
v
1
,
v
2
,
…
,
v
n
} and edge set E
=
E
(
G
). The adjacency matrix A
=
A
(
G
)
=
(
a
i
j
)
n
×
n of G is defined as follows: a
i
j
=
1 if there exists an edge joining v
i and v
j, and a
i
j
=
0 otherwise. The nullity of a simple graph G is the multiplicity of the eigenvalue zero in the spectrum of A
(
G
), denoted by η
(
G
). The rank of G is referred to the rank of A
(
G
) and denoted by r
(
G
). Clearly, η
(
G
)
+
r
(
G
)
=
n if G has n vertices.A signed graph is a graph with a sign attached to each of its edges. Formally, a signed graphΓ
(
G
)
=
(
G
,
σ
) consists of a simple graph G
=
(
V
,
E
) which is regarded as its underlying graph, and a mapping σ
:
E
→
{
+
,
-
}, the edge labeling. To avoid confusion, we also write V
(
Γ
(
G
)
) instead of V, E
(
Γ
(
G
)
) instead of E, and E
(
Γ
(
G
)
)
=
E
σ.The adjacency matrix ofΓ
(
G
) is A
(
Γ
(
G
)
)
=
(
a
i
j
σ
) with a
i
j
σ
=
σ
(
v
i
v
j
)
a
i
j, where (
a
i
j
) is the adjacency matrix of the underlying graph G. In the case of σ
=
+, which is an all-positive edge labeling, A
(
G
,
+
) is exactly the classical adjacency matrix of G. So a simple graph is always assumed as a signed graph with all edges positive.The nullity of a signed graphΓ
(
G
) is defined as the multiplicity of the eigenvalue zero in the spectrum of A
(
Γ
(
G
)
), and is denoted by η
(
Γ
(
G
)
). The rank of Γ
(
G
) is referred to the rank of A
(
Γ
(
G
)
), and denoted by r
(
Γ
(
G
)
). Surely, η
(
Γ
(
G
)
)
+
r
(
Γ
(
G
)
)
=
n if Γ
(
G
) has n vertices.LetΓ
(
G
)
=
(
G
,
σ
) be a signed graph and let Γ
(
C
) be a signed cycle of Γ
(
G
). The sign of Γ
(
C
) is defined by sgn
⁡
(
Γ
(
C
)
)
=
∏
e
∈
Γ
(
C
)
σ
(
e
). The cycle Γ
(
C
) is said to be positive or negative if sgn
⁡
(
Γ
(
C
)
)
=
+ or sgn
⁡
(
Γ
(
C
)
)
=
-. A signed graph is said to be balanced if all its cycles are positive, or equivalently, all cycles have even number of negative edges; otherwise it is called unbalanced.About the nullity of simple graphs and its applications, there are many known results (see [1–8] for details). In 1953, Hurary [9] introduced the concept of a signed graph in connection with the study of the theory of social balance in social psychology. For more results of signed graphs and their applications, see [9–21].In this paper, we obtain the coefficients theorem of the characteristic polynomial of a signed graph and give two formulae on the nullity of signed graphs with cut-points. As applications of the above results, we investigate the nullity of the bicyclic signed graphΓ
(
∞
(
p
,
q
,
l
)
), obtain the nullity set of unbalanced bicyclic signed graphs, and thus determine the nullity set of bicyclic signed graphs.


## 2. The Coefficients ofP
Γ
(
G
)
(
λ
)

In this section, we obtain the coefficients theorem of the characteristic polynomial of a signed graphΓ
(
G
), P
Γ
(
G
)
(
λ
), and the nullity of a signed cycle Γ
(
C
n
) by using the coefficients theorem.Theorem 1 (see [11]).
Let(1)
P
G
(
λ
)
=
|
λ
I
n
-
A
|
=
λ
n
+
a
1
λ
n
-
1
+
⋯
+
a
n
be the characteristic polynomial of an arbitrary undirected weighted multigraph G.
Call an “elementary figure”: (a) the graphK
2 or (b) every graph C
q
(
q
≥
1
) (loops being included with q
=
1).
Call a basic figureU if all of its components are elementary figures; let p
(
U
) and c
(
U
) be the number of components and the number of cycles contained in U, respectively, and let 𝒰
i denote the set of all basic figures contained in G having exactly i vertices. Then for any i
∈
{
1,2
,
…
,
n
},
(2)
a
i
=
∑
U
∈
𝒰
i
(
-
1
)
p
(
U
)
·
2
c
(
U
)
·
∏
(
U
)
,
∏
(
U
)
=
∏
e
∈
E
(
U
)
‍
(
w
(
e
)
)
ξ
(
e
;
U
)
,
where E
(
U
) is the set of edges of U, w
(
e
) is the weight of the edge e, and
(3)
ξ
(
e
;
U
)
=
{
1
,
i
f
e
i
s
c
o
n
t
a
i
n
e
d
i
n
s
o
m
e
c
y
c
l
e
o
f
U
;
2
,
o
t
h
e
r
w
i
s
e
.Corollary 2.
LetΓ
(
G
) be a signed graph on n vertices and let
(4)
P
Γ
(
G
)
(
λ
)
=
|
λ
I
n
-
A
(
Γ
(
G
)
)
|
=
λ
n
+
a
1
λ
n
-
1
+
⋯
+
a
n
be the characteristic polynomial of A
(
Γ
(
G
)
). Then for any i
∈
{
1,2
,
…
,
n
},
(5)
a
i
=
∑
Γ
(
U
)
∈
Γ
(
𝒰
i
)
(
-
1
)
p
(
Γ
(
U
)
)
+
s
(
Γ
(
U
)
)
·
2
c
(
Γ
(
U
)
)
,
where s
(
Γ
(
U
)
) is the number of negative edges in cycle of Γ
(
U
); other notations are similar to Theorem 1.Proof.
SinceΓ
(
G
) is a signed graph, w
(
e
)
=
+
1 or -
1, then ∏
‍
(
Γ
(
U
)
)
=
∏
e
∈
E
(
Γ
(
U
)
)
(
-
1
)
s
(
Γ
(
U
)
). Thus the result follows from Theorem 1.Proposition 3.
(1) (see [11]). Let Γ
(
C
n
) be a balanced cycle. Then η
(
Γ
(
C
n
)
)
=
2 if n
≡
0
(
mod
⁡
4
) and η
(
Γ
(
C
n
)
)
=
0 otherwise.
(2) (see [13]). Let Γ
(
C
n
) be an unbalanced signed cycle. Then η
(
Γ
(
C
n
)
)
=
2 if n
≡
2
(
mod
⁡
4
) and η
(
Γ
(
C
n
)
)
=
0 otherwise.Lets
=
s
(
Γ
(
C
n
)
) be the number of negative edges of Γ
(
C
n
). It is clear that Γ
(
C
n
) is balanced if and only if s
≡
0
(
mod
⁡
2
); Γ
(
C
n
) is unbalanced if and only if s
≡
1
(
mod
⁡
2
). Then Proposition 3 is equivalent to Theorem 4. We will give a new proof by Corollary 2.Theorem 4.
LetΓ
(
C
n
)
=
(
C
n
,
σ
) be a signed cycle on n vertices, and s is the number of negative edges of Γ
(
C
n
). Then
(6)
η
(
Γ
(
C
n
)
)
=
{
2
,
i
f
n
≡
0
(
mod
⁡
4
)
,
s
≡
0
(
mod
⁡
2
)
;
2
,
i
f
n
≡
2
(
mod
⁡
4
)
,
s
≡
1
(
mod
⁡
2
)
;
0
,
i
f
n
≡
1
(
mod
⁡
2
)
;
0
,
i
f
n
≡
0
(
mod
⁡
4
)
,
s
≡
1
(
mod
⁡
2
)
;
0
,
i
f
n
≡
2
(
mod
⁡
4
)
,
s
≡
0
(
mod
⁡
2
)
.Proof.
By Corollary2, for any i
∈
{
1,2
,
…
,
n
}, we have
(7)
a
i
=
∑
Γ
(
U
)
∈
Γ
(
𝒰
i
)
(
-
1
)
p
(
Γ
(
U
)
)
+
s
(
Γ
(
U
)
)
·
2
c
(
Γ
(
U
)
)
.
Case
1.
n
≡
1
(
mod
⁡
2
).
Clearly,Γ
(
U
)
=
Γ
(
C
n
). Thus a
n
=
2
·
(
-
1
)
s
+
1
≠
0.
Case
2.
n
≡
0
(
mod
⁡
2
).
Clearly,Γ
(
U
)
=
Γ
(
C
n
) or Γ
(
U
)
=
(
n
/
2
)
Γ
(
K
2
), and there exist two basic figures (
n
/
2
)
Γ
(
K
2
) in Γ
(
C
n
). Then
(8)
a
n
=
2
·
(
-
1
)
s
+
1
+
2
·
(
-
1
)
n
/
2
=
{
0
,
if
n
≡
0
(
mod
⁡
4
)
,
s
≡
0
(
mod
⁡
2
)
;
4
,
if
n
≡
0
(
mod
⁡
4
)
,
s
≡
1
(
mod
⁡
2
)
;
-
4
,
if
n
≡
2
(
mod
⁡
4
)
,
s
≡
0
(
mod
⁡
2
)
;
0
,
if
n
≡
2
(
mod
⁡
4
)
,
s
≡
1
(
mod
⁡
2
)
.
If a
n
≠
0, then η
(
Γ
(
C
n
)
)
=
0.
Ifa
n
=
0, then we consider a
n
-
1 and a
n
-
2. Since n is even, it is clear that a
n
-
1
=
0 and a
n
-
2
≠
0 by Corollary 2. Thus η
(
Γ
(
C
n
)
)
=
2.Similarly, by Corollary2, we have the following.Proposition 5.
LetΓ
(
P
n
)
=
(
P
n
,
σ
) be a signed path on n vertices. Then
(9)
η
(
Γ
(
P
n
)
)
=
{
1
,
i
f
n
i
s
o
d
d
;
0
,
i
f
n
i
s
e
v
e
n
.


## 3. The Nullity of a Signed Graph with Cut-Points

In this section, we deduce two concise formulae on the nullity of signed graphs with cut-points by similar technique applied in [3].We first introduce some concepts and notations.LetG be a simple graph with vertex set V
=
V
(
G
). For a nonempty subset U of V, the subgraph with vertex set U and edge set consisting of those pairs of vertices that are edges in G is called the induced subgraph of G, denoted by G
[
U
]. Denote by G
-
U, where U
⊆
V, the graph obtained from G by removing the vertices of U together with all edges incident to them. Sometimes we use the notation G
-
G
1 instead of G
-
V
(
G
1
) if G
1 is an induced subgraph of G. For an induced subgraph G
1 (of G) and v
∈
G
-
G
1, the induced subgraph G
[
V
(
G
1
)
∪
{
v
}
] is simply written as G
1
+
v. The vertex v
∈
V is called a cut-point of G if the resultant graph G
-
v is disconnected.LetA be the adjacency matrix of a graph G
=
(
V
(
G
)
,
E
(
G
)
) on n vertices. For U
⊆
V
(
G
), W
⊆
V
(
G
), denoted by A
[
U
,
W
] is the submatrix of A with rows corresponding to the vertices of U and columns corresponding to the vertices of W. To simplify, the submatrix A
[
U
,
U
] is written as A
[
U
]. For convenience, we usually write A
[
G
1
,
G
2
] instead of the standard A
[
V
(
G
1
)
,
V
(
G
2
)
] for the two induced subgraphs G
1 and G
2 of G. In particular, denoted by A
[
v
,
G
] is the row vector of A corresponding to the vertex v and by A
[
v
,
G
i
] is the subvector of A
[
v
,
G
] corresponding to the vertices of G
i. We refer to Cvetković et al. [11] for more terminologies and notations not defined here.The following lemma is obvious.Lemma 6.
LetG
=
G
1
∪
G
2
∪
⋯
∪
G
s and Γ
(
G
) be a signed graph, where G
1
,
G
2
,
…
,
G
s are the connected components of G. Then Γ
(
G
1
)
,
Γ
(
G
2
)
,
…
,
Γ
(
G
s
) are the connected components of Γ
(
G
), r
(
Γ
(
G
)
)
=
∑
i
=
1
s
r
(
Γ
(
G
i
)
), and η
(
Γ
(
G
)
)
=
∑
i
=
1
s
η
(
Γ
(
G
i
)
).Theorem 7.
LetΓ
(
G
) be a connected signed graph on n vertices, let v be a cut-point of Γ
(
G
), and let Γ
(
G
1
)
,
Γ
(
G
2
)
,
…
,
Γ
(
G
s
) be all the components of Γ
(
G
-
v
). If there exists a component, say Γ
(
G
1
), among Γ
(
G
1
)
,
Γ
(
G
2
)
,
…
,
Γ
(
G
s
) such that η
(
Γ
(
G
1
)
)
=
η
(
Γ
(
G
1
+
v
)
)
+
1, then η
(
Γ
(
G
)
)
=
η
(
Γ
(
G
-
v
)
)
-
1
=
∑
i
=
1
s
η
(
Γ
(
G
i
)
)
-
1.Proof.
LetA
=
A
(
Γ
(
G
)
) be the adjacency matrix of Γ
(
G
). For each i, denote by A
[
Γ
(
G
i
)
] the adjacency matrix of the subgraph Γ
(
G
i
) and by A
[
v
,
Γ
(
G
i
)
] the subvector of A
[
v
,
Γ
(
G
)
] corresponding to the vertices of Γ
(
G
i
); then the matrix A can be partitioned as follows:
(10)
[
0
A
[
v
,
Γ
(
G
1
)
]
A
[
v
,
Γ
(
G
2
)
]
⋯
A
[
v
,
Γ
(
G
s
)
]
A
[
Γ
(
G
1
)
,
v
]
A
[
Γ
(
G
1
)
]
0
⋯
0
A
[
Γ
(
G
2
)
,
v
]
0
A
[
Γ
(
G
2
)
]
⋯
0
⋯
⋯
⋯
⋯
⋯
A
[
Γ
(
G
s
)
,
v
]
0
0
⋯
A
[
Γ
(
G
s
)
]
]
,
where A
[
Γ
(
G
i
)
,
v
]
=
A
[
v
,
Γ
(
G
i
)
]
T
(
i
=
1,2
,
…
,
s
), the transpose of A
[
v
,
Γ
(
G
i
)
], for each i.
Note thatη
(
Γ
(
G
1
)
)
=
η
(
Γ
(
G
1
+
v
)
)
+
1, then r
(
Γ
(
G
1
+
v
)
)
=
r
(
Γ
(
G
1
)
)
+
2, thus the row vector A
[
v
,
Γ
(
G
1
)
] is not linear combination of the row vectors of A
[
Γ
(
G
1
)
], therefore the row vector A
[
v
,
Γ
(
G
)
] is not linear combination of any other row vectors of A
[
Γ
(
G
)
]. Since A is a symmetric matrix, the column vector A
[
Γ
(
G
)
,
v
] is not linear combination of any other column vectors of A, which implies that r
(
Γ
(
G
)
)
=
r
(
Γ
(
G
-
v
)
)
+
2. Then by Lemma 6,
(11)
η
(
Γ
(
G
)
)
=
n
-
r
(
Γ
(
G
)
)
=
n
-
r
(
Γ
(
G
-
v
)
)
-
2
=
η
(
Γ
(
G
-
v
)
)
-
1
=
∑
i
=
1
s
η
(
Γ
(
G
i
)
)
-
1
.Theorem 8.
LetΓ
(
G
) be a connected signed graph on n vertices, let v be a cut-point of Γ
(
G
), and let Γ
(
G
1
) be a component of Γ
(
G
-
v
). If η
(
Γ
(
G
1
)
)
=
η
(
Γ
(
G
1
+
v
)
)
-
1, then η
(
Γ
(
G
)
)
=
η
(
Γ
(
G
1
)
)
+
η
(
Γ
(
G
-
G
1
)
).Proof.
LetA
=
A
(
Γ
(
G
)
) be the adjacency matrix of Γ
(
G
). Then
(12)
A
=
[
A
[
Γ
(
G
1
)
]
A
[
Γ
(
G
1
)
,
v
]
0
A
[
v
,
Γ
(
G
1
)
]
0
A
[
v
,
Γ
(
G
-
G
1
-
v
)
]
0
A
[
Γ
(
G
-
G
1
-
v
)
,
v
]
A
[
Γ
(
G
-
G
1
-
v
)
]
]
.
Becauseη
(
Γ
(
G
1
)
)
=
η
(
Γ
(
G
1
+
v
)
)
-
1, r
(
Γ
(
G
1
+
v
)
)
=
r
(
Γ
(
G
1
)
) and thus the row vector A
[
v
,
Γ
(
G
1
+
v
)
]
=
[
A
[
v
,
Γ
(
G
1
)
]  0
] is linear combination of the row vectors of A
[
Γ
(
G
1
)
,
Γ
(
G
1
+
v
)
]. Similarly, the column vector A
[
Γ
(
G
1
+
v
)
,
v
] is linear combination of the column vectors of A
[
Γ
(
G
1
+
v
)
,
Γ
(
G
1
)
]. Thus B can be obtained from A by row and column linear transformations, where
(13)
B
=
[
A
[
Γ
(
G
1
)
]
0
0
0
0
A
[
v
,
Γ
(
G
-
G
1
-
v
)
]
0
A
[
Γ
(
G
-
G
1
-
v
)
,
v
]
A
[
Γ
(
G
-
G
1
-
v
)
]
]
.
It is easy to see that B is the adjacency matrix of the union of Γ
(
G
1
) and Γ
(
G
-
G
1
). Then we have r
(
A
)
=
r
(
B
), which implies that η
(
Γ
(
G
)
)
=
n
-
r
(
A
)
=
n
-
r
(
B
)
=
η
(
B
)
=
η
(
Γ
(
G
1
)
)
+
η
(
Γ
(
G
-
G
1
)
).


## 4. The Nullity of the Bicyclic Signed GraphΓ
(
∞
(
p
,
q
,
l
)
)

Firstly, we introduce some definitions and notations which will be used in the following.A bicyclic graph is a simple connected graph in which the number of edges equals the number of vertices plus one. There are two basic bicyclic graphs:∞-graph and Θ-graph. An ∞-graph, denoted by ∞
(
p
,
q
,
l
), is obtained from two vertex-disjoint cycles C
p and C
q by connecting one vertex of C
p and one of C
q with a path P
l of length l
-
1 (in the case of l
=
1, identifying the above two vertices); and a Θ-graph, denoted by Θ
(
p
,
q
,
l
), is a union of three internally disjoint paths P
p
+
1
,
P
q
+
1
,
P
l
+
1 of length p
,
q
,
l, respectively, with common end vertices, where p
,
q
,
l
≥
1 and at most one of them is 1. Observe that any bicyclic graph G is obtained from an ∞-graph or a Θ-graph (possibly) by attaching trees to some of its vertices.Lemma 9 (see [13]).
LetΓ
(
G
) be a signed graph containing a pendant vertex, and let Γ
(
H
) be the induced subgraph of Γ
(
G
) obtained by deleting this pendant vertex together with the vertex adjacent to it. Then η
(
Γ
(
G
)
)
=
η
(
Γ
(
H
)
).Theorem 10.
Letp
,
q
,
l be integers with p
,
q
≥
3
,
l
≥
1, and G
=
∞
(
p
,
q
,
l
).(1)
Ifp and q are odd, then
(14)
η
(
Γ
(
G
)
)
=
{
0
,
i
f
l
i
s
e
v
e
n
;
0
,
i
f
l
i
s
o
d
d
a
n
d
s
(
Γ
(
C
p
)
)
-
s
(
Γ
(
C
q
)
)
+
q
-
p
2
≡
0
(
mod
⁡
2
)
;
1
,
i
f
l
=
1
a
n
d
s
(
Γ
(
C
p
)
)
-
s
(
Γ
(
C
q
)
)
+
q
-
p
2
≡
1
(
mod
⁡
2
)
;
≥
1
,
i
f
l
(
≥
3
)
i
s
o
d
d
a
n
d
s
(
Γ
(
C
p
)
)
-
s
(
Γ
(
C
q
)
)
+
q
-
p
2
≡
1
(
mod
⁡
2
)
.
(2)
Ifp and q have different parities, without loss of generality, let p be even; then
(15)
η
(
Γ
(
G
)
)
=
{


0
,
i
f
η
(
Γ
(
C
p
)
)
=
0
;
1
,
i
f
η
(
Γ
(
C
p
)
)
=
2
.
(3)
Ifp and q are even, then
(16)
η
(
Γ
(
G
)
)
=
{
3
,
i
f
l
i
s
o
d
d
,
η
(
Γ
(
C
p
)
)
=
η
(
Γ
(
C
q
)
)
=
2
;
1
,
i
f
l
i
s
o
d
d
,
η
(
Γ
(
C
p
)
)
·
η
(
Γ
(
C
q
)
)
=
0
;
2
,
i
f
l
i
s
e
v
e
n
,
η
(
Γ
(
C
p
)
)
=
2
o
r
η
(
Γ
(
C
q
)
)
=
2
;
0
,
i
f
l
i
s
e
v
e
n
,
η
(
Γ
(
C
p
)
)
=
η
(
Γ
(
C
q
)
)
=
0
.Proof.
The proof is as follows.
Case
1 (both p and q are odd). By Corollary 2, we know
(17)
a
i
=
∑
Γ
(
U
)
∈
Γ
(
𝒰
i
)
(
-
1
)
p
(
Γ
(
U
)
)
+
s
(
Γ
(
U
)
)
·
2
c
(
Γ
(
U
)
)
∑
Γ
(
U
)
∈
Γ
(
𝒰
i
)
(
-
1
)
p
(
Γ
(
U
)
)
+
s
(
Γ
(
U
)
)
(
i
=
1,2
,
…
n
)
.
Subcase
1.1 (l is even). Consider
(18)
a
n
=
(
-
1
)
s
(
Γ
(
C
p
)
)
+
s
(
Γ
(
C
q
)
)
+
(
(
l
+
2
)
/
2
)
×
2
2
+
(
-
1
)
(
(
(
p
-
1
)
/
2
)
+
(
(
q
-
1
)
/
2
)
+
(
l
/
2
)
)
×
2
0
≠
0
.
So η
(
Γ
(
G
)
)
=
0.
Subcase
1.2 (l is odd). 							(19)
a
n
=
(
-
1
)
s
(
Γ
(
C
p
)
)
+
(
(
l
+
q
)
/
2
)
×
2
1
+
(
-
1
)
s
(
Γ
(
C
q
)
)
+
(
(
l
+
p
)
/
2
)
×
2
1
,
a
n
=
0
,
if
s
(
Γ
(
C
p
)
)
-
s
(
Γ
(
C
q
)
)
+
q
-
p
2
≡
1
(
mod
⁡
2
)
;
a
n
≠
0
,
if
s
(
Γ
(
C
p
)
)
-
s
(
Γ
(
C
q
)
)
+
q
-
p
2
≡
0
(
mod
⁡
2
)
.
Clearly, ifa
n
≠
0, η
(
Γ
(
G
)
)
=
0; a
n
=
0, η
(
Γ
(
G
)
)
≥
1. It is obvious that a
n
-
1
≠
0 when l
=
1; thus η
(
Γ
(
G
)
)
=
1 when l
=
1.
Case
2 (p is even). Let v be the vertex of Γ
(
G
) joining Γ
(
C
p
) and Γ
(
P
l
), then v is a cut-point of Γ
(
G
). Note that η
(
Γ
(
C
p
-
v
)
)
=
η
(
Γ
(
P
p
-
1
)
)
=
1 by Proposition 5 and η
(
Γ
(
C
p
)
)
=
2 or 0 by Theorem 4.
Subcase
2.1 (η
(
Γ
(
C
p
)
)
=
0). It is clear that η
(
Γ
(
C
p
-
v
)
)
=
η
(
Γ
(
C
p
)
)
+
1. Then by Theorem 7 and Lemma 9,
(20)
η
(
Γ
(
G
)
)
=
η
(
Γ
(
G
-
v
)
)
-
1
=
η
(
Γ
(
C
p
-
v
)
)
+
η
(
Γ
(
G
-
C
p
)
)
-
1
=
η
(
Γ
(
G
-
C
p
)
)
=
{
η
(
Γ
(
P
q
-
1
)
)
,
if
l
is
odd
;
η
(
Γ
(
C
q
)
)
,
if
l
is
even
.
Subcase
2.2 (η
(
Γ
(
C
p
)
)
=
2). It is clear that η
(
Γ
(
C
p
-
v
)
)
=
η
(
Γ
(
C
p
)
)
-
1. Then by Theorem 8 and Lemma 9,
(21)
η
(
Γ
(
G
)
)
=
η
(
Γ
(
C
p
-
v
)
)
+
η
(
Γ
(
G
-
C
p
+
v
)
)
=
1
+
η
(
Γ
(
G
-
C
p
+
v
)
)
=
{
1
+
η
(
Γ
(
C
q
)
)
,
if
l
is
odd
;
1
+
η
(
Γ
(
P
q
-
1
)
)
,
if
l
is
even
.
By Theorem4,
(22)
η
(
Γ
(
C
q
)
)
=
{
0
,
if
q
is
odd
;
0
or
2
,
if
q
is
even
.
Then by Proposition 5 and previous arguments, (2) and (3) hold.


## 5. The Nullity Set of Bicyclic Signed Graphs

Denoted byℬ
n is the set of all bicyclic graphs on n vertices. Obviously, ℬ
n consists of three types of graphs: first type denoted by B
n
+ is the set of those graphs each of which is an ∞-graph, ∞
(
p
,
q
,
l
), with trees attached when l
>
1; second type denoted by B
n
+
+ is the set of those graphs each of which is an ∞-graph, ∞
(
p
,
q
,
l
), with trees attached when l
=
1; third type denoted by Θ
n is the set of those graphs each of which is a Θ-graph, Θ
(
p
,
q
,
l
), with trees attached. Then ℬ
n
=
B
n
+
∪
B
n
+
+
∪
Θ
n.LetΓ
(
ℬ
n
) be the set of all bicyclic signed graphs on n vertices. Clearly, Γ
(
ℬ
n
)
=
Γ
(
B
n
+
)
∪
Γ
(
B
n
+
+
)
∪
Γ
(
Θ
n
).LetΓ
(
G
)
=
(
G
,
σ
) be a signed graph on n vertices. Suppose θ
:
V
(
G
)
→
{
+
,
-
} is a sign function. Switching Γ
(
G
) by θ means forming a new signed graph Γ
(
G
)
θ
=
(
G
,
σ
θ
) whose underlying graph is the same as G, but whose sign function is defined on an edge u
v by σ
θ
(
u
v
)
=
θ
(
u
)
σ
(
u
v
)
θ
(
v
). Note that switching does not change the signs or balance of the cycles of Γ
(
G
). If we define a diagonal signature matrix D
θ
=
diag
⁡
(
d
1
,
d
2
,
…
,
d
n
) with d
i
=
θ
(
v
i
) for each v
i
∈
V
(
G
), then A
(
Γ
(
G
)
θ
)
=
D
θ
A
(
Γ
(
G
)
)
D
θ. Two graphs, Γ
1
(
G
) and Γ
2
(
G
) are called switching equivalent, denoted by Γ
1
(
G
)
~
Γ
2
(
G
), if there exists a switching function θ such that Γ
2
(
G
)
=
Γ
1
θ
(
G
), or equivalently, A
(
Γ
2
(
G
)
)
=
D
θ
A
(
Γ
1
(
G
)
)
D
θ.Theorem 11 (see [16]).
LetΓ
(
G
)
=
(
G
,
σ
) be a signed graph. Then Γ
(
G
) is balanced if and only if Γ
(
G
)
=
(
G
,
σ
)
~
(
G
,
+
).Note that switching equivalence is a relation of equivalence, and two switching equivalent graphs have the same nullity. Therefore, when we discuss the nullity of signed graphs, we can choose an arbitrary representative of each switching equivalent class. If a signed graph is balanced, by Theorem11, it is switching equivalent to one with all edges positive, that is, the underlying graph. Thus we only need to consider the case of unbalanced.Hu et al. [6], Li et al. [7] characterize the maximal nullity of bicyclic graphs and determine the the nullity set of ℬ
n. Recently, Fan et al. [14] characterize the maximal, the second maximal nullity of bicyclic signed graphs.Theorem 12 (see [7]).
Letn be a positive integer, [
0
,
n
]
=
{
0,1
,
2
,
…
,
n
}. Then(1)
letn
≥
7, the nullity set of B
n
+ is [
0
,
n
-
6
];
(2)
letn
≥
8, the nullity set of B
n
+
+ is [
0
,
n
-
6
];
(3)
letn
≥
6, the nullity set of Θ
n is [
0
,
n
-
4
].In Section5.1–Section 5.3, we firstly obtain an upper bound of the nullity of bicyclic signed graphs in Γ
(
B
n
+
) and Γ
(
B
n
+
+
), and then we obtain the nullity set of unbalanced bicyclic signed graphs in Γ
(
B
n
+
), Γ
(
B
n
+
+
), Γ
(
Θ
n
), respectively, and determine the nullity set of (unbalanced) bicyclic signed graphs.


### 5.1. The Nullity Set of Unbalanced Bicyclic Signed Graphs inΓ
(
B
n
+
)

Theorem 13.
Letn
≥
7, Γ
(
G
)
∈
Γ
(
B
n
+
). Then η
(
Γ
(
G
)
)
≤
n
-
6.Proof.
LetG
∈
B
n
+ be a bicyclic graph with trees attached on an ∞-graph, ∞
(
p
,
q
,
l
), where p
,
q
≥
3
,
l
≥
2.
Case
1 (p
,
q
∈
{
3,4
}). Consider the following subcases.
Subcase
1.1 (p
=
q
=
4). Note that
(23)
p
+
q
+
l
-
2
=
6
+
l
≥
{
9
,
if
l
is
odd
;
8
,
if
l
is
even
.
Then by (3) of Theorem 10, r
(
Γ
(
∞
(
4,4
,
l
)
)
)
≥
6.
Clearly,∞
(
4,4
,
l
) is an induced subgraph of G; then r
(
Γ
(
G
)
)
≥
r
(
Γ
(
∞
(
4,4
,
l
)
)
)
≥
6. Therefore η
(
Γ
(
G
)
)
≤
n
-
6.
Subcase
1.2 (p
≠
4 or q
≠
4). In this case, there must exist a graph H on 6 vertices as an induced subgraph of G, where H
=
H
1 or H
=
H
2, shown in Figure 1. By Lemma 9 repeatedly we obtain η
(
Γ
(
H
1
)
)
=
η
(
Γ
(
H
2
)
)
=
0, then r
(
Γ
(
H
1
)
)
=
r
(
Γ
(
H
2
)
)
=
6. Thus r
(
Γ
(
G
)
)
≥
r
(
Γ
(
H
)
)
≥
6 and η
(
Γ
(
G
)
)
≤
n
-
6.
Case
2 (p
≥
5 or q
≥
5). Without loss of generality, we assume that p
≥
5. There must exist a graph H
3 on p
+
1 vertices shown in Figure 1 as an induced subgraph of G. By Lemma 9 and Proposition 5, it is easy to check that
(24)
η
(
Γ
(
H
3
)
)
=
{
0
,
if
p
is
odd
;
1
,
if
p
is
even
.
Hence
(25)
r
(
Γ
(
H
3
)
)
=
{
p
+
1
,
if
p
is
odd
;
p
,
if
p
is
even
.
Since p
≥
5, r
(
Γ
(
H
3
)
)
≥
6. Then r
(
Γ
(
G
)
)
≥
r
(
Γ
(
H
3
)
)
≥
6. Thus η
(
Γ
(
G
)
)
≤
n
-
6.Figure 1Theorem 14.
Letn
≥
7. Then the nullity set of unbalanced bicyclic signed graphs in Γ
(
B
n
+
) is [
0
,
n
-
6
].Proof.
It suffices to show that for eachk
∈
[
0
,
n
-
6
], there exists an unbalanced bicyclic signed graph Γ
(
G
)
∈
Γ
(
B
n
+
) such that η
(
Γ
(
G
)
)
=
k.
Case
1
(
k
=
0
). It is clear that there exists an unbalanced bicyclic signed graph Γ
(
G
)
=
Γ
(
∞
(
p
,
q
,
l
)
)
∈
Γ
(
B
n
+
) satisfying η
(
Γ
(
G
)
)
=
0 by Theorem 10, where p
,
q
≥
3
,
l
≥
2.
Case
2(k
=
n
-
6). Let G
=
G
1 shown in Figure 2, where Γ
(
G
1
) contains a balanced quadrangle and an unbalanced triangle. Thus η
(
Γ
(
C
4
)
)
=
2 by Theorem 4.
Ifn
=
7, then G
=
∞
(
3,4
,
2
) and η
(
Γ
(
G
)
)
=
1
=
n
-
6 by (2) of Theorem 10.
Ifn
≥
8, then by Lemmas 9 and 6, we have η
(
Γ
(
G
)
)
=
η
(
Γ
(
P
2
)
∪
Γ
(
C
4
)
∪
(
n
-
8
)
Γ
(
K
1
)
)
=
η
(
Γ
(
P
2
)
)
+
η
(
Γ
(
C
4
)
)
+
(
n
-
8
)
η
(
Γ
(
K
1
)
)
=
0
+
2
+
(
n
-
8
)
=
n
-
6.
Case
3
(
1
≤
k
≤
n
-
7
). Let G
=
G
2 shown in Figure 2, where Γ
(
G
2
) contains two unbalanced triangles. By using Lemma 9 repeatedly, after [
(
n
-
k
-
4
)
/
2
] steps, we have
(26)
η
(
Γ
(
G
)
)
=
{
η
(
Γ
(
P
2
)
∪
Γ
(
C
3
)
∪
k
Γ
(
K
1
)
)
,
if
n
-
k
is
odd
;
η
(
2
Γ
(
P
2
)
∪
k
Γ
(
K
1
)
)
,
if
n
-
k
is
even
.
Hence by Lemma6,
(27)
η
(
Γ
(
G
)
)
=
{
η
(
Γ
(
P
2
)
)
+
η
(
Γ
(
C
3
)
)
+
k
η
(
Γ
(
K
1
)
)
=
0
+
0
+
k
=
k
,
if
n
-
k
is
odd
;
2
η
(
Γ
(
P
2
)
)
+
k
η
(
Γ
(
K
1
)
)
=
0
+
k
=
k
,
if
n
-
k
is
even
.Figure 2


### 5.2. The Nullity Set of Unbalanced Bicyclic Signed Graphs inΓ
(
B
n
+
+
)

Theorem 15.
Letn
≥
8, Γ
(
G
)
∈
Γ
(
B
n
+
+
). Then η
(
Γ
(
G
)
)
≤
n
-
6.Proof.
LetG
∈
B
n
+
+ be a bicyclic graph with trees attached on an ∞-graph, ∞
(
p
,
q
,
1
), where p
,
q
≥
3.
Case
1 (p
,
q
∈
{
3,4
}). In this case, there must exist a graph H on h vertices as an induced subgraph of G, where H
=
H
4
,
H
5 with h
=
6, or H
=
H
6
,
H
7
,
H
8
,
H
9 with h
=
7, or H
=
H
10
,
H
11
,
H
12 with h
=
8 shown in Figure 3. By Lemma 9 repeatedly and Theorem 4, we obtain η
(
Γ
(
H
4
)
)
=
η
(
Γ
(
H
5
)
)
=
η
(
Γ
(
H
8
)
)
=
0, η
(
Γ
(
H
6
)
)
=
η
(
Γ
(
H
7
)
)
=
η
(
Γ
(
H
9
)
)
=
1, η
(
Γ
(
H
11
)
)
=
η
(
Γ
(
H
12
)
)
=
2, and let Γ
(
C
4
) be the quadrangle containing no pendent edge of Γ
(
H
10
); we have
(28)
η
(
Γ
(
H
10
)
)
=
{
2
,
if
Γ
(
C
4
)
is
balanced
;
0
,
if
Γ
(
C
4
)
is
unbalanced
.
Hence for eachΓ
(
H
i
)
(
i
=
4,5
,
…
,
12
), we have r
(
Γ
(
H
i
)
)
≥
6, so r
(
Γ
(
G
)
)
≥
r
(
Γ
(
H
i
)
)
≥
6. Thus η
(
Γ
(
G
)
)
≤
n
-
6.
Case
2 (p
≥
5 or q
≥
5). Without loss of generality, we assume that p
≥
5. There must exist a graph H
3 on p
+
1 vertices shown in Figure 1 as an induced subgraph of G. Similar to the proof of Case 2 in Theorem 13, we have r
(
Γ
(
H
3
)
)
≥
6. Then r
(
Γ
(
G
)
)
≥
r
(
Γ
(
H
3
)
)
≥
6 and thus η
(
Γ
(
G
)
)
≤
n
-
6.Figure 3Lemma 16 (see [14]).
LetH
13 be a graph on 5 vertices as shown in Figure 4, and the two triangles of Γ
(
H
13
) have the same balance. Then η
(
Γ
(
H
13
)
)
=
n
-
5
=
0.Figure 4Theorem 17.
Letn
≥
8; then the nullity set of unbalanced bicyclic signed graphs in Γ
(
B
n
+
+
) is [
0
,
n
-
6
].Proof.
It suffices to show that for eachk
∈
[
0
,
n
-
6
], there exists an unbalanced bicyclic signed graph Γ
(
G
)
∈
Γ
(
B
n
+
+
) such that η
(
Γ
(
G
)
)
=
k.
Case
1 (k
=
0). It is clear that there exists an unbalanced bicyclic signed graph Γ
(
G
)
=
Γ
(
∞
(
p
,
q
,
1
)
)
∈
Γ
(
B
n
+
+
) satisfying η
(
Γ
(
G
)
)
=
0 by Theorem 10, where p
,
q
≥
3.
Case
2 (k
=
n
-
6). Let G
=
G
3 shown in Figure 4, where the two triangles of Γ
(
G
3
) are unbalanced. Then by Lemmas 9 and 6, we have η
(
Γ
(
G
)
)
=
η
(
Γ
(
P
2
)
∪
(
n
-
6
)
Γ
(
K
1
)
)
=
η
(
Γ
(
P
2
)
)
+
(
n
-
6
)
η
(
Γ
(
K
1
)
)
=
0
+
(
n
-
6
)
=
n
-
6.
Case
3 (1
≤
k
≤
n
-
7). Let G
=
G
4 shown in Figure 5, where the two triangles of Γ
(
G
4
) are unbalanced.
Subcase
3.1 (n
-
k is odd). By using Lemma 9 repeatedly, after (
n
-
k
-
5
)
/
2 steps, we obtain the graph k
Γ
(
K
1
)
∪
Γ
(
H
13
), where the two triangles of Γ
(
H
13
) are unbalanced. Hence η
(
Γ
(
G
)
)
=
η
(
k
Γ
(
K
1
)
∪
Γ
(
H
13
)
)
=
η
(
k
Γ
(
K
1
)
)
+
η
(
Γ
(
H
13
)
)
=
k
+
0
=
k by Lemma 16.
Subcase
3.2 (n
-
k is even). By using Lemma 9 repeatedly, after (
n
-
k
-
2
)
/
2 steps, we obtain the graph k
Γ
(
K
1
)
∪
Γ
(
P
2
). Hence η
(
Γ
(
G
)
)
=
η
(
k
Γ
(
K
1
)
∪
Γ
(
P
2
)
)
=
η
(
k
Γ
(
K
1
)
)
+
η
(
Γ
(
P
2
)
)
=
k
+
0
=
k.Figure 5


### 5.3. The Nullity Set of Unbalanced Bicyclic Signed Graphs inΓ
(
Θ
n
)

Lemma 18 (see [14]).
LetΓ
(
G
) be an unbalanced bicyclic signed graph on n vertices. Then η
(
Γ
(
G
)
)
≤
n
-
3, with equality if and only if Γ
(
G
)
=
Γ
(
Θ
(
2,2
,
1
)
) and the two triangles of Γ
(
Θ
(
2,2
,
1
)
) are both unbalanced.By Lemma18, we obtain the following result immediately.Proposition 19.
Letn
≥
5 and let Γ
(
G
) be an unbalanced bicyclic signed graph in Γ
(
Θ
n
). Then η
(
Γ
(
G
)
)
≤
n
-
4.Theorem 20.
Letn
≥
6. Then the nullity set of unbalanced bicyclic signed graphs in Γ
(
Θ
n
) is [
0
,
n
-
4
].Proof.
It suffices to show that for eachk
∈
[
0
,
n
-
4
], there exists an unbalanced bicyclic signed graph Γ
(
G
)
∈
Γ
(
Θ
n
) such that η
(
Γ
(
G
)
)
=
k.
Case
1 (k
=
0). Let G
=
G
5 shown in Figure 6, where Γ
(
G
5
) contains at least an unbalanced triangle. By Lemma 9 and Theorem 4 (when n is odd) or Proposition 5 (when n is even), we have η
(
Γ
(
G
)
)
=
0.
Case
2 (k
=
n
-
4). Let G
=
G
6 shown in Figure 6, where Γ
(
G
6
) contains at least an unbalanced triangle. By Lemma 9 and Proposition 5, we have η
(
Γ
(
G
)
)
=
η
(
Γ
(
P
3
)
∪
(
n
-
5
)
Γ
(
K
1
)
)
=
η
(
Γ
(
P
3
)
)
+
(
n
-
5
)
η
(
Γ
(
K
1
)
)
=
1
+
(
n
-
5
)
=
n
-
4.
Case
3 (1
≤
k
≤
n
-
5). Consider the following subcases.
Subcase
3.1 (n
-
k is odd). Let G
=
G
7 shown in Figure 6, where the two triangles of G
7 are unbalanced. By using Lemma 9 repeatedly, after (
n
-
k
-
3
)
/
2 steps, we obtain the graph Γ
(
Θ
(
2,2
,
1
)
)
∪
(
k
-
1
)
Γ
(
K
1
). Hence η
(
Γ
(
G
)
)
=
η
(
Γ
(
Θ
(
2,2
,
1
)
)
∪
(
k
-
1
)
Γ
(
K
1
)
)
=
η
(
Γ
(
Θ
(
2,2
,
1
)
)
)
+
(
k
-
1
)
η
(
Γ
(
K
1
)
)
=
1
+
(
k
-
1
)
=
k by Lemmas 9 and 18.
Subcase
3.2 (n
-
k is even). Let G
=
G
8 shown in Figure 6, where the triangle of G
8 is unbalanced and the quadrangle is balanced. By using Lemma 9 repeatedly, after (
n
-
k
-
2
)
/
2 steps, we obtain the graph Γ
(
C
4
)
∪
(
k
-
2
)
Γ
(
K
1
). Hence η
(
Γ
(
G
)
)
=
η
(
Γ
(
C
4
)
∪
(
k
-
2
)
Γ
(
K
1
)
)
=
η
(
Γ
(
C
4
)
)
+
(
k
-
2
)
η
(
Γ
(
K
1
)
)
=
2
+
(
k
-
2
)
=
k by Lemma 9 and Theorem 4.Figure 6


### 5.4. In Conclusion

From the above discussion, by Theorems12, 14, 17 and 20 we can obtain the following results immediately.Theorem 21.
Letn
≥
8. Then the nullity set of unbalanced bicyclic signed graphs is [
0
,
n
-
4
].Theorem 22.
Letn
≥
8. Then the nullity set of bicyclic signed graphs is [
0
,
n
-
4
].When4
≤
n
≤
7, the nullity set of bicyclic signed graphs is easy to obtain by known results and direct calculation, so we omit it.


## 5.1. The Nullity Set of Unbalanced Bicyclic Signed Graphs inΓ
(
B
n
+
)

Theorem 13.
Letn
≥
7, Γ
(
G
)
∈
Γ
(
B
n
+
). Then η
(
Γ
(
G
)
)
≤
n
-
6.Proof.
LetG
∈
B
n
+ be a bicyclic graph with trees attached on an ∞-graph, ∞
(
p
,
q
,
l
), where p
,
q
≥
3
,
l
≥
2.
Case
1 (p
,
q
∈
{
3,4
}). Consider the following subcases.
Subcase
1.1 (p
=
q
=
4). Note that
(23)
p
+
q
+
l
-
2
=
6
+
l
≥
{
9
,
if
l
is
odd
;
8
,
if
l
is
even
.
Then by (3) of Theorem 10, r
(
Γ
(
∞
(
4,4
,
l
)
)
)
≥
6.
Clearly,∞
(
4,4
,
l
) is an induced subgraph of G; then r
(
Γ
(
G
)
)
≥
r
(
Γ
(
∞
(
4,4
,
l
)
)
)
≥
6. Therefore η
(
Γ
(
G
)
)
≤
n
-
6.
Subcase
1.2 (p
≠
4 or q
≠
4). In this case, there must exist a graph H on 6 vertices as an induced subgraph of G, where H
=
H
1 or H
=
H
2, shown in Figure 1. By Lemma 9 repeatedly we obtain η
(
Γ
(
H
1
)
)
=
η
(
Γ
(
H
2
)
)
=
0, then r
(
Γ
(
H
1
)
)
=
r
(
Γ
(
H
2
)
)
=
6. Thus r
(
Γ
(
G
)
)
≥
r
(
Γ
(
H
)
)
≥
6 and η
(
Γ
(
G
)
)
≤
n
-
6.
Case
2 (p
≥
5 or q
≥
5). Without loss of generality, we assume that p
≥
5. There must exist a graph H
3 on p
+
1 vertices shown in Figure 1 as an induced subgraph of G. By Lemma 9 and Proposition 5, it is easy to check that
(24)
η
(
Γ
(
H
3
)
)
=
{
0
,
if
p
is
odd
;
1
,
if
p
is
even
.
Hence
(25)
r
(
Γ
(
H
3
)
)
=
{
p
+
1
,
if
p
is
odd
;
p
,
if
p
is
even
.
Since p
≥
5, r
(
Γ
(
H
3
)
)
≥
6. Then r
(
Γ
(
G
)
)
≥
r
(
Γ
(
H
3
)
)
≥
6. Thus η
(
Γ
(
G
)
)
≤
n
-
6.Figure 1Theorem 14.
Letn
≥
7. Then the nullity set of unbalanced bicyclic signed graphs in Γ
(
B
n
+
) is [
0
,
n
-
6
].Proof.
It suffices to show that for eachk
∈
[
0
,
n
-
6
], there exists an unbalanced bicyclic signed graph Γ
(
G
)
∈
Γ
(
B
n
+
) such that η
(
Γ
(
G
)
)
=
k.
Case
1
(
k
=
0
). It is clear that there exists an unbalanced bicyclic signed graph Γ
(
G
)
=
Γ
(
∞
(
p
,
q
,
l
)
)
∈
Γ
(
B
n
+
) satisfying η
(
Γ
(
G
)
)
=
0 by Theorem 10, where p
,
q
≥
3
,
l
≥
2.
Case
2(k
=
n
-
6). Let G
=
G
1 shown in Figure 2, where Γ
(
G
1
) contains a balanced quadrangle and an unbalanced triangle. Thus η
(
Γ
(
C
4
)
)
=
2 by Theorem 4.
Ifn
=
7, then G
=
∞
(
3,4
,
2
) and η
(
Γ
(
G
)
)
=
1
=
n
-
6 by (2) of Theorem 10.
Ifn
≥
8, then by Lemmas 9 and 6, we have η
(
Γ
(
G
)
)
=
η
(
Γ
(
P
2
)
∪
Γ
(
C
4
)
∪
(
n
-
8
)
Γ
(
K
1
)
)
=
η
(
Γ
(
P
2
)
)
+
η
(
Γ
(
C
4
)
)
+
(
n
-
8
)
η
(
Γ
(
K
1
)
)
=
0
+
2
+
(
n
-
8
)
=
n
-
6.
Case
3
(
1
≤
k
≤
n
-
7
). Let G
=
G
2 shown in Figure 2, where Γ
(
G
2
) contains two unbalanced triangles. By using Lemma 9 repeatedly, after [
(
n
-
k
-
4
)
/
2
] steps, we have
(26)
η
(
Γ
(
G
)
)
=
{
η
(
Γ
(
P
2
)
∪
Γ
(
C
3
)
∪
k
Γ
(
K
1
)
)
,
if
n
-
k
is
odd
;
η
(
2
Γ
(
P
2
)
∪
k
Γ
(
K
1
)
)
,
if
n
-
k
is
even
.
Hence by Lemma6,
(27)
η
(
Γ
(
G
)
)
=
{
η
(
Γ
(
P
2
)
)
+
η
(
Γ
(
C
3
)
)
+
k
η
(
Γ
(
K
1
)
)
=
0
+
0
+
k
=
k
,
if
n
-
k
is
odd
;
2
η
(
Γ
(
P
2
)
)
+
k
η
(
Γ
(
K
1
)
)
=
0
+
k
=
k
,
if
n
-
k
is
even
.Figure 2


## 5.2. The Nullity Set of Unbalanced Bicyclic Signed Graphs inΓ
(
B
n
+
+
)

Theorem 15.
Letn
≥
8, Γ
(
G
)
∈
Γ
(
B
n
+
+
). Then η
(
Γ
(
G
)
)
≤
n
-
6.Proof.
LetG
∈
B
n
+
+ be a bicyclic graph with trees attached on an ∞-graph, ∞
(
p
,
q
,
1
), where p
,
q
≥
3.
Case
1 (p
,
q
∈
{
3,4
}). In this case, there must exist a graph H on h vertices as an induced subgraph of G, where H
=
H
4
,
H
5 with h
=
6, or H
=
H
6
,
H
7
,
H
8
,
H
9 with h
=
7, or H
=
H
10
,
H
11
,
H
12 with h
=
8 shown in Figure 3. By Lemma 9 repeatedly and Theorem 4, we obtain η
(
Γ
(
H
4
)
)
=
η
(
Γ
(
H
5
)
)
=
η
(
Γ
(
H
8
)
)
=
0, η
(
Γ
(
H
6
)
)
=
η
(
Γ
(
H
7
)
)
=
η
(
Γ
(
H
9
)
)
=
1, η
(
Γ
(
H
11
)
)
=
η
(
Γ
(
H
12
)
)
=
2, and let Γ
(
C
4
) be the quadrangle containing no pendent edge of Γ
(
H
10
); we have
(28)
η
(
Γ
(
H
10
)
)
=
{
2
,
if
Γ
(
C
4
)
is
balanced
;
0
,
if
Γ
(
C
4
)
is
unbalanced
.
Hence for eachΓ
(
H
i
)
(
i
=
4,5
,
…
,
12
), we have r
(
Γ
(
H
i
)
)
≥
6, so r
(
Γ
(
G
)
)
≥
r
(
Γ
(
H
i
)
)
≥
6. Thus η
(
Γ
(
G
)
)
≤
n
-
6.
Case
2 (p
≥
5 or q
≥
5). Without loss of generality, we assume that p
≥
5. There must exist a graph H
3 on p
+
1 vertices shown in Figure 1 as an induced subgraph of G. Similar to the proof of Case 2 in Theorem 13, we have r
(
Γ
(
H
3
)
)
≥
6. Then r
(
Γ
(
G
)
)
≥
r
(
Γ
(
H
3
)
)
≥
6 and thus η
(
Γ
(
G
)
)
≤
n
-
6.Figure 3Lemma 16 (see [14]).
LetH
13 be a graph on 5 vertices as shown in Figure 4, and the two triangles of Γ
(
H
13
) have the same balance. Then η
(
Γ
(
H
13
)
)
=
n
-
5
=
0.Figure 4Theorem 17.
Letn
≥
8; then the nullity set of unbalanced bicyclic signed graphs in Γ
(
B
n
+
+
) is [
0
,
n
-
6
].Proof.
It suffices to show that for eachk
∈
[
0
,
n
-
6
], there exists an unbalanced bicyclic signed graph Γ
(
G
)
∈
Γ
(
B
n
+
+
) such that η
(
Γ
(
G
)
)
=
k.
Case
1 (k
=
0). It is clear that there exists an unbalanced bicyclic signed graph Γ
(
G
)
=
Γ
(
∞
(
p
,
q
,
1
)
)
∈
Γ
(
B
n
+
+
) satisfying η
(
Γ
(
G
)
)
=
0 by Theorem 10, where p
,
q
≥
3.
Case
2 (k
=
n
-
6). Let G
=
G
3 shown in Figure 4, where the two triangles of Γ
(
G
3
) are unbalanced. Then by Lemmas 9 and 6, we have η
(
Γ
(
G
)
)
=
η
(
Γ
(
P
2
)
∪
(
n
-
6
)
Γ
(
K
1
)
)
=
η
(
Γ
(
P
2
)
)
+
(
n
-
6
)
η
(
Γ
(
K
1
)
)
=
0
+
(
n
-
6
)
=
n
-
6.
Case
3 (1
≤
k
≤
n
-
7). Let G
=
G
4 shown in Figure 5, where the two triangles of Γ
(
G
4
) are unbalanced.
Subcase
3.1 (n
-
k is odd). By using Lemma 9 repeatedly, after (
n
-
k
-
5
)
/
2 steps, we obtain the graph k
Γ
(
K
1
)
∪
Γ
(
H
13
), where the two triangles of Γ
(
H
13
) are unbalanced. Hence η
(
Γ
(
G
)
)
=
η
(
k
Γ
(
K
1
)
∪
Γ
(
H
13
)
)
=
η
(
k
Γ
(
K
1
)
)
+
η
(
Γ
(
H
13
)
)
=
k
+
0
=
k by Lemma 16.
Subcase
3.2 (n
-
k is even). By using Lemma 9 repeatedly, after (
n
-
k
-
2
)
/
2 steps, we obtain the graph k
Γ
(
K
1
)
∪
Γ
(
P
2
). Hence η
(
Γ
(
G
)
)
=
η
(
k
Γ
(
K
1
)
∪
Γ
(
P
2
)
)
=
η
(
k
Γ
(
K
1
)
)
+
η
(
Γ
(
P
2
)
)
=
k
+
0
=
k.Figure 5


## 5.3. The Nullity Set of Unbalanced Bicyclic Signed Graphs inΓ
(
Θ
n
)

Lemma 18 (see [14]).
LetΓ
(
G
) be an unbalanced bicyclic signed graph on n vertices. Then η
(
Γ
(
G
)
)
≤
n
-
3, with equality if and only if Γ
(
G
)
=
Γ
(
Θ
(
2,2
,
1
)
) and the two triangles of Γ
(
Θ
(
2,2
,
1
)
) are both unbalanced.By Lemma18, we obtain the following result immediately.Proposition 19.
Letn
≥
5 and let Γ
(
G
) be an unbalanced bicyclic signed graph in Γ
(
Θ
n
). Then η
(
Γ
(
G
)
)
≤
n
-
4.Theorem 20.
Letn
≥
6. Then the nullity set of unbalanced bicyclic signed graphs in Γ
(
Θ
n
) is [
0
,
n
-
4
].Proof.
It suffices to show that for eachk
∈
[
0
,
n
-
4
], there exists an unbalanced bicyclic signed graph Γ
(
G
)
∈
Γ
(
Θ
n
) such that η
(
Γ
(
G
)
)
=
k.
Case
1 (k
=
0). Let G
=
G
5 shown in Figure 6, where Γ
(
G
5
) contains at least an unbalanced triangle. By Lemma 9 and Theorem 4 (when n is odd) or Proposition 5 (when n is even), we have η
(
Γ
(
G
)
)
=
0.
Case
2 (k
=
n
-
4). Let G
=
G
6 shown in Figure 6, where Γ
(
G
6
) contains at least an unbalanced triangle. By Lemma 9 and Proposition 5, we have η
(
Γ
(
G
)
)
=
η
(
Γ
(
P
3
)
∪
(
n
-
5
)
Γ
(
K
1
)
)
=
η
(
Γ
(
P
3
)
)
+
(
n
-
5
)
η
(
Γ
(
K
1
)
)
=
1
+
(
n
-
5
)
=
n
-
4.
Case
3 (1
≤
k
≤
n
-
5). Consider the following subcases.
Subcase
3.1 (n
-
k is odd). Let G
=
G
7 shown in Figure 6, where the two triangles of G
7 are unbalanced. By using Lemma 9 repeatedly, after (
n
-
k
-
3
)
/
2 steps, we obtain the graph Γ
(
Θ
(
2,2
,
1
)
)
∪
(
k
-
1
)
Γ
(
K
1
). Hence η
(
Γ
(
G
)
)
=
η
(
Γ
(
Θ
(
2,2
,
1
)
)
∪
(
k
-
1
)
Γ
(
K
1
)
)
=
η
(
Γ
(
Θ
(
2,2
,
1
)
)
)
+
(
k
-
1
)
η
(
Γ
(
K
1
)
)
=
1
+
(
k
-
1
)
=
k by Lemmas 9 and 18.
Subcase
3.2 (n
-
k is even). Let G
=
G
8 shown in Figure 6, where the triangle of G
8 is unbalanced and the quadrangle is balanced. By using Lemma 9 repeatedly, after (
n
-
k
-
2
)
/
2 steps, we obtain the graph Γ
(
C
4
)
∪
(
k
-
2
)
Γ
(
K
1
). Hence η
(
Γ
(
G
)
)
=
η
(
Γ
(
C
4
)
∪
(
k
-
2
)
Γ
(
K
1
)
)
=
η
(
Γ
(
C
4
)
)
+
(
k
-
2
)
η
(
Γ
(
K
1
)
)
=
2
+
(
k
-
2
)
=
k by Lemma 9 and Theorem 4.Figure 6


## 5.4. In Conclusion

From the above discussion, by Theorems12, 14, 17 and 20 we can obtain the following results immediately.Theorem 21.
Letn
≥
8. Then the nullity set of unbalanced bicyclic signed graphs is [
0
,
n
-
4
].Theorem 22.
Letn
≥
8. Then the nullity set of bicyclic signed graphs is [
0
,
n
-
4
].When4
≤
n
≤
7, the nullity set of bicyclic signed graphs is easy to obtain by known results and direct calculation, so we omit it.



---

*Source: 483735-2014-02-18.xml*