| Full text | |
| Author(s): |
Fernandes, Cristina G.
;
Mota, Guilherme Oliveira
;
Sanhueza-Matamala, Nicolas
Total Authors: 3
|
| Document type: | Journal article |
| Source: | RANDOM STRUCTURES & ALGORITHMS; v. 66, n. 3, p. 19-pg., 2025-05-01. |
| Abstract | |
We prove that in any n-vertex complete graph, there is a collection P of (1+o(1))n paths that strongly separates any pair of distinct edges e,f, meaning that there is a path in P, which contains e but not f. Furthermore, for certain classes of n-vertex alpha n-regular graphs, we find a collection of (3 alpha+1-1+o(1))n paths that strongly separates any pair of edges. Both results are best-possible up to the o(1) term. (AU) | |
| FAPESP's process: | 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics |
| Grantee: | Guilherme Oliveira Mota |
| Support Opportunities: | Research Grants - Young Investigators Grants |
| FAPESP's process: | 19/13364-7 - Extremal and structural problems in graph theory |
| Grantee: | Cristina Gomes Fernandes |
| Support Opportunities: | Regular Research Grants |