A generalization of the block decomposition for k-connected graphs (2022)
- Authors:
- Autor USP: MALPARTIDA, JARED LEÓN - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2022.tde-02032023-200641
- Subjects: COMBINATÓRIA; TEORIA DOS GRAFOS
- Keywords: Árvore de blocos; Block decomposition; Block tree; Decomposição por blocos; K-conexidade; K-connectivity
- Agências de fomento:
- Language: Inglês
- Abstract: A decomposição de um grafo conexo pelo conjunto de seus vértices de corte, às vezes chamada de "decomposição por blocos" ou "árvore de blocos" de um grafo, é um conceito bem conhecido e básico na teoria dos grafos. Essa decomposição, no entanto, não fornece informações significativas quando é aplicada a um grafo k-conexo para k >1. Tem havido uma série de tentativas de generalizar a construção da decomposição em blocos para grafos k-conexos. Notavelmente, Tutte construiu uma árvore que descreve o arranjo mútuo dos 2-cutsets em um grafo 2-conexo. Esta decomposição tem algumas semelhanças com a decomposição por blocos de um grafo conexo. Em outros trabalhos, um bloco de um grafo k-conexo é definido como um subgrafo (k+1)-conexo maximal. Karpov descreveu a decomposição de um grafo k-conexo pelo conjunto dos seus k-cutsets que não são separados por nenhum outro k-cutset do grafo. Karpov também descreveu algumas propriedades de sua decomposição para o caso de um grafo 2-conexo. As decomposições definidas por Karpov e Tutte para o caso de grafos 2-conexos compartilham algumas semelhanças. Neste trabalho, nós apresentamos uma descrição autocontida da decomposição de Karpov. Nós também apresentamos algumas aplicações para o estudo de planaridade, número cromático, grafos criticamente 2-conexos, e a partição de certos grafos 2-conexos em três subgrafos conexos
- Imprenta:
- Data da defesa: 15.12.2022
- 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
MALPARTIDA, Jared León. A generalization of the block decomposition for k-connected graphs. 2022. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2022. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-02032023-200641/. Acesso em: 19 mar. 2026. -
APA
Malpartida, J. L. (2022). A generalization of the block decomposition for k-connected graphs (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-02032023-200641/ -
NLM
Malpartida JL. A generalization of the block decomposition for k-connected graphs [Internet]. 2022 ;[citado 2026 mar. 19 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-02032023-200641/ -
Vancouver
Malpartida JL. A generalization of the block decomposition for k-connected graphs [Internet]. 2022 ;[citado 2026 mar. 19 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-02032023-200641/
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
