對於一個（簡單）圖 G，我們分別用 |V(G)|、|E(G)|、η(G) 及 m(G) 來表示該圖的階數、邊數、零化數和匹配數。 Wang 和 Wong (2014) 證明了：對每一圖 G，這些數有以下的關係:
|V(G)|-2m(G)-c(G)≤η(G)≤|V(G)|-2m(G)+2c(G),
其中 c(G):=|E(G)|-|V(G)|+θ(G) 是 G 的圈數，θ(G) 是 G 的極大連通子圖數。稍後，Song 等人 (2015) 對具有最大零化數條件的圖做了刻劃；而 Rula 等人 (2016) 和 Wang (2016) 也分別獨立地對具有最小零化數條件的圖給出了刻劃。早些時候Gou等人 (2009) 證明了，對於任一單圈圖 G，η(G)-|V(G)|+2m(G) 此數的可能取值為 -1,0 或 2 ；此外，他們也刻劃了這三種類型的單圈圖。
    在本論文，我們利用與有根樹圖相關的典型星圖、與單圈圖相關的典型單圈圖、圖的關鍵子圖、將原圖中圈縮為點所形成的無圈圖、及最大基本子圖的概念，修正、強化和擴展了以前作者在該主題上的工作。
    我們證明了由 Wang (2016) 所引入的圖的所有關鍵子圖都是圖同構的。我們對於三種單圈圖、非奇異單圈圖和具有最小或最大零化數條件的圖給出了更完整的刻劃。此外，也證明了如果給定正整數c, n且n ≥ 6c + 2，則對於任意整數k，-c ≤ k ≤ 2c，k≠2c-1，存在滿足以下條件的n階連通圖G: c(G) = c 及η(G) -|V(G)|+ 2m(G) = k；然而，若 k = 2c -1，則不存在滿足相應條件的的圖G。

For a (simple) graph G, we denote by |V(G)|, |E(G)|, η(G) and m(G) respectively the order, the number of edges, the nullity, and the matching number of G. It was shown by Wang and Wong (2014) that for every graph G, 
|V(G)|-2m(G)-c(G)≤η(G) ≤|V(G)|-2m(G)+2c(G),
where c(G):=|E(G)|-|V(G)|+θ(G) is the cyclomatic number of G, θ(G) being the number of components of G. Graphs with the maximal nullity condition has been characterized by Song et al.,(2015), and graphs with the minimal nullity condition have also been characterized independently by Rula et al.,(2016) and Wang,(2016). Earlier Guo et al., (2009) had also shown that for a unicyclic graph G, η(G)-|V(G)|+2m(G) can take only one of the values -1,0 or 2, and they characterized these three types of unicyclic graphs. In this thesis, exploiting the concepts of canonical star associated with a rooted tree, the canonical unicyclic graph associated with a unicyclic graph, a crucial subgraph of a graph, the acyclic graph obtained from a graph by contracting its cycles and elementary subgraphs with maximum order, we rectify, strengthen and extend the work of previous authors on this topic. We give a nontrivial proof for the fact that the crucial subgraphs of a graph, as introduced by Wang (2016), are unique up to isomorphism. More complete lists of characterizations for the three types of unicyclic graphs, nonsingular unicyclic graphs, and graphs with minimal or maximal nullity conditions are found. It is proved that if c, n are given positive integers with n ≥ 6c+2, then for any integer k, -c ≤ k ≤2c, k≠2c-1, there exists a connected graph G of order n that satisfies c(G) = c and η(G)-|V(G)|+2m(G) = k; however, if k is replaced by 2c-1, there is no graph G of any order that satisfies the corresponding conditions.

Contents
1 Introduction 1
2 Preliminaries 7
2.1 Some graph-theoretic definitions . . . . . . . . . . . . . . . . 7
2.2 The canonical star associated with a rooted tree . . . . . . . 9
2.3 The canonical unicyclic graph associated with a unicyclic graph 13
2.4 Crucial subgraphs: the uniqueness issue . . . . . . . . . . . 14
2.5 Relations between matching numbers and nullities of G, G′, G − G′ . . . . . . . . . . . . . . . . . . . . . . 31

3 A Classification of Unicyclic Graphs 37
3.1 Possible values of η(G)−|V (G)+2m(G): the unicyclic graph
case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2 Matched and mismatched vertices . . . . . . . . . . . . . . . 40
3.3 The crucial subgraph of a unicyclic graph . . . . . . . . . . 42
3.4 Relations between m(G), m(G∗) and m(G − G∗) . . . . . . . 43
3.5 Classification of unicyclic graphs . . . . . . . . . . . . . . . 47
4 Characterizations of Nonsingular Unicyclic Graphs 50
4.1 Historical background . . . . . . . . . . . . . . . . . . . . . 50
4.2 Canonical unicyclic graphs, perfect matchings . . . . . . . . 52
4.3 Characterizations of nonsingular unicyclic graphs . . . . . . 54
5 Graphs with the Minimal or Maximal Nullity Condition 60
CONTENTS iii
5.1 Elementary subgraphs of maximum order . . . . . . . . . . . 61
5.2 Graphs with pairwise vertex-disjoint cycles . . . . . . . . . . 64
5.3 Graphs with the minimal nullity condition . . . . . . . . . . 79
5.4 Graphs with the maximal nullity condition . . . . . . . . . . 83
6 Possible Values of η(G) − |V (G)| + 2m(G) 89
6.1 Two technical lemmas . . . . . . . . . . . . . . . . . . . . . 90
6.2 Proof of Theorem 6.0.1 . . . . . . . . . . . . . . . . . . . . . 97
6.3 Final Remarks . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.3.1 Extensions to signed graphs . . . . . . . . . . . . . . 100
6.3.2 Equality cases of the bounds for m(G) . . . . . . . . 101
6.3.3 A comparison of upper bounds for η(G) . . . . . . . 102
6.3.4 Limitation of our work . . . . . . . . . . . . . . . . . 104
References 105

[1] L. Collatz and U. Sinogowitz, Spektren sndicher grafen, Abhandlungenaus dem Mathematischen Seminar der Universtaet Hamburg 21 (1957), 63–77.
[2] D. M. Cvetković, I. Gutman, and N. Trinajstić, Graphical studies on the relations between the structure and reactivity of conjugated systems: the role of non-bonding molecular orbitals, Journal of Molecular Structure 28 (1975), 289–303.
[3] D. M. Cvetković and Ivan Gutman, The algebraic multiplicity of the number zero in the spectrum of a bipartite graph, Matematički Vesnik. New Series 9 (1972), 141–150.
[4] Shi-Cai Gong, Yi-Zheng Fan, and Zhi-Xiang Yin, On the nullity of graphs with pendant trees, Linear Algebra Appl. 433 (2010), no. 7, 1374–1380. MR 2680264
[5] Ji-Ming Guo, Weigen Yan, and Yeong-Nan Yeh, On the nullity and the
matching number of unicyclic graphs, Linear Algebra and its Applications 431 (2009), no. 8, 1293 – 1301.
[6] Ivan Gutman and Bojana Borovićanin, Nullity of graphs: an updated survey, Selected topics on applications of graph spectra, Math. Inst., Belgrade (2011), 137–154.
[7] Shengjie He, Rong-Xia Hao, and Hong-Jian Lai, Bounds for the matching number and cyclomatic number of a signed graph in terms of rank, Linear Algebra and its Applications 572 (2019), 273–291.
[8] Xin Li and Ji-Ming Guo, No graph with nullity η(G) = |V (G)|−2m(G)+2c(G)−1, Discrete Applied Mathematics 268(5) (2019), 130–136.
[9] Yong Lu and Jingwen Wu, No signed graph with the nullity η(G.σ)=|V (G)|−2m(G) + 2c(G)−1, Linear Algebra and its Applications 615
(2021), 175–193.
[10] Xiaobin Ma, Dein Wong, and Fenglei Tian, Nullity of a graph in terms
of the dimension of cycle space and the number of pendant vertices,
Discrete Applied Mathematics 215 (2016), 171–176.
106
[11] Sa Rula, An Chang, and Yirong Zheng, The extremal graphs with respect
to their nullity, Journal of Inequalities and Applications 2016 (2016),
no. 1, 1–13.
[12] Horst Sachs, D. M. Cvetković, and Michael Doob, Spectra of graphs:
theory and applications, VEB Deutscher Verlag der Wissenschaften,
1980.
[13] Ya-zhi Song, Xiao-qiu Song, and Bit-Shun Tam, A characterization of
graphs g with nullity, Linear Algebra and its Applications 465 (2015),
363 – 375.
[14] Bit-Shun Tam and Tsu-Hsien Huang, Nullities of graphs with given order,
matching number and cyclomatic number revisited, Linear Algebra
and its Applications 535 (2017), 105–140.
[15] Xuezhong Tan and Bolian Liu, On the nullity of unicyclic graphs, Linear
algebra and its applications 408 (2005), 212–220.
[16] Nenad Trinajstić, Chemical graph theory second ed., CRC Press, 1992.
[17] Long Wang, Characterization of graphs with given order, given size and
given matching number that minimize nullity, Discrete Mathematics
339 (2016), no. 5, 1574 – 1582.
[18] Long Wang and Dein Wong, Bounds for the matching number, the edge
chromatic number and the independence number of a graph in terms of
rank, Discrete Applied Mathematics 166 (2014), 276–281.
[19] Douglas Brent West et al., Introduction to graph theory, vol. 2, Prentice
hall Upper Saddle River, NJ, 1996.