Separating Path Systems in Complete Graphs
ABSTRACT We prove that in any ‐vertex complete graph, there is a collection of paths that strongly separates any pair of distinct edges , meaning that there is a path in , which contains but not . Furthermore, for certain classes of ‐vertex ‐regular graphs, we find a collection of paths that strongly separates any pair of edges. Both results are best‐possible up to the term.
Authors
- Cristina G. Fernandes (ORCID: https://orcid.org/0000-0002-5259-2859)
- Nicolás Sanhueza‐Matamala (ORCID: https://orcid.org/0000-0003-4791-5710)
- Guilherme Oliveira Mota (ORCID: https://orcid.org/0000-0001-9722-1819)
Institutions
- University of Concepción (CL)
- Universidade de São Paulo (BR)
- Brazilian Society of Computational and Applied Mathematics (BR)
Publication Details
- Journal
- Random Structures and Algorithms
- Published
- 2025-05-01
- DOI
- https://doi.org/10.1002/rsa.70006
- Citations
- 2
- Primary Topic
- graph theory and CDMA systems
- Type
- article
- Field-Weighted Citation Impact
- 1.46
Funders
- Fundação de Amparo à Pesquisa do Estado de São Paulo
- Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
- Conselho Nacional de Desenvolvimento Científico e Tecnológico
- Agencia Nacional de Investigación y Desarrollo