Degree Type

Dissertation

Date of Award

2015

Degree Name

Doctor of Philosophy

Department

Mathematics

First Advisor

Leslie Hogben

Abstract

This thesis applies techniques from fractional graph theory to develop fractional versions of graph parameters related to minimum rank and zero forcing. Projective rank, a graph parameter with applications to quantum information, is formally related to $r$-fold generalizations of orthogonal representations for graphs. Using similar techniques, fractional minimum positive semidefinite rank is defined via $r$-fold generalizations of faithful orthogonal representations and $r$-fold minimum positive semidefinite rank, and it is shown that the fractional minimum positive semidefinite rank of any graph equals the projective rank of the complement of the graph. An alternate characterization of $r$-fold minimum positive semidefinite rank that considers the ranks of certain Hermitian matrices is also presented. Motivated by the connections between zero forcing games and minimum rank problems, an $r$-fold analogue of the positive semidefinite zero forcing process is introduced and used to define the fractional positive semidefinite forcing number of a graph. An analysis of the $r$-fold positive semidefinite forcing game leads to a three-color forcing game that allows computation of fractional positive semidefinite forcing number without appealing to the $r$-fold game. The three-color approach is applied to the standard zero forcing game and it is shown that the skew zero forcing number of a graph is exactly the parameter obtained by applying the fractionalization technique to the standard zero forcing game. Graphs whose skew zero forcing number equals zero are characterized via the three-color approach and an algorithm.

Copyright Owner

Kevin Francis Palmowski

Language

en

File Format

application/pdf

File Size

89 pages

Included in

Mathematics Commons

Share

COinS