The inverse eigenvalue problem for probe graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909123190194176 |
|---|---|
| author | Curl, Emelie Kritschgau, Jürgen Reinhart, Carolyn van der Holst, Hein |
| author_facet | Curl, Emelie Kritschgau, Jürgen Reinhart, Carolyn van der Holst, Hein |
| contents | In this paper, we initiate the study of the inverse eigenvalue problem for probe graphs. A probe graph is a graph whose vertices are partitioned into probe vertices and non-probe vertices such that the non-probe vertices form an independent set. In general, a probe graph is used to represent the set of graphs that can be obtained by adding edges between non-probe vertices. The inverse eigenvalue problem for a graph considers a family of matrices whose zero-nonzero pattern is defined by the graph and asks which spectra are achievable by matrices in this family. We ask the same question for probe graphs. We start by establishing bounds on the maximum nullity for probe graphs and defining the probe graph zero forcing number. Next, we focus on graphs of two parallel paths, the unique family of graphs whose (standard) zero forcing number is two. We partially characterize the probe graph zero forcing number of such graphs and prove some necessary structural results about the family. Finally, we characterize probe graphs whose minimum rank is $0, 1, 2, n-2,$ and $n-1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_18670 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The inverse eigenvalue problem for probe graphs Curl, Emelie Kritschgau, Jürgen Reinhart, Carolyn van der Holst, Hein Combinatorics 05C50, 05C69 In this paper, we initiate the study of the inverse eigenvalue problem for probe graphs. A probe graph is a graph whose vertices are partitioned into probe vertices and non-probe vertices such that the non-probe vertices form an independent set. In general, a probe graph is used to represent the set of graphs that can be obtained by adding edges between non-probe vertices. The inverse eigenvalue problem for a graph considers a family of matrices whose zero-nonzero pattern is defined by the graph and asks which spectra are achievable by matrices in this family. We ask the same question for probe graphs. We start by establishing bounds on the maximum nullity for probe graphs and defining the probe graph zero forcing number. Next, we focus on graphs of two parallel paths, the unique family of graphs whose (standard) zero forcing number is two. We partially characterize the probe graph zero forcing number of such graphs and prove some necessary structural results about the family. Finally, we characterize probe graphs whose minimum rank is $0, 1, 2, n-2,$ and $n-1$. |
| title | The inverse eigenvalue problem for probe graphs |
| topic | Combinatorics 05C50, 05C69 |
| url | https://arxiv.org/abs/2402.18670 |