Cospectral vertices, walk-regular planar graphs and the echolocation problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914876724609024 |
|---|---|
| author | Kong, Shi-Lei Wyman, Emmett L. Xi, Yakun |
| author_facet | Kong, Shi-Lei Wyman, Emmett L. Xi, Yakun |
| contents | We study cospectral vertices on finite graphs in relation to the echolocation problem on Riemannian manifolds. First, We prove a computationally simple criterion to determine whether two vertices are cospectral. Then, we use this criterion in conjunction with a computer search to find minimal examples of various types of graphs on which cospectral but non-similar vertices exist, including minimal walk-regular non-vertex-transitive graphs, which turn out to be non-planar. Moreover, as our main result, we classify all finite 3-connected walk-regular planar graphs, proving that such graphs must be vertex-transitive. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_06022 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Cospectral vertices, walk-regular planar graphs and the echolocation problem Kong, Shi-Lei Wyman, Emmett L. Xi, Yakun Combinatorics Spectral Theory We study cospectral vertices on finite graphs in relation to the echolocation problem on Riemannian manifolds. First, We prove a computationally simple criterion to determine whether two vertices are cospectral. Then, we use this criterion in conjunction with a computer search to find minimal examples of various types of graphs on which cospectral but non-similar vertices exist, including minimal walk-regular non-vertex-transitive graphs, which turn out to be non-planar. Moreover, as our main result, we classify all finite 3-connected walk-regular planar graphs, proving that such graphs must be vertex-transitive. |
| title | Cospectral vertices, walk-regular planar graphs and the echolocation problem |
| topic | Combinatorics Spectral Theory |
| url | https://arxiv.org/abs/2401.06022 |