Reconfiguration graphs of zero forcing sets

Thumbnail Image
Date
2020-01-01
Authors
Geneson, Jesse
Haas, Ruth
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Person
Hogben, Leslie
Associate Dean
Research Projects
Organizational Units
Organizational Unit
Mathematics
Welcome to the exciting world of mathematics at Iowa State University. From cracking codes to modeling the spread of diseases, our program offers something for everyone. With a wide range of courses and research opportunities, you will have the chance to delve deep into the world of mathematics and discover your own unique talents and interests. Whether you dream of working for a top tech company, teaching at a prestigious university, or pursuing cutting-edge research, join us and discover the limitless potential of mathematics at Iowa State University!
Journal Issue
Is Version Of
Versions
Series
Department
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.

Description
Keywords
Citation
DOI
Source
Copyright
Wed Jan 01 00:00:00 UTC 2020
Collections