< Terug naar vorige pagina

Publicatie

CONSTRUCTIONS OF COSPECTRAL GRAPHS WITH DIFFERENT ZERO FORCING NUMBERS

Tijdschriftbijdrage - Tijdschriftartikel

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.
Tijdschrift: The Electronic Journal of Linear Algebra
Volume: 38
Pagina's: 280-294
Jaar van publicatie:2022
Trefwoorden:Graph, Maximum nullity, Minimum rank, Spectral characterization, Zero forcing number