葉鴻國臺灣大學:數學研究所黃良豪Huang, Liang-HaoLiang-HaoHuang2010-05-052018-06-282010-05-052018-06-282009U0001-1906200913433400http://ntur.lib.ntu.edu.tw//handle/246246/180631給定圖 $G$ 和體 $F$，$G$ 佈於 $F$ 的最小秩 $mr^F(G)$是所有佈於 $F$ 可決定 $G$ 的對稱方陣中最小的秩。圖的最小秩問題是等價於圖的最大零維數 ($M^F(G)$) 問題。Barioli 等人 [1] 提出圖的參數 $Z(G)$ 作為 $M^F(G)$ 的上界，這篇論文中的目標是[1] 中提出的一個問題︰哪類的圖具有 $Z(G)=M^F(G)$ 的性質。 在第二章中，我們證明了如果 $G$ 是區塊圖，則$Z(G)=M^F(G)$。推廣了 [1] 中的結果。我們也證明了如果 $|F|= infty$ 且 $G$是單位區間圖，則$Z(G)=M^F(G)$。在第三章中，我們證明 $d$ 維的hypercube $Q_d$，$M^F(Q_d)$ 和所佈於的體 $F$ 是無關的，推廣了 [1] 中的結果。我們還提供幾類圖具有 $Z(G)=M^F(G)$ 的性質。在第四章中pp 我們提供幾類圖pp 具有特別形式的最優矩陣。在第五章中，我們研究 cograph 的秩，且回答 Royle [28]所提出的問題。對於 cograph 的秩，我們給予不同的方式證明。The minimum rank problem is, for a given graph $G$ and a field $F$, to determine the smallest possible rank among all symmetric matrices over $F$ whose off-diagonal pattern of zero-nonzero entries is described by $G$. The solution to the minimum rank problem is equivalent to the determination of the maximum nullity $M^F(G)$ among the same family of matrices. Recently, in [1], a new graph parameter $Z(G)$, the zero forcing number, has been introduced as a technique to bound $M^F(G)$ from above.t the end of the paper [1]} the authors posed the following attractive question: What is the class of graphs $G$ for which $Z(G)=M^F(G)$ for some field $F$? Our goal of this thesis is to investigate which graphs has the property $Z(G)=M^F(G)$ and to determine $M^F(G)$.In Chapter 2, we show that if $G$ is a block-clique graph,hen $Z(G)=M^F(G)$. The assertion for block-clique graphs generalizes Proposition 3.23 of [1]. We also show that if $F$ is infinite and $G$ is a unit interval graph, then $Z(G)=M^F(G)$. In Chapter 3, we show that for the $d$-dimensional hypercube $Q_d$, $M^F(Q_d)$ is field independent. This result generalizes Theorem 3.1 of [1] We also give several families of product graphs $G$ which are demonstrated that $Z(G)=M^F(G)$ for every field $F$. In Chapter 4, we give several families of graphs $G$ whichas a universally optimal matrix and has field independent minimum rank. In Chapter 5, we answer a question posed by Royle [28] by giving an elementary short proof for a more general setting of this rank property of cographs.1 Introduction 1 1.1 Minimum rank of a graph . . . . . . . . . . . . 1 1.2 Basic definitions in graph theory . . . . . . . 3 1.3 Basic definitions in linear algebra . . . . . . . 4 1.4 Zero forcing number of a graph . . . . . . . . . 5 1.5 Results of this thesis . . . . . . . . . . . . . 7 The Minimum Rank of Graphs and Zero Forcing Sets 8 2.1 Introduction and preliminary results . . . . . . 8 2.2 The minimum rank of block-clique graphs . . . . 9 2.3 The minimum rank of unit interval graphs . . . 14 The Minimum Rank of Product Graphs 17 3.1 Cartesian product . . . . . . . . . . . . . . . 17 3.2 Direct product and strong product . . . . . . . 27 Universally Optimal Matrices 40 4.1 Introduction . . . . . . . . . . . . . . . . . 40 4.2 Main results . . . . . . . . . . . . . . . . . 42 The Rank of Cographs 55 5.1 Preliminary . . . . . . . . . . . . . . . . 55 5.2 Rank of a vertex-weighted cograph . . . . . . . 57ibliography 62application/pdf569108 bytesapplication/pdfen-US最小秩最大零維數秩minimum rankmaximum nullityrankthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/180631/1/ntu-98-D93221001-1.pdf