| Texto completo | |
| Autor(es): |
Fernandes, Cristina G.
;
Mota, Guilherme Oliveira
;
Sanhueza-Matamala, Nicolas
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | RANDOM STRUCTURES & ALGORITHMS; v. 66, n. 3, p. 19-pg., 2025-05-01. |
| Resumo | |
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) | |
| Processo FAPESP: | 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática |
| Beneficiário: | Guilherme Oliveira Mota |
| Modalidade de apoio: | Auxílio à Pesquisa - Jovens Pesquisadores |
| Processo FAPESP: | 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos |
| Beneficiário: | Cristina Gomes Fernandes |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |