On the Rank of Graphs
Date Issued
2009
Date
2009
Author(s)
Huang, Liang-Hao
Abstract
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.
Subjects
minimum rank
maximum nullity
rank
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-D93221001-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):ac4a7c1c8a151dcaf0e78c2b89be5cd3