Degree Type

Dissertation

Date of Award

2008

Degree Name

Doctor of Philosophy

Department

Mathematics

First Advisor

Leslie Hogben

Abstract

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.

Copyright Owner

Rana C. Mikkelson

Language

en

Date Available

2012-04-30

File Format

application/pdf

File Size

60 pages

Included in

Mathematics Commons

Share

COinS