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
- Este periódico é de acesso aberto
- Este artigo NÃO é de acesso aberto
-
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://www.teses.usp.br/teses/disponiveis/45/45134/tde-25082025-104946/. Acesso em: 22 jan. 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://www.teses.usp.br/teses/disponiveis/45/45134/tde-25082025-104946/ -
NLM
Fernandes AKB. Graph decompositions and separations [Internet]. 2024 ;[citado 2026 jan. 22 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-25082025-104946/ -
Vancouver
Fernandes AKB. Graph decompositions and separations [Internet]. 2024 ;[citado 2026 jan. 22 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-25082025-104946/
Informações sobre o DOI: 10.11606/D.45.2024.tde-25082025-104946 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
