Graph decompositions and separations (2024)
- Authors:
- Autor USP: FERNANDES, ANTÔNIO KAIQUE BARROSO - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2024.tde-25082025-104946
- Assunto: TEORIA DOS GRAFOS
- Keywords: Conjuntos separadores; Caminhos multicoloridos; Cobertura; Covering; Grafo; Graph; Partição; Partition; Rainbow paths; Separating system; Sistema separador
- Agências de fomento:
- Language: Inglês
- Abstract: Esta dissertação de mestrado tem como objetivo principal apresentar o problema de conjuntos separadores, com foco no problema proposto por Katona de encontrar o tamanho do menor sistema separador das arestas de um grafo por caminhos. O texto apresenta a história do problema, bem como a prova apresentada por Bonamy, Botler, Dross, Naia e Skokan, que mostrou que todo grafo admite um sistema de caminhos separadores de tamanho linear no número de vértices. Ademais, apresentamos uma breve história dos problemas de coberturas em grafos e apresentamos resultados autorais desenvolvidos durante o período de pesquisa no mestrado. Inicialmente, provamos que, para p\gg (\log n)^{1/2}/n o grafo aleatório binomial G=G(n,p), com alta probabilidade, toda coloração própria das arestas de G admite uma cobertura de E(G) por \bigoh(n) caminhos multicoloridos. Em seguida, mostramos que para \varepsilon > 0 e p \geq n^{\varepsilon - 1}, o mesmo resultado vale
- Imprenta:
- Data da defesa: 15.10.2024
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
FERNANDES, Antônio Kaique Barroso. Graph decompositions and separations. 2024. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2024. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-25082025-104946/. Acesso em: 23 mar. 2026. -
APA
Fernandes, A. K. B. (2024). Graph decompositions and separations (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-25082025-104946/ -
NLM
Fernandes AKB. Graph decompositions and separations [Internet]. 2024 ;[citado 2026 mar. 23 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-25082025-104946/ -
Vancouver
Fernandes AKB. Graph decompositions and separations [Internet]. 2024 ;[citado 2026 mar. 23 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-25082025-104946/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
