零強迫數在最小秩問題上的應用

Applications of zero forcing number to the minimum rank problem

林晉宏(Chin-Hung Lin)

指導教授 ： 張鎮華

國立臺灣大學/理學院/數學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.02039

摘要

一個圖G的最小秩問題是在討論所有可決定G的實對稱方陣中最小的秩，這等同於討論這群方陣中的最大零維數M(G)。零強迫數Z(G)是指最小零強迫集的個數，可用於最小秩問題的研究。而路徑覆蓋數P(G)是指可以用來覆蓋圖G點集的最小導出路徑數。當圖G中有截點時，我們提出一個公式用小圖的零強迫數來計算原圖G的零強迫數，並且討論在某些條件下P(G)會等於Z(G)，而這條件叫做強PZ條件。
　　零強迫數Z(G)是M(G)已知的上界。我們提出一個更緊的上界叫窮舉零強迫數~Z(G)，也就是Z(G)≥~Z(G)≥M(G)。並且提出一個篩選過程，使得在某些特殊例子中，可以得到比窮舉零強迫數再更緊的上界。
　　最後，我們找到一個反例，可以用來回答一個關於零強迫數在邊上的差值問題。

關鍵字

最小秩 ； 零強迫數 ； 窮舉零強迫數 ； 篩選過程

並列摘要

無資料

並列關鍵字

minimum rank ； zero forcing number ； exhaustive zero forcing number ； sieving process

參考文獻

[1] AIM minimum rank-special graphs work group, Zero forcing sets and the minimum rank of graphs, Linear Algebra and its Applications 428 (2008) 1628--1648.

[4] F. Barioli, S. Fallat, and L. Hogben, Computation of minimal rank and path cover number for certain graphs, Linear Algebra and its Applications 392 (2004) 289--303.

[5] F. Barioli, S. Fallat, and L. Hogben, On the difference between the maximum multiplicity and path cover number for tree-like graphs, Linear Algebra and its Applications 409 (2005) 13--31.

[8] C. J. Edholm, L. Hogben, M. Huynh, J. LaGrange, and D. D. Row, Vertex and edge spread of zero forcing number, maximum nullity, and maximum rank of a graph, Hogben's Homepage.

[9] S. Fallat and L. Hogben, The minimum rank of symmetric matrices described by a graph: A survey, Linear Algebra and its Applications 426 (2007) 558--582.