擁有已知階數、匹配數及圈數的圖之零化數

Nullities of Graphs with Given Order, Matching Number and Cyclomatic Number

黃祖賢(Tsu-Hsien Huang)

指導教授 ： 譚必信

淡江大學/理學院/數學學系博士班/博士(2021年)

https://doi.org/10.6846/TKU.2021.00575

摘要

對於一個（簡單）圖 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.

並列關鍵字

Nullity ； Canonical star associated with a rooted tree ； Canonical unicyclic graph ； Pendant star ； Elementary subgraph ； Matching ； Minimal nullity condition ； Maximal nullity condition ； the Sachs theorem

參考文獻

[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