Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

2020

Journal or Book Title

arXiv

Abstract

This paper begins the study of reconfiguration of zero forcing sets, and more specifically, the zero forcing graph. Given a base graph G, its zero forcing graph, Z(G), is the graph whose vertices are the minimum zero forcing sets of G with an edge between vertices B and B′ of Z(G) if and only if B can be obtained from B′ by changing a single vertex of G. It is shown that the zero forcing graph of a forest is connected, but that many zero forcing graphs are disconnected. We characterize the base graphs whose zero forcing graphs are either a path or the complete graph, and show that the star cannot be a zero forcing graph. We show that computing Z(G) takes 2Θ(n) operations in the worst case for a graph G of order n.

Comments

This is a pre-print of the article Geneson, Jesse, Ruth Haas, and Leslie Hogben. "Reconfiguration graphs of zero forcing sets." arXiv preprint arXiv:2009.00220 (2020). Posted with permission.

Copyright Owner

The Author(s)

Language

en

File Format

application/pdf

Published Version

Share

COinS