PreprintCC BY-NC-ND 4.0arXiv
A matroid characterization of the combinatorially symmetric maximum nullity of a graph
Abstract
The graph parameter N(G) is the maximum nullity among all combinatorially symmetric matrices associated to a graph G. The zero forcing number Z(G) is a well-known upper bound for N(G), and a zero forcing set of G is exactly a set that intersects each fort of the graph. So the zero forcing number can be defined as the size of a minimum set that intersects every fort of G. This paper provides a similar characterization of N(G) that is purely combinatorial, using a connection to matroid theory and collections of forts that are compatible in a certain sense. We provide several examples highlighting subtle differences among compatible collections of forts and how they relate to full spark matrices and matroids associated to G.
Related
- The Vámos Matroid Has No Second Symmetric Power
- Corrigendum to "On the Maximum Symmetric Division Deg Index of k-Cyclic Graphs [J. Math. 2022, (2022) \#7783128]"
- Strong maximum principle for nonlocal diffusion in measure spaces: new characterization and population dynamics applications
- Characterization of graphs attaining the maximum signless Laplacian spectral radius under forbidden cycles and theta graphs
- A Compactness Characterization of Strongly Symmetric Homeomorphisms
BibTeX
@misc{deaett2026matroid,
title = {{A matroid characterization of the combinatorially symmetric maximum nullity of a graph}},
author = {Louis Deaett and Veronika Furst and John Hutchens and Lon Mitchell},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01102},
eprint = {2611.01102},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01102},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - A matroid characterization of the combinatorially symmetric maximum nullity of a graph
AU - Louis Deaett
AU - Veronika Furst
AU - John Hutchens
AU - Lon Mitchell
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01102
UR - https://arxiv.org/abs/2611.01102
AB - The graph parameter N(G) is the maximum nullity among all combinatorially symmetric matrices associated to a graph G. The zero forcing number Z(G) is a well-known upper bound for N(G), and a zero forcing set of G is exactly a set that intersects each fort of the graph. So the zero forcing number can be defined as the size of a minimum set that intersects every fort of G. This paper provides a similar characterization of N(G) that is purely combinatorial, using a connection to matroid theory and collections of forts that are compatible in a certain sense. We provide several examples highlighting subtle differences among compatible collections of forts and how they relate to full spark matrices and matroids associated to G.
ER -