Distance Critical Graphs
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_ | 1866916248960368640 |
|---|---|
| author | Cooper, Joshua Tauscheck, Gabrielle |
| author_facet | Cooper, Joshua Tauscheck, Gabrielle |
| contents | In 1971, Graham and Pollak provided a formula for the determinant of the distance matrix of any tree on $n$ vertices. Yan and Yeh reproved this by exploiting the fact that pendant vertices can be deleted from trees without changing the remaining entries of the distance matrix. Considering failures of their argument to generalize invites the question: which graphs have the property that deleting any one vertex results in a change to some pairwise distance? We refer to such worst-case graphs as ``distance critical''. This work explores the structural properties of distance critical graphs, preservation of distance-criticality by products, and the nature of extremal distance critical graphs. We end with a few open questions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_09656 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distance Critical Graphs Cooper, Joshua Tauscheck, Gabrielle Combinatorics Discrete Mathematics 05C12 (Primary) 05C35, 05C75 (Secondary) G.2.2 In 1971, Graham and Pollak provided a formula for the determinant of the distance matrix of any tree on $n$ vertices. Yan and Yeh reproved this by exploiting the fact that pendant vertices can be deleted from trees without changing the remaining entries of the distance matrix. Considering failures of their argument to generalize invites the question: which graphs have the property that deleting any one vertex results in a change to some pairwise distance? We refer to such worst-case graphs as ``distance critical''. This work explores the structural properties of distance critical graphs, preservation of distance-criticality by products, and the nature of extremal distance critical graphs. We end with a few open questions. |
| title | Distance Critical Graphs |
| topic | Combinatorics Discrete Mathematics 05C12 (Primary) 05C35, 05C75 (Secondary) G.2.2 |
| url | https://arxiv.org/abs/2405.09656 |