Date of Award
Doctor of Philosophy
The traditional "minimum rank problem" for simple graphs associates a set of symmetric matrices, the zero-nonzero pattern of whose off-diagonal entries are described by the graph, over a particular field and asks us to find the minimum among the ranks of the matrices in that set. Given a simple tree, the minimum rank is readily computed over any field. There is no known technique for finding the minimum rank of any given graph, but several techniques have been developed for some graphs that have a particular property or structure. In particular, if a graph has a cut vertex, a formula is known that allows the minimum rank to be computed from certain subgraphs. One extension of the traditional "minimum rank problem" is to graphs that allow loops. An algorithm for the computation of minimum rank of any tree that allows loops over the real numbers is known. In this presentation we discuss an extension of the known result for simple graphs with a cut vertex to graphs that allow loops that have a cut vertex and apply the result to obtain a means of computing the minimum rank of any tree that allows loops over any field with at least three elements. Minimum rank problems (in various forms, including sign patterns), have application to communication complexity.
Rana C. Mikkelson
Mikkelson, Rana C., "Minimum rank of graphs that allow loops" (2008). Graduate Theses and Dissertations. 11187.