Abstract
The utility of a matrix satisfying the Strong Spectral Property has been well established particularly in connection with the inverse eigenvalue problem for graphs. More recently the class of graphs in which all associated symmetric matrices possess the Strong Spectral Property (denoted \({\mathcal {G}}^\textrm{SSP}\)) were studied, and along these lines we aim to study properties of graphs that exhibit a so-called barbell partition. Such a partition is a known impediment to membership in the class \({\mathcal {G}}^\textrm{SSP}\). In particular we consider the existence of barbell partitions under various standard and useful graph operations. We do so by considering both the preservation of an already present barbell partition after performing said graph operations as well as barbell partitions which are introduced under certain graph operations. The specific graph operations we consider are the addition and removal of vertices and edges, the duplication of vertices, as well as the Cartesian products, tensor products, strong products, corona products, joins, and vertex sums of two graphs. We also identify a correspondence between barbell partitions and graph substructures called forts, using this correspondence to further connect the study of zero forcing and the Strong Spectral Property.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data Availability
Data sharing not applicable to this article as no datasets were generated or analysed during the current study.
References
Ahmadi, B., Alinaghipour, F., Cavers, M.S., Fallat, S.M., Meagher, K., Nasserasr, S.: Minimum number of distinct eigenvalues of graphs. Electron. J. Linear Algebra 26, 673–691 (2013)
Ahn, J., Alar, C., Bjorkman, B., Butler, S., Carlson, J., Goodnight, A., Knox, H., Monroe, C., Wigal, M.C.: Ordered multiplicity inverse eigenvalue problem for graphs on six vertices. Electron. J. Linear Algebra 37, 316–358 (2021)
Arnol’d, V.I.: On matrices depending on parameters (Russian). Uspehi Mat. Nauk. 26, 101–114 (1971). (English translation in Russ. Math. Surv. 26, 29–43 (1971))
Barrett, W., Fallat, S., Hall, H.T., Hogben, L., Lin, J.C.-H., Shader, B.L.: Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph. Electron. J. Comb. 24(2), 1–28 (2017)
Barrett, W., Butler, S., Fallat, S.M., Hall, H.T., Hogben, L., Lin, J.C.-H., Shader, B.L., Young, M.: The inverse eigenvalue problem of a graph: multiplicities and minors. J. Comb. Theory Ser. B 142, 276–306 (2020)
Fallat, S., Hall, H.T., Lin, J.C.-H., Shader, B.: The bifurcation lemma for strong properties in the inverse eigenvalue problem of a graph. Linear Algebra Appl. 648, 70–87 (2022)
Fallat, S., Hogben, L.: The minimum rank of symmetric matrices described by a graph: a survey. Linear Algebra Appl. 426, 558–582 (2007)
Fallat, S., Hogben, L.: Minimum rank, maximum nullity, and zero forcing number of graphs. In: Hogben, L. (ed.) Handbook of Linear Algebra, 2nd edn, pp. 46-1–46-36. CRC Press, Boca Raton (2014)
Fast, C.C., Hicks, I.V.: Effects of vertex degrees on the zero-forcing number and propagation time of a graph. Discrete Appl. Math. 250, 215–226 (2018)
Hogben, L., Lin, J.C.-H., Shader, B.L.: Inverse Problems and Zero Forcing for Graphs. Mathematical Surveys and Monographs. American Mathematical Society (2022)
Levene, R.H., Oblak, P., Šmigoc, H.: A Nordhaus–Gaddum conjecture for the minimum number of distinct eigenvalues of a graph. Linear Algebra Appl. 564, 236–263 (2019)
Lin, J.C.-H., Oblak, P., Šmigoc, H.: The strong spectral property for graphs. Linear Algebra Appl. 598, 68–91 (2020)
de Verdière, Y.C.: Sur un nouvel invariant des graphes et un critère de planarité. J. Comb. Theory Ser. B 50, 11–21 (1990)
de Verdière, Y.C.: On a new graph invariant and a criterion for planarity. Graph Struct. Theory 147, 137 (1993)
Acknowledgements
This work 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.
Funding
This material is based upon work supported by the National Science Foundation under Grant Number DMS 1916439. Shaun M. Fallat was also supported in part by an NSERC Discovery Research Grant, Application No.: RGPIN–2019–03934.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Allred, S., Curl, E., Fallat, S. et al. The Strong Spectral Property of Graphs: Graph Operations and Barbell Partitions. Graphs and Combinatorics 40, 20 (2024). https://doi.org/10.1007/s00373-023-02745-6
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-023-02745-6