TY - JOUR

T1 - CONSTRUCTIONS OF COSPECTRAL GRAPHS WITH DIFFERENT ZERO FORCING NUMBERS

AU - Abiad, Aida

AU - Brimkov, Boris

AU - Breen, Jane

AU - Cameron, Thomas R.

AU - Gupta, Himanshu

AU - Villagrán, Ralihe R.

N1 - Funding Information:
Acknowledgments. The research of all the authors was partially supported by NSF grant 1916439. This project was started at the MRC workshop “Finding Needles in Haystacks: Approaches to Inverse Problems using Combinatorics and Linear Algebra,” which took place in June 2021 with support from the National Science Foundation and the American Mathematical Society. The authors are grateful to the organizers of this meeting. We thank S. Fallat for bringing reference [4] to our attention. A. Abiad is partially supported by the FWO (Research Foundation Flanders) grant 1285921N. The work of J. Breen was supported in part by NSERC Discovery Grant RGPIN-2021-03775.
Publisher Copyright:
© 2022, International Linear Algebra Society. All rights reserved.

PY - 2022

Y1 - 2022

N2 - Several researchers have recently explored various graph parameters that can or cannot be characterized by the spectrum of a matrix associated with a graph. In this paper, we show that several NP-hard zero forcing numbers are not characterized by the spectra of several types of associated matrices with a graph. In particular, we consider standard zero forcing, positive semidefinite zero forcing, and skew zero forcing and provide constructions of infinite families of pairs of cospectral graphs, which have different values for these numbers. We explore several methods for obtaining these cospectral graphs including using graph products, graph joins, and graph switching. Among these, we provide a construction involving regular adjacency cospectral graphs; the regularity of this construction also implies cospectrality with respect to several other matrices including the Laplacian, signless Laplacian, and normalized Laplacian. We also provide a construction where pairs of cospectral graphs can have an arbitrarily large difference between their zero forcing numbers.

AB - Several researchers have recently explored various graph parameters that can or cannot be characterized by the spectrum of a matrix associated with a graph. In this paper, we show that several NP-hard zero forcing numbers are not characterized by the spectra of several types of associated matrices with a graph. In particular, we consider standard zero forcing, positive semidefinite zero forcing, and skew zero forcing and provide constructions of infinite families of pairs of cospectral graphs, which have different values for these numbers. We explore several methods for obtaining these cospectral graphs including using graph products, graph joins, and graph switching. Among these, we provide a construction involving regular adjacency cospectral graphs; the regularity of this construction also implies cospectrality with respect to several other matrices including the Laplacian, signless Laplacian, and normalized Laplacian. We also provide a construction where pairs of cospectral graphs can have an arbitrarily large difference between their zero forcing numbers.

UR - http://www.scopus.com/inward/record.url?scp=85131826041&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85131826041&partnerID=8YFLogxK

U2 - 10.13001/ela.2022.6737

DO - 10.13001/ela.2022.6737

M3 - Article

AN - SCOPUS:85131826041

SN - 1537-9582

VL - 38

SP - 280

EP - 294

JO - Electronic Journal of Linear Algebra

JF - Electronic Journal of Linear Algebra

ER -