Graph-based clustering with minimum spanning trees and Jensen-Shannon distance
Anomaly detection using an incremental learning algorithm based on minimum spannin...
Dual bounds and exact algorithms for minimum dilation problems in geometric graphs
| Full text | |
| Author(s): |
Reed, Bruce
;
Stein, Maya
Total Authors: 2
|
| Document type: | Journal article |
| Source: | JOURNAL OF GRAPH THEORY; v. 102, n. 4, p. 47-pg., 2022-10-07. |
| Abstract | |
In this paper and a companion paper, we prove that, if m $m$ is sufficiently large, every graph on m + 1 $m+1$ vertices that has a universal vertex and minimum degree at least L 2 m 3 <SIC> RIGHT FLOOR $\lfloor \phantom{\rule[-0.5em]{}{0ex}}\frac{2m}{3}\rfloor $ contains each tree T $T$ with m $m$ edges as a subgraph. Our result confirms, for large m $m$, an important special case of a recent conjecture by Havet, Reed, Stein and Wood. The present paper already contains an approximate version of the result. (AU) | |
| FAPESP's process: | 19/13364-7 - Extremal and structural problems in graph theory |
| Grantee: | Cristina Gomes Fernandes |
| Support Opportunities: | Regular Research Grants |