Minimum rank of graphs that allow loops

Thumbnail Image
Date
2008-01-01
Authors
Mikkelson, Rana
Major Professor
Advisor
Leslie Hogben
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Mathematics
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.

Comments
Description
Keywords
Citation
Source
Subject Categories
Copyright
Tue Jan 01 00:00:00 UTC 2008