Positive semidefinite propagation time

Thumbnail Image
Date
2014-01-01
Authors
Warnberg, Nathan
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

Let G be a simple, undirected graph. Positive semidefinite (PSD) zero forcing on G is based on the following color-change rule: Let W1,W2, ..., Wk be the sets of vertices of the k connected components in G - B (where B is a set of blue vertices). If w is in Wi and is the only white neighbor of some blue vertex b in the graph G[Bi] (where Bi is the set of blue vertices of B and the white vertices of Wi), then we change w to blue. A positive semidefinite zero forcing set (PSDZFS) is a set of blue vertices that colors the entire graph blue. The positive semidefinite zero forcing number, denoted Z+(G), is the minimum cardinality of a positive semidefinite zero forcing set. The PSD propagation time of a PSDZFS B of graph G is the minimum number of iterations that it takes to color the entire graph blue, starting with B blue, such that at each iteration as many vertices are colored blue as allowed by the color-change rule. The minimum and maximum PSD propagation times are taken over all minimum PSD zero forcing sets of the graph. The PSD propagation time interval of a graph G is the set of integers [pt+(G),pt+(G) +1,...,PT+(G)]. It is believed that every integer in the interval is achievable by some minimum PSDZFS. This thesis develops tools to analyze the minimum and maximum PSD propagation time, tools for analyzing the PSD propagation time interval and applies these tools to study the PSD propagation time of many graph families.

Comments
Description
Keywords
Citation
Source
Subject Categories
Copyright
Wed Jan 01 00:00:00 UTC 2014